Search-Based Online Trajectory Planning for Car-like Robots in Highly Dynamic Environments
This work addresses real-time motion planning for car-like robots in dynamic settings, which is incremental as it builds on existing search-based methods with algorithmic improvements.
The paper tackles the problem of generating dynamically feasible trajectories for car-like robots in highly dynamic environments, achieving near-time-optimal solutions with planning times in milliseconds and a higher success rate compared to state-of-the-art methods.
This paper presents a search-based partial motion planner to generate dynamically feasible trajectories for car-like robots in highly dynamic environments. The planner searches for smooth, safe, and near-time-optimal trajectories by exploring a state graph built on motion primitives, which are generated by discretizing the time dimension and the control space. To enable fast online planning, we first propose an efficient path searching algorithm based on the aggregation and pruning of motion primitives. We then propose a fast collision checking algorithm that takes into account the motions of moving obstacles. The algorithm linearizes relative motions between the robot and obstacles and then checks collisions by comparing a point-line distance. Benefiting from the fast searching and collision checking algorithms, the planner can effectively and safely explore the state-time space to generate near-time-optimal solutions. The results through extensive experiments show that the proposed method can generate feasible trajectories within milliseconds while maintaining a higher success rate than up-to-date methods, which significantly demonstrates its advantages.