Improved Search-Based Quadrotors Motion Planning with Motion Primitives

Search-based motion planning with motion primitives is a complete and optimal method, and it can generate dynamically feasible, collision-free, smooth trajectories in dense environments. To further enhance the computational efficiency of this method while maintaining its completeness and optimality, we focus on the motion primitive graph search strategy and collision detection method, and propose three improvements: (1) We design an admissible heuristic function that considers environmental obstacles, which is pre-computed based on a modified Dijkstra algorithm and is stored in a Look-Up table; (2) We propose two motion primitive cost penalty strategies by penalizing the angle between the velocity and the yaw direction after the generation of motion primitives. The penalty strategies not only smooth the trajectory but also direct the search process toward more promising paths, thereby improving search efficiency. (3) In structured obstacle environments, we propose a novel motion primitive collision detection method with linear complexity based on Sturm’s theory; Finally, extensive simulations validate that our algorithm, with the above three improvements, greatly enhances computational performance by more than 38.1% on our benchmark, without sacrificing the completeness and optimality.