Final colloquium Qingyi Ren

Real-Time Trajectory Planning Design of Car-like Robots on Uneven Terrain with Dynamic Obstacles

Supervisor: Tamas Keviczky

Abstract:
This thesis introduces two improvements in trajectory planning on uneven terrain with dynamic obstacles: the Dynamic Traversability-based Hybrid A* (DT Hybrid A*) algorithm and the Safety Direction Velocity Obstacle (DSVO) replanning method. The DT Hybrid A* differs from traditional path-planning approaches by adopting a less conservative strategy, incorporating vehicle momentum into terrain traversability in order to more accurately reflect the vehicle's capability to navigate uneven terrain. Based on dynamic traversability, the DT Hybrid A* is developed by leveraging a kinematic bicycle model for steering, allowing variable travel lengths between adjacent nodes, and incorporating both distance and time heuristics. These enhancements significantly reduce CPU time costs during the planning process, resulting in shorter path lengths and faster planning times.

This thesis incorporates a collision detection mechanism within the global path planning framework, enabling the system to replan if a potential collision is predicted in the future. The replanning process initializes the global path to avoid all static obstacles. With the movement of dynamic obstacles, if a potential conflict is recognized, the vehicle discards the current global path and replans from its current location. To ensure that the replanned path is free of dynamic obstacles, the collision detection mechanism incorporates Safety and Direction Elements based on a VO cost term into the global path algorithm (DSVO). 

The DSVO algorithm enhances collision avoidance by integrating Safety and Direction Elements based on a VO cost term, surpassing traditional methods that use Euclidean distance penalties. DSVO avoids collisions by considering obstacle velocity and direction over time. It enhances the rate of successful replans for dynamic obstacle avoidance, producing the shortest collision-free paths with minimal computational overhead and completion time. The effectiveness of these approaches highlights the balance between computational efficiency and dynamic obstacle management, paving the way for more reliable path replanning solutions. 

DSVO surpasses methods that use Euclidean distance as a penalty for dynamic obstacles because it considers the obstacle's velocity and direction over time. It also outperforms the Safety Element based on a VO cost term, which only ensures collision avoidance within a short time frame and provides the optimal velocity for that period but does not account for longer-term safety, potentially leading to collisions over extended durations. Additionally, since these are cost terms within global path planning algorithms, there can be conflicts between obstacle avoidance and achieving the goal. The DSVO algorithm, which incorporates Safety and Direction Elements based on a VO cost term, mitigates conflicts between obstacle avoidance and goal achievement. Additionally, DSVO effectively adjusts the path to navigate around dynamic obstacles while maintaining a direct route toward the goal, balancing safety and efficiency.