Search-Based Online Trajectory Planning for Car-like Robots in Highly Dynamic Environments

Abstract

This paper presents a search-based partial motion planner for generating feasible trajectories of 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. To enable fast online planning, we 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 calculating a point-line distance. Benefiting from the fast searching and collision checking algorithms, the planner can effectively explore the state-time space to generate near-time-optimal solutions. 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.