並列制約付きバーンスタイン法による安全・最適・リアルタイム軌道計画
Safe, Optimal, Real-time Trajectory Planning with a Parallel Constrained Bernstein Algorithm
移動ロボットの軌道計画において、各計画周期で大域的最適解を証明付きで求めるRTD*を提案し、それを実現する並列分枝限定法PCBAの実装・計算量保証・既存解法との比較・実機実証を行った論文。
著者: Shreyas Kousik, Bohao Zhang, Pengcheng Zhao, Ram Vasudevan
分類: math.OC, cs.RO
原文アブストラクト
To move through the world, mobile robots typically use a receding-horizon strategy, wherein they execute an old plan while computing a new plan to incorporate new sensor information. A plan should be dynamically feasible, meaning it obeys constraints like the robot's dynamics and obstacle avoidance; it should have liveness, meaning the robot does not stop to plan so frequently that it cannot accomplish tasks; and it should be optimal, meaning that the robot tries to satisfy a user-specified cost function such as reaching a goal location as quickly as possible. Reachability-based Trajectory Design (RTD) is a planning method that can generate provably dynamically-feasible plans. However, RTD solves a nonlinear polynmial optimization program at each planning iteration, preventing optimality guarantees; furthermore, RTD can struggle with liveness because the robot must brake to a stop when the solver finds local minima or cannot find a feasible solution. This paper proposes RTD*, which certifiably finds the globally optimal plan (if such a plan exists) at each planning iteration. This method is enabled by a novel Parallelized Constrained Bernstein Algorithm (PCBA), which is a branch-and-bound method for polynomial optimization. The contributions of this paper are: the implementation of PCBA; proofs of bounds on the time and memory usage of PCBA; a comparison of PCBA to state of the art solvers; and the demonstration of PCBA/RTD* on a mobile robot. RTD* outperforms RTD in terms of optimality and liveness for real-time planning in a variety of environments with randomly-placed obstacles.
