⚡ electrical engineering

Efficient Collision-Avoidance Constraints for Ellipsoidal Obstacles in Optimal Control: Application to Path-Following MPC and UAVs

This paper presents a modular optimal control framework featuring a computationally efficient, continuously differentiable collision-avoidance condition for ellipsoidal obstacles, which is validated through simulations and real-world 3D experiments on a Crazyflie quadrotor using a novel two-stage optimization approach to address numerical challenges.

Original authors: David Leprich, Mario Rosenfelder, Markus Herrmann-Wicklmayr, Kathrin Flaßkamp, Peter Eberhard, Henrik Ebel

Published 2026-08-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David Leprich, Mario Rosenfelder, Markus Herrmann-Wicklmayr, Kathrin Flaßkamp, Peter Eberhard, Henrik Ebel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of robotics, the difference between a machine that works and one that crashes often comes down to how it sees the space around it. For a robot to move safely, it must constantly calculate where it is, where it is going, and what might get in its way. This is especially true for flying machines like drones, which navigate a three-dimensional world filled with invisible air currents and sudden obstacles. While engineers have long known how to plot a course from point A to point B, doing so in real time while dodging unexpected objects is a formidable challenge. If a drone relies on a pre-planned route, it might fly straight into a newly appeared obstacle. If it tries to react too quickly without a solid plan, it might become unstable or crash. The core difficulty lies in creating a control system that is fast enough to make split-second decisions but smart enough to understand the complex shape of the world and the physical limits of the machine itself.

This is the problem tackled by a team of researchers who have developed a new way for drones to avoid collisions in real time. Their work focuses on a specific type of obstacle: the ellipsoid, which is essentially a stretched or squashed sphere, like a rugby ball or a flattened egg. By treating both the drone and the obstacles as these smooth, rounded shapes, the team created a mathematical method to quickly determine if the two are about to touch. Unlike older methods that might struggle with complex calculations or get stuck when things get too close, this new approach provides a smooth, continuous way to check for danger. It allows the drone's computer to constantly ask, "If I move this way, will I hit that object?" and get a clear, immediate answer that can be used to adjust its flight path instantly.

The researchers applied this method to a model predictive controller, a type of software that acts like a forward-thinking pilot. Instead of just reacting to what is happening right now, this controller looks ahead, simulating several possible future paths to see which one is safest and most efficient. The team tested this system on a small, lightweight drone called the Crazyflie 2.1, which is roughly the size of a human hand. In their experiments, the drone was given a specific path to follow, but a static, egg-shaped obstacle was placed directly in its way. The obstacle was detected at runtime, and the drone's control system was tasked with avoiding a collision with it. The results were successful: the drone smoothly deviated from its original course to slip around the obstacle and then returned to its path, all without crashing or losing stability.

To make this work in the real world, where computers have limited speed, the researchers introduced a clever two-step process. The first step involves finding the best way to measure the distance between the drone and the obstacle, essentially tuning a variable that defines how close the drone can safely get. The second step uses that information to solve the complex math required to steer the drone. By separating these tasks, the system avoids getting bogged down by difficult calculations, allowing it to run fast enough for real-time control. In their tests, the system completed these calculations in less than two milliseconds for most instances, well within the time limits required to keep the drone stable. This speed was crucial, as the drone's motors need to be adjusted hundreds of times per second to stay in the air.

The team also demonstrated that this method works for moving obstacles, not just stationary ones. In a simulation, they introduced an obstacle that drifted slowly through the air. The drone successfully tracked the moving object, adjusted its speed and direction to avoid a collision, and continued along its intended route. This capability is significant because it shows the system can handle dynamic environments where things are constantly changing. The researchers noted that while their method is highly effective, it does require the drone to be approximated as a simple shape. In their specific tests, they modeled the drone as an ellipsoid based on its physical dimensions, which worked well because the drone stayed relatively level during flight.

What makes this achievement particularly notable is that it represents the first time such a sophisticated control system has been demonstrated on actual hardware in a fully three-dimensional task. Previous attempts often relied on simplified, two-dimensional scenarios or were limited to simulations. By proving that this approach works on a real drone flying in a real room, the researchers have shown that complex, safety-critical calculations can be performed quickly enough for practical use. The system did not just avoid the obstacle; it did so while trying to stay as close as possible to the original path, balancing safety with efficiency. This balance is essential for robots that need to perform tasks like delivery or inspection, where straying too far from a planned route could waste time or energy.

The success of these experiments suggests a path forward for more autonomous robots. The method is modular, meaning it could potentially be adapted for different types of machines or different kinds of obstacles. The researchers plan to explore how their system handles even more complex shapes and to provide stronger mathematical guarantees that the system will always work as intended. For now, the demonstration with the Crazyflie drone serves as a concrete proof that advanced, real-time collision avoidance is possible. It moves the field from theoretical models to working machines, showing that with the right mathematical tools, robots can navigate our cluttered, unpredictable world with a new level of confidence and safety.

Technical Summary: Efficient Collision-Avoidance Constraints for Ellipsoidal Obstacles in Optimal Control

