Coarse grid partition to speed up A* robot navigation. (17th February 2020)

• Record Type: Journal Article
• Authors: Wang, Chien-Yen; Yang, Chan-Yun; Banitaan, Shadi; Luo, Chaomin; Galsanbadam, Sainzaya
• Is Part Of: Journal of the Chinese Institute of Engineers. Volume 43:Number 2(2020)
• Page Start: 186
• Page End: 199
• Publication Date: 2020-02-17
• Subjects: Robot navigation -- obstacle avoidance -- path planning -- divide-and-conquer; Technology -- Periodicals; Engineering -- Periodicals; 620.005
• DOI: 10.1080/02533839.2019.1694444
• Languages: English
• ISSNs: 0253-3839

Abstract

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 ( n 2 ) 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.