Abstract:To address the difficulty of graph-based path planning algorithms in finding optimal paths in continuous spaces and the low efficiency of path generation in sampling-based path planning algorithms, this paper proposes an optimal path planning algorithm based on Informed Sampling of Convex Dissection (CDI-RRT*). The algorithm first performs a convex dissection of the static map and establishes a topological graph. Guided by this topological graph, the A* algorithm is used to generate an initial path, which is then optimized using the elastic band algorithm to obtain an initial locally optimal path. Subsequently, the algorithm constructs an initial tree under the guidance of the topological graph and integrates partition line constraints with the informed set constraints of the Informed-RRT* algorithm to create a dynamic sampling area. By randomly sampling within this dynamic sampling area to optimize the initial tree, the algorithm plans the optimal path. Finally, the CDI-RRT* algorithm is compared with current advanced optimal path planning algorithms through experiments in both simulation and real-world scenarios. The experimental results show that the CDI-RRT* algorithm outperforms the compared algorithms in key metrics such as initial path generation efficiency and optimal path generation efficiency, fully validating the feasibility and effectiveness of the proposed algorithm.