On the average path lengths of typical sensor-based path-planning algorithms by uncertain random mazes
On the average path lengths of typical sensor-based path-planning algorithms by uncertain random mazes
复制标题
典型基于传感器的不确定随机迷宫路径规划算法的平均路径长度
DOI：
10.1109/cira.2003.1222135
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
H. Noborio
中科院分区：
文献类型：
--
作者：
R. Nogami;S. Hirao;H. Noborio
在基于传感器的路径规划中，已经完全求出了所有算法的最坏路径长度下界。然而，我们很难计算它们的平均路径长度。然而，在实际应用中，评价是很有价值的。此外，最差路径长度为最优的算法并不总是等于平均路径长度为最优的算法。本文对几乎所有基于传感器的路径规划算法在1000多种未知迷宫中的平均路径长度进行了仿真和比较。对于每个不确定迷宫中所有对起始点和目标点，得到所有路径长度，并通过仿真计算它们的和。由此可见，最坏路径长度无界的HD-I算法在平均路径长度上是最好的，最坏路径最优的Rev2算法在平均路径长度上是最好的。
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.