不連続性を許容するA*探索による動力学拘束下の移動ロボット運動計画
db-A*: Discontinuity-bounded Search for Kinodynamic Mobile Robot Motion Planning
グラフ探索と軌道最適化を組み合わせ、運動プリミティブ間の不連続性を許容しつつ局所修正する時間最適運動計画手法db-A*を提案し、探索・サンプリング・最適化手法との比較ベンチマークで優位性を示した。
著者: Wolfgang Hoenig, Joaquim Ortiz-Haro, Marc Toussaint
分類: cs.RO
原文アブストラクト
We consider time-optimal motion planning for dynamical systems that are translation-invariant, a property that holds for many mobile robots, such as differential-drives, cars, airplanes, and multirotors. Our key insight is that we can extend graph-search algorithms to the continuous case when used symbiotically with optimization. For the graph search, we introduce discontinuity-bounded A* (db-A*), a generalization of the A* algorithm that uses concepts and data structures from sampling-based planners. Db-A* reuses short trajectories, so-called motion primitives, as edges and allows a maximum user-specified discontinuity at the vertices. These trajectories are locally repaired with trajectory optimization, which also provides new improved motion primitives. Our novel kinodynamic motion planner, kMP-db-A*, has almost surely asymptotic optimal behavior and computes near-optimal solutions quickly. For our empirical validation, we provide the first benchmark that compares search-, sampling-, and optimization-based time-optimal motion planning on multiple dynamical systems in different settings. Compared to the baselines, kMP-db-A* consistently solves more problem instances, finds lower-cost initial solutions, and converges more quickly.
