A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical Map

Abstract

Although the popular path-planning algorithms based on graph-search such as Dijkstra and A* guarantee to find the optimal path, the search time will increase rapidly with the growth of map size. Those traditional graph-search based algorithms ignore the distribution of obstacles, causing much time wasted on exploring unrelated regions. A fast bidirectional-A* algorithm based on hierarchical map(QH-A*) was proposed in this paper with high real-time performance. QH-A* consists of two parts: offline pre-processing and online search. The offline pre-processing of QH-A* comprises map decomposition and construction of hierarchical map. In the map decomposition step, a modified quad-tree decomposition method was used to recursively divide the initial map into different regions. Then boundary nodes of each region were extracted. During the construction of hierarchical map, a kind of hierarchical map was defined and precomputation was done to construct the hierarchical map. In the online-search step, a revised bidirectional-A* specific to hierarchical map was proposed to finish the path-planning task. Experiments and theories proved that QH-A* can always find the shortest path. In addition, the search area required by QH-A* was 70%-80% less than that of A*, which verified high real-time performance of QH-A*.

Keywords

• Quad-tree decomposition
• bi-directional A*
• hierarchical map
• real-time path planning