A Partitioning-Based Approach for Robot Path Planning Problems

摘要

Path planning is one of the most important studied problems in the field of autonomous robots. The autonomous robot should pass around obstacles from a given starting position to a given target position, touching none of them, i.e. the goal is to find a collision-free path from the starting to the target position. Research on path planning has generated many fundamentally different approaches to the solution of this problem, in which A* algorithm is the one of the outstanding approaches have been developed for solving this problem, but it only ensures that the algorithm gives its result within a large amount of time-consumption. Therefore, in this paper, a Partitioning-Based Path Planning approach, called PBPP, has been proposed by partitioning-based and hierarchical methods that effectively improve the A* algorithm. The PBPP uses the concept of divide-and-conquer to divide the global map into each of sub-map in which a collision-free space is able to be represented. Furthermore, hierarchical planning can provide more feasible direction to achieve a smooth path in the result of the optimal path. The experimental results demonstrate the PBPP‘s utility for reducing time-consumption and finding low-cost paths.