A Statistically Rigorous Analysis of 2D Path-Planning Algorithms

作者：Munoz Pablo; Barrero David F; R Moreno Maria D^*

来源：Computer Journal, 2015, 58(11): 2876-2891.

DOI：10.1093/comjnl/bxu137

• path planning
• statistic distribution
• run time
• heading changes
• path-length

Path-planning is a well-known studied problem in Artificial Intelligence. Given two points in a map, path-planning algorithms search for a path that joins those two points, avoiding obstacles. It is a challenging problem with important practical applications in a wide range of applications: autonomous mobile robotics, logistics or video games, just to mention some of them. Given its importance, it has attracted much research, resulting in a large number of algorithms, some classical, such as A*, other more specialized, such as swarms. However, despite all the literature dedicated to this problem, the statistics used to analyze experimental results in most cases are na < ve. In this paper, we position in favor of the need of incorporating stronger statistical methods in path-planning empirical research and promote a debate in the research community. To this end, we analyze some 2D-grid classical path-planning algorithms in discrete domains (i.e. A* and A* with post-processing) and more recent algorithms in continuous domains (i.e. Theta* and S-Theta*). Given the differences of these algorithms, we study them under different criteria: Run-time, number of heading changes, number of expanded vertices and path-length.

• 出版日期2015-11