FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First Search
The majority of planning algorithms used are based on the occupancy grid maps, but in complicated situations, the occupancy grid maps have a significant search overhead. This paper proposed a path planner based on the visibility graph (v-graph) for the mobile robot that uses sparse methods to speed...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-08-01
|
| Series: | Remote Sensing |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2072-4292/14/15/3720 |
| _version_ | 1797412428509609984 |
|---|---|
| author | Qunzhao Li Fei Xie Jing Zhao Bing Xu Jiquan Yang Xixiang Liu Hongbo Suo |
| author_facet | Qunzhao Li Fei Xie Jing Zhao Bing Xu Jiquan Yang Xixiang Liu Hongbo Suo |
| author_sort | Qunzhao Li |
| collection | DOAJ |
| description | The majority of planning algorithms used are based on the occupancy grid maps, but in complicated situations, the occupancy grid maps have a significant search overhead. This paper proposed a path planner based on the visibility graph (v-graph) for the mobile robot that uses sparse methods to speed up and simplify the construction of the v-graph. Firstly, the complementary grid framework is designed to reduce graph updating iteration costs during the data collection process in each data frame. Secondly, a filter approach based on the edge length and the number of vertices of the obstacle contour is proposed to reduce redundant nodes and edges in the v-graph. Thirdly, a bidirectional breadth-first search is combined into the path searching process in the proposed fast path planner algorithm in order to reduce the waste of exploring space. Finally, the simulation results indicate that the proposed sparse v-graph planner can significantly improve the efficiency of building the v-graph and reduce the time of path search. In highly convoluted unknown or partially known environments, our method is 40% faster than the FAR Planner and produces paths 25% shorter than it. Moreover, the physical experiment shows that the proposed path planner is faster than the FAR Planner in both the v-graph update process and laser process. The method proposed in this paper performs faster when seeking paths than the conventional method based on the occupancy grid. |
| first_indexed | 2024-03-09T05:01:55Z |
| format | Article |
| id | doaj.art-4157a70daba744c192b95881e74521fd |
| institution | Directory Open Access Journal |
| issn | 2072-4292 |
| language | English |
| last_indexed | 2024-03-09T05:01:55Z |
| publishDate | 2022-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Remote Sensing |
| spelling | doaj.art-4157a70daba744c192b95881e74521fd2023-12-03T12:58:35ZengMDPI AGRemote Sensing2072-42922022-08-011415372010.3390/rs14153720FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First SearchQunzhao Li0Fei Xie1Jing Zhao2Bing Xu3Jiquan Yang4Xixiang Liu5Hongbo Suo6School of Electrical and Automation Engineering, Nanjing Normal University, Nanjing 210023, ChinaSchool of Electrical and Automation Engineering, Nanjing Normal University, Nanjing 210023, ChinaCollege of Automation & College of Artificial Intelligence, Nanjing University of Posts and Telecommunications, Nanjing 210023, ChinaDepartment of Aeronautical and Aviation Engineering, The Hong Kong Polytechnic University, Hong Kong, ChinaSchool of Electrical and Automation Engineering, Nanjing Normal University, Nanjing 210023, ChinaCollege of Instrument Science & Engineering, Southeast University, Nanjing 210096, ChinaNanjing Zhongke Raycham Laser Technology Co., Ltd., Nanjing 210023, ChinaThe majority of planning algorithms used are based on the occupancy grid maps, but in complicated situations, the occupancy grid maps have a significant search overhead. This paper proposed a path planner based on the visibility graph (v-graph) for the mobile robot that uses sparse methods to speed up and simplify the construction of the v-graph. Firstly, the complementary grid framework is designed to reduce graph updating iteration costs during the data collection process in each data frame. Secondly, a filter approach based on the edge length and the number of vertices of the obstacle contour is proposed to reduce redundant nodes and edges in the v-graph. Thirdly, a bidirectional breadth-first search is combined into the path searching process in the proposed fast path planner algorithm in order to reduce the waste of exploring space. Finally, the simulation results indicate that the proposed sparse v-graph planner can significantly improve the efficiency of building the v-graph and reduce the time of path search. In highly convoluted unknown or partially known environments, our method is 40% faster than the FAR Planner and produces paths 25% shorter than it. Moreover, the physical experiment shows that the proposed path planner is faster than the FAR Planner in both the v-graph update process and laser process. The method proposed in this paper performs faster when seeking paths than the conventional method based on the occupancy grid.https://www.mdpi.com/2072-4292/14/15/3720visibility graphcomputational geometrypath planningmapping |
| spellingShingle | Qunzhao Li Fei Xie Jing Zhao Bing Xu Jiquan Yang Xixiang Liu Hongbo Suo FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First Search Remote Sensing visibility graph computational geometry path planning mapping |
| title | FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First Search |
| title_full | FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First Search |
| title_fullStr | FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First Search |
| title_full_unstemmed | FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First Search |
| title_short | FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First Search |
| title_sort | fps fast path planner algorithm based on sparse visibility graph and bidirectional breadth first search |
| topic | visibility graph computational geometry path planning mapping |
| url | https://www.mdpi.com/2072-4292/14/15/3720 |
| work_keys_str_mv | AT qunzhaoli fpsfastpathplanneralgorithmbasedonsparsevisibilitygraphandbidirectionalbreadthfirstsearch AT feixie fpsfastpathplanneralgorithmbasedonsparsevisibilitygraphandbidirectionalbreadthfirstsearch AT jingzhao fpsfastpathplanneralgorithmbasedonsparsevisibilitygraphandbidirectionalbreadthfirstsearch AT bingxu fpsfastpathplanneralgorithmbasedonsparsevisibilitygraphandbidirectionalbreadthfirstsearch AT jiquanyang fpsfastpathplanneralgorithmbasedonsparsevisibilitygraphandbidirectionalbreadthfirstsearch AT xixiangliu fpsfastpathplanneralgorithmbasedonsparsevisibilitygraphandbidirectionalbreadthfirstsearch AT hongbosuo fpsfastpathplanneralgorithmbasedonsparsevisibilitygraphandbidirectionalbreadthfirstsearch |