Coarse grid partition to speed up A* robot navigation

Abstract

Path planning is one of the most focused on problems in the field of autonomous robots. The autonomous robot should pass around obstacles from a given starting position to a goal position without touching them. Research on path planning has pursued many different approaches to the solution of this problem, in which the A* algorithm is one of the outstanding approaches that has been widely disseminated in applications, but the algorithm utilizes a large amount of time. Therefore, an alternative Partitioning-Based Path Planning approach, namely PBPP, is proposed to reduce time consumption using a hierarchical partitioning method to improve the A* algorithm. A combination of the two concepts, the coarse-to-fine grid map representation and the A* path planner, which achieves a near-shortest path in O(n2) computational complexity is the main contribution of the study. Conceptually, the PBPP uses the principle of divide-and-conquer to divide the global map into several sub-maps in which individual collision-free spaces are able to be decomposed and represented. With the subdivided maps, hierarchical planning can provide a 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 the shortest path.