最適部分構造を持たない問題に対する効率的な動作計画
Efficient motion planning for problems lacking optimal substructure
リスクゾーンでの累積滞在時間に超線形ペナルティを課す新コスト関数を提案し、最適部分構造が成立しない問題でも解けるダイクストラ拡張アルゴリズムを開発した。
著者: Oren Salzman, Brian Hou, Siddhartha Srinivasa
分類: cs.RO
原文アブストラクト
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\left((n_B\cdot n) \log( n_B\cdot n) + n_B\cdot m\right)$ 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.