Problem Statement
In robotic applications, particularly for unmanned aerial vehicles (UAVs), ensuring safe operation in complex environments requires effective collision avoidance. While global path planners can generate geometric paths avoiding known static obstacles, they often fail to account for dynamic behaviors or a-priori unknown local obstacles discovered in real-time. Re-planning global paths continuously is computationally prohibitive. Conversely, local controllers that integrate obstacle avoidance directly into the control loop face significant challenges. Specifically, incorporating anti-collision constraints into Optimal Control Problems (OCPs) in a manner that is both differentiable and computationally efficient is non-trivial. Naïve implementations often result in slow, unreliable solvers, hindering real-time closed-loop operation. Furthermore, existing methods often struggle to extend beyond planar (2D) scenarios to fully three-dimensional (3D) tasks while maintaining numerical stability.

Methodology
The authors propose a modular optimal control framework designed for local 3D ellipsoidal obstacle avoidance, applied specifically to Model Predictive Path-Following Control (MPC).

Ellipsoidal Representation and Collision Detection:
Both the robot (UAV) and obstacles are modeled as ellipsoids defined by a quadratic form $E(P, r) = \{x \in \mathbb{R}^3 \mid (x-r)^\top P (x-r) \leq 1\}$ . To detect collisions efficiently, the framework utilizes a computationally efficient and continuously differentiable condition derived from the intersection of two ellipsoids. This condition relies on an auxiliary ellipsoid $E_\lambda$ , constructed as a convex combination of the robot's and obstacle's shape matrices. The non-intersection of two ellipsoids is guaranteed if there exists a parameter $\lambda \in [0, 1]$ such that a scalar function $K(\lambda)$ is negative. Specifically, the condition $K(\lambda) < 0$ implies the ellipsoids do not intersect, while $K(\lambda) > 0$ indicates a collision. This formulation allows the collision constraint to be integrated directly into the OCP as a smooth, differentiable constraint.
Path-Following MPC Formulation:
The control task is defined as following a time-independent geometric path $P$ while avoiding local obstacles. A timing law $g(z, \nu)$ governs the evolution of the path parameter $s$ , treating it as a state variable with a virtual input $\nu$ . The MPC minimizes a stage cost that penalizes deviations from the path, control effort, and virtual input, subject to system dynamics and state/input constraints. The collision avoidance condition is formulated as $K(\lambda, x) \leq 0$ for each prediction step. This inequality constraint allows for the case where $K=0$ (ellipsoids touching but not overlapping) or $K<0$ (no overlap), while strictly prohibiting $K>0$ (collision).
Two-Stage Optimization Approach:
Solving the resulting OCP presents numerical challenges, primarily due to the absence of the collision parameter $\lambda$ in the stage cost, which can lead to ill-conditioning in Sequential Quadratic Programming (SQP) solvers. To mitigate this, the authors introduce a two-stage optimization scheme:
- Stage 1: For a given state prediction, the parameter $\lambda$ is optimized to minimize $K(\lambda, x)$ over the horizon. This is a cheap, convex scalar optimization.
- Stage 2: The optimized $\lambda$ values are treated as fixed parameters in the main MPC problem, which is then solved for the control inputs and state trajectory.
  This process is iterative (Algorithm 1), alternating between updating $\lambda$ and solving the MPC, typically converging within a single iteration in practice.
Dynamic Model:
The framework is validated using a Crazyflie 2.1 quadrotor. The high-level MPC operates at 50 Hz, providing reference signals to a fast low-level attitude controller (500 Hz). The system dynamics are modeled as a continuous-time system incorporating the effects of the low-level attitude loop via first-order lag elements for roll and pitch.

Key Contributions

3D Extension: The work extends previous 2D collision-avoidance MPC approaches to fully three-dimensional space, handling both static and moving ellipsoidal obstacles.
Differentiable Collision Constraint: It employs a continuously differentiable condition for ellipsoidal collision detection, making it suitable for gradient-based optimal control solvers.
Numerical Stability: A novel two-stage optimization approach is introduced to resolve numerical ill-conditioning issues arising from the structure of the OCP, ensuring short computation times suitable for real-time applications.
Hardware Demonstration: The approach is validated through real-world experiments, marking a significant step in practical UAV control.

Experimental Results
The proposed method was tested in an indoor environment using a motion capture system (OptiTrack) for state estimation.

Static Obstacle Scenario: In a real-world experiment, the Crazyflie successfully followed a geometric path while avoiding a static, unknown ellipsoidal obstacle. The drone deviated from the path only as necessary to maintain a safe distance, demonstrating the trade-off between path tracking and safety.
Dynamic Obstacle Simulation: Simulations were conducted with a moving obstacle, showing the controller's ability to adapt to time-varying obstacle positions.
Performance: The two-stage optimization algorithm demonstrated high computational efficiency. Empirical cumulative distribution function (eCDF) analysis showed that 75% of optimization steps completed in under 2 ms, with a maximum time of 5.6 ms, well within the 20 ms sampling interval.
Robustness: The system handled minor state estimation inaccuracies by utilizing soft constraints, preventing solver crashes while maintaining safety.

Significance and Claims
The authors assert that this work represents the first hardware demonstration of an MPC controller of this specific kind (integrating ellipsoidal collision avoidance via a two-stage optimization) for UAVs in a three-dimensional task. The paper highlights that while theoretical convergence guarantees for the iterative algorithm remain an open question, the experimental results confirm the practical feasibility and reliability of the approach for real-time collision avoidance in complex 3D environments. The framework is presented as a modular solution that can be adapted for various robotic platforms beyond the quadrotor.

Technical Summary: Efficient Collision-Avoidance Constraints for Ellipsoidal Obstacles in Optimal Control

More like this