Statistic Methods for Path-Planning Algorithms Comparison

Abstract

The path-planning problem for autonomous mobile robots has been addressed by classical search techniques such as A* or, more recently, Theta* or S-Theta*. However, research usually focuses on reducing the length of the path or the processing time. The common practice in the literature is to report the run-time/length of the algorithm with means and, sometimes, some dispersion measure. However, this practice has several drawbacks, mainly due to the loose of valuable information that this reporting practice involves such as asymmetries in the run-time, or the shape of its distribution. Run-time analysis is a type of empirical tool that studies the time consumed by running an algorithm. This paper is an attempt to bring this tool to the path-planning community. To this end the paper reports an analysis of the run-time of the path-planning algorithms with a variety of problems of different degrees of complexity, indoors, outdoors and Mars surfaces. We conclude that the time required by these algorithms follows a lognormal distribution.