A Statistically Rigorous Analysis of 2D Path-Planning Algorithms

• Published in: Computer journal 2015-11, Vol.58 (11), p.2876-2891
• Main Authors: Muñoz, Pablo, Barrero, David F., R-Moreno, María D.
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial intelligence; Statistical methods
• ISSN: 0010-4620; 1460-2067
• DOI: 10.1093/comjnl/bxu137

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 naive. 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.