Optimization-Based Collision Avoidance¶
Authors: Xiaojing Zhang, Alexander Liniger, Francesco Borrelli
Published: 2017 (Journal Paper)
Source: IEEE Transactions on Control Systems Technology
Algorithm: OBCA
arXiv: 1711.03449
DOI: 10.1109/TCST.2019.2949540
Summary¶
Presents an optimization-based collision avoidance formulation using differentiable signed distance functions. Optimization problems are solved with general nonlinear solver IPOPT. Proposes using A* for warm-starting.
Abstract¶
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.
Links¶
Primary
Standard
Alternate
Tags¶
-
Collision avoidance
-
Trajectory optimization
-
Autonomous vehicles
-
Nonlinear optimization
-
Augmented Lagrangian