Efficient Motion Planning for Problems Lacking Optimal Substructure
Efficient Motion Planning for Problems Lacking Optimal Substructure
复制标题
针对缺乏最佳子结构问题的高效运动规划
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Srinivasa
中科院分区：
文献类型：
--
作者：
Oren Salzman;Brian Hou;S. Srinivasa
我们考虑的运动规划问题规划的无碰撞路径的机器人存在的风险区。机器人被允许在这些区域中行进，但是以超线性的方式对在那里花费的连续累积时间进行惩罚。我们建议一个自然的成本函数，平衡路径长度和风险暴露时间。具体来说，我们考虑离散设置，其中我们给出了一个图或路线图，并且我们希望在此成本函数下计算最小成本路径。有趣的是，使用我们的成本函数定义的路径没有最佳子结构。即，最优路径的子路径不一定是最优的。因此，Bellman条件不被满足，并且不能使用标准图搜索算法，例如Dijkstra。我们提出了一个路径查找算法，它可以被看作是一个自然的推广Dijkstra的算法。算法的时间复杂度为O（（n B· n）log（n B · n）+ n B · m），其中n和m分别是图的顶点数和边数，n B是边与危险区边界的交点数.我们提出了机器人平台上的模拟演示我们的成本函数和我们的算法的计算效率产生的自然路径。
We consider the motion-planning problem of planning a collision-free path of a robot in the presence of risk zones. The robot is allowed to travel in these zones but is penalized in a super-linear fashion for consecutive accumulative time spent there. We suggest a natural cost function that balances path length and risk-exposure time. Specifically, we consider the discrete setting where we are given a graph, or a roadmap, and we wish to compute the minimal-cost path under this cost function. Interestingly, paths defined using our cost function do not have an optimal substructure. Namely, subpaths of an optimal path are not necessarily optimal. Thus, the Bellman condition is not satisfied and standard graph-search algorithms such as Dijkstra cannot be used. We present a path-finding algorithm, which can be seen as a natural generalization of Dijkstra’s algorithm. Our algorithm runs in O ((n B · n) log(n B · n) + n B · m) time, where n and m are the number of vertices and edges of the graph, respectively, and n B is the number of intersections between edges and the boundary of the risk zone. We present simulations on robotic platforms demonstrating both the natural paths produced by our cost function and the computational efficiency of our algorithm.