A Review of Global Path Planning Methods for Occupancy Grid Maps Regardless of Obstacle Density

详细信息    查看全文

• 作者：E. G. Tsardoulias ; A. Iliakopoulou ; A. Kargakos…
• 关键词：Path planning ; Probabilistic RoadMaps ; Visibility graph ; Generalized Voronoi graph ; Rapidly exploring random trees ; Occupancy grid maps
• 刊名：Journal of Intelligent & Robotic Systems
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：84
• 期：1-4
• 页码：829-858
• 全文大小：
• 刊物类别：Engineering
• 刊物主题：Control, Robotics, Mechatronics; Electrical Engineering; Artificial Intelligence (incl. Robotics); Mechanical Engineering;
• 出版者：Springer Netherlands
• ISSN：1573-0409
• 卷排序：84

文摘

Path planning constitutes one of the most crucial abilities an autonomous robot should possess, apart from Simultaneous Localization and Mapping algorithms (SLAM) and navigation modules. Path planning is the capability to construct safe and collision free paths from a point of interest to another. Many different approaches exist, which are tightly dependent on the map representation method (metric or feature-based). In this work four path planning algorithmic families are described, that can be applied on metric Occupancy Grid Maps (OGMs): Probabilistic RoadMaps (PRMs), Visibility Graphs (VGs), Rapidly exploring Random Trees (RRTs) and Space Skeletonization. The contribution of this work includes the definition of metrics for path planning benchmarks, actual benchmarks of the most common global path planning algorithms and an educated algorithm parameterization based on a global obstacle density coefficient.