On the average path lengths of typical sensor-based path-planning algorithms by uncertain random mazes
Ryo Nogami, S. Hirao, H. Noborio · 2004
In the sensor-based path-planning, the lower bounds of worst path lengths of all algorithms have been completely evaluated. However, it is quite difficult for us to evaluate their average path lengths. However, in a practical use, the evaluation is worth much. Moreover, an algorithm whose worst path length is optimal does not always equal to an algorithm whose average path length is optimal. In this paper, average path lengths of almost all the sensor-based path-planning algorithms are simulated and compared in more than 1000 kinds of unknown mazes. For all pairs of start and goal points in each uncertain maze, all path lengths are obtained and their sum is calculated by simulation. As a result, we can see that our algorithm HD-I whose worst path length is not bounded is the best and our algorithm Rev2 whose worst path is optimal is the better concerning to the average path length.