A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical Map
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9475032/ |
| _version_ | 1811210295969841152 |
|---|---|
| author | Zhou Yijun Xi Jiadong Luo Chen |
| author_facet | Zhou Yijun Xi Jiadong Luo Chen |
| author_sort | Zhou Yijun |
| collection | DOAJ |
| description | 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*. |
| first_indexed | 2024-04-12T04:53:17Z |
| format | Article |
| id | doaj.art-31205b1607ac4cc8b6a71f529569a979 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-12T04:53:17Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-31205b1607ac4cc8b6a71f529569a9792022-12-22T03:47:14ZengIEEEIEEE Access2169-35362021-01-01910287710288510.1109/ACCESS.2021.30948549475032A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical MapZhou Yijun0https://orcid.org/0000-0002-3838-7779Xi Jiadong1https://orcid.org/0000-0002-8023-0169Luo Chen2School of Mechanical Engineering, Southeast University, Nanjing, ChinaSchool of Mechanical Engineering, Southeast University, Nanjing, ChinaSchool of Mechanical Engineering, Southeast University, Nanjing, ChinaAlthough 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*.https://ieeexplore.ieee.org/document/9475032/Quad-tree decompositionbi-directional A*hierarchical mapreal-time path planning |
| spellingShingle | Zhou Yijun Xi Jiadong Luo Chen A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical Map IEEE Access Quad-tree decomposition bi-directional A* hierarchical map real-time path planning |
| title | A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical Map |
| title_full | A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical Map |
| title_fullStr | A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical Map |
| title_full_unstemmed | A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical Map |
| title_short | A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical Map |
| title_sort | fast bi directional a x002a algorithm based on quad tree decomposition and hierarchical map |
| topic | Quad-tree decomposition bi-directional A* hierarchical map real-time path planning |
| url | https://ieeexplore.ieee.org/document/9475032/ |
| work_keys_str_mv | AT zhouyijun afastbidirectionalax002aalgorithmbasedonquadtreedecompositionandhierarchicalmap AT xijiadong afastbidirectionalax002aalgorithmbasedonquadtreedecompositionandhierarchicalmap AT luochen afastbidirectionalax002aalgorithmbasedonquadtreedecompositionandhierarchicalmap AT zhouyijun fastbidirectionalax002aalgorithmbasedonquadtreedecompositionandhierarchicalmap AT xijiadong fastbidirectionalax002aalgorithmbasedonquadtreedecompositionandhierarchicalmap AT luochen fastbidirectionalax002aalgorithmbasedonquadtreedecompositionandhierarchicalmap |