Optimal path planning under defferent norms in continuous state spaces
Optimal path planning under defferent norms in continuous state spaces
复制标题
连续状态空间中不同范数下的最优路径规划
DOI：
10.1109/robot.2006.1641818
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Ian M. Mitchell
中科院分区：
文献类型：
--
作者：
K. Alton;Ian M. Mitchell
在完全状态和地图知识下的最优路径规划通常使用Dijkstra算法的一些变体来完成，尽管它将路径域表示为离散图而不是连续空间。在本文中，我们比较Dijkstra的离散算法的一个变种（通常称为快速行进法），更准确地对待基本的连续空间。从分析上讲，两者都生成一个没有局部最小值的值函数，因此最优路径生成只需要梯度下降。我们还研究了使用的最优性度量以外的欧几里德距离这两种算法。这些不同的规范更好地代表了某些类型的问题的最佳路径，如规划多机器人场景的最佳无碰撞路径所示。当考虑与底层状态空间一致的近似时，我们的结论是快速行进对网格连接的约束较少，并且在许多但不是所有情况下，它比Dijkstra的离散算法实现更好的精度
Optimal path planning under full state and map knowledge is often accomplished using some variant of Dijkstra's algorithm, despite the fact that it represents the path domain as a discrete graph rather than as a continuous space. In this paper we compare Dijkstra's discrete algorithm with a variant (often called the fast marching method) which more accurately treats the underlying continuous space. Analytically, both generate a value function free of local minima, so that optimal path generation merely requires gradient descent. We also investigate the use of optimality metrics other than Euclidean distance for both algorithms. These different norms better represent optimal paths for some types of problems, as demonstrated by planning optimal collision-free paths for a multiple robot scenario. When considering approximations consistent with the underlying state space, our conclusion is that fast marching places fewer constraints upon grid connectivity, and that it achieves better accuracy than Dijkstra's discrete algorithm in many but not all cases