Paper Info
Title
FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First Search
Abstract
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.
Year
DOI
Venue
2022
10.3390/rs14153720
REMOTE SENSING
Keywords
DocType
Volume
visibility graph, computational geometry, path planning, mapping
Journal
14
Issue
ISSN
Citations 
15
2072-4292
0
PageRank 
References 
Authors
0.34
0
7
Name
Order
Citations
PageRank
Qunzhao Li100.34
Fei Xie242.01
Jing Zhao310759.16
Bin Xu413323.23
Jiquan Yang500.68
Xixiang Liu600.68
Hongbo Suo700.34