凸最適化の双対性を用いた衝突回避制約の平滑化手法
Optimization-Based Collision Avoidance
微分不可能な衝突回避制約を凸最適化の強双対性で滑らかな非線形制約に変換し、勾配・ヘッセ行列ベースの最適化でリアルタイム軌道計画を可能にした研究。
著者: Xiaojing Zhang, Alexander Liniger, Francesco Borrelli
分類: math.OC, cs.RO, cs.SY, eess.SY
原文アブストラクト
This paper presents a novel method for reformulating non-differentiable collision avoidance constraints into smooth nonlinear constraints using strong duality of convex optimization. We focus on a controlled object whose goal is to avoid obstacles while moving in an n-dimensional space. The proposed reformulation does not introduce approximations, and applies to general obstacles and controlled objects that can be represented in an n-dimensional space as the finite union of convex sets. Furthermore, we connect our results with the notion of signed distance, which is widely used in traditional trajectory generation algorithms. Our method can be used in generic navigation and trajectory planning tasks, and the smoothness property allows the use of general-purpose gradient- and Hessian-based optimization algorithms. Finally, in case a collision cannot be avoided, our framework allows us to find "least-intrusive" trajectories, measured in terms of penetration. We demonstrate the efficacy of our framework on a quadcopter navigation and automated parking problem, and our numerical experiments suggest that the proposed methods enable real-time optimization-based trajectory planning problems in tight environments. Source code of our implementation is provided at https://github.com/XiaojingGeorgeZhang/OBCA.
