Optimization-Based Collision Avoidance

Zhang, Xiaojing; Liniger, Alexander; Borrelli, Francesco · 2020 · OpenAlex-citations

DOI: 10.1109/tcst.2019.2949540

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of formulating collision avoidance constraints for optimization-based trajectory planning, specifically for autonomous systems navigating in environments with obstacles. Traditional methods often rely on approximations, integer variables, or point-mass models, which limit their applicability to full-dimensional objects or real-time nonlinear control. The authors propose a novel method to reformulate non-differentiable collision avoidance constraints into smooth nonlinear constraints using the strong duality of convex optimization. This approach applies to general obstacles and controlled objects represented as unions of convex sets, such as polytopes or ellipsoids, without introducing approximations. The methodology involves two primary formulations. First, for collision-free trajectory generation, the distance between the controlled object and obstacles is reformulated using dual variables, resulting in smooth non-convex constraints that can be solved using gradient- and Hessian-based optimization algorithms. Second, to handle scenarios where collision is unavoidable, the authors introduce a signed distance formulation based on penetration depth. This allows the optimization framework to compute "least-intrusive" trajectories by minimizing penetration when strict collision avoidance is infeasible. The framework extends from point-mass models to full-dimensional objects by incorporating rotation and translation matrices, ensuring that the generated trajectories are kinodynamically feasible. Numerical experiments demonstrate the efficacy of the proposed framework on a quadcopter navigation task and an automated parking problem. In these tight environments, the method successfully generates real-time trajectories that avoid obstacles or minimize penetration when avoidance is impossible. The results indicate that the smoothness of the reformulated constraints enables the use of general-purpose nonlinear programming solvers, such as IPOPT, to solve the optimization problems efficiently. The authors provide source code for their implementation, highlighting the practical applicability of the method for robotic manipulators, self-driving cars, and other autonomous systems. The significance of this work lies in its ability to handle complex, full-dimensional collision avoidance problems without resorting to mixed-integer programming or conservative approximations. By leveraging strong duality, the method provides exact reformulations that preserve continuity and differentiability, facilitating real-time optimization-based planning. This contributes to the field of autonomous systems by offering a robust tool for trajectory generation in constrained environments, where traditional methods may fail or become computationally prohibitive. The approach bridges the gap between theoretical optimization and practical implementation, enabling safer and more efficient navigation for autonomous vehicles.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• perception reaction time