T*ε: 曲率拘束系のための有界準最適で効率的な最短時間動作計画
T*$\varepsilon$ -- Bounded-Suboptimal Efficient Motion Planning for Minimum-Time Planar Curvature-Constrained Systems
障害物環境で曲率拘束系(固定翼ドローン等)の最短時間経路を求める際、最適解ではなく1+ε倍の有界準最適解を許容することで、計算コストの高い時間最適遷移の評価回数を大幅に削減し、解品質の保証を保ちつつ実行時間を数桁短縮する手法を提案した。
著者: Doron Pinsky, Petr Váňa, Jan Faigl, Oren Salzman
分類: cs.RO, cs.AI
原文アブストラクト
We consider the problem of finding collision-free paths for curvature-constrained systems in the presence of obstacles while minimizing execution time. Specifically, we focus on the setting where a planar system can travel at some range of speeds with unbounded acceleration. This setting can model many systems, such as fixed-wing drones. Unfortunately, planning for such systems might require evaluating many (local) time-optimal transitions connecting two close-by configurations, which is computationally expensive. Existing methods either pre-compute all such transitions in a preprocessing stage or use heuristics to speed up the search, thus foregoing any guarantees on solution quality. Our key insight is that computing all the time-optimal transitions is both~(i)~computationally expensive and~(ii)~unnecessary for many problem instances. We show that by finding bounded-suboptimal solutions (solutions whose cost is bounded by $1+\varepsilon$ times the cost of the optimal solution for any user-provided $\varepsilon$) and not time-optimal solutions, one can dramatically reduce the number of time-optimal transitions used. We demonstrate using empirical evaluation that our planning framework can reduce the runtime by several orders of magnitude compared to the state-of-the-art while still providing guarantees on the quality of the solution.
