Fast Time-optimal Avoidance of Moving Obstacles for High-Speed MAV Flight

Marius Beul, Sven Behnke

Abstract

In this work, we propose a method to efficiently compute smooth, time-optimal trajectories for micro aerial vehicles (MAVs) evading a moving obstacle. Our approach first computes an n-dimensional trajectory from the start- to an arbitrary target state including position, velocity and acceleration. It respects input- and state-constraints and is thus dynamically feasible. The trajectory is then efficiently checked for collisions, exploiting the piecewise polynomial formulation. If collisions occur, viastates are inserted into the trajectory to circumvent the obstacle and still maintain time-optimality. These viastates are described by position, velocity, and acceleration. The evaluation shows that the computational demands of the proposed method are minimal such that obstacle avoidance can begin within few milliseconds. Optimality of generated trajectories, combined with the ability for frequent online re-planning from non-hover initial conditions, make the approach well suited for evasion of suddenly perceived obstacles during fast flight.

Introduction

High-speed autonomous flight requires a delicate balance between aggressive maneuvers and safety. When a Micro Aerial Vehicle (MAV) operates at high velocity, it must react to obstacles—both static and moving—almost instantaneously. Traditional global planners are often too computationally expensive for high-speed reactive maneuvers, while many local reactive methods ignore complex vehicle dynamics like jerk limits or produce suboptimal paths that significantly reduce flight speed. This paper introduces a local planner that is both time-optimal and computationally efficient enough to run in a real-time control loop at 10Hz or higher.

Methodology

The proposed approach builds upon jerk-limited trajectory generation and follows a three-step pipeline:

1. Partially Defined Target States

The trajectory generator is extended to handle targets where not all variables (position, velocity, acceleration) are fixed. This flexibility allows the drone to pass through specific regions or gaps where, for instance, the exact velocity in a certain direction is not critical to the mission success.

2. Efficient Collision Detection

Trajectories are represented as piecewise polynomials of rank 3. This formulation allows the system to check for collisions by solving for the zero-crossings of the combined MAV and obstacle motion. This analytical approach is significantly faster than discrete sampling methods.

Candidate trajectories generated to avoid a moving cuboid obstacle, color-coded by velocity.

3. Optimal Viastate Insertion

When a collision is detected, the algorithm inserts a "viastate" at a corner of the obstacle. To maintain time-optimality, the system must find the optimal velocity at this viastate. Rather than using iterative searches, the authors identify "bound" axes and model the time-cost surface of the trajectory segments. By fitting second-order polynomials to the "grooves" of these surfaces and solving a fourth-order polynomial, the system analytically finds the globally optimal velocity for the detour.

Dynamic profiles (position, velocity, acceleration, and jerk) showing the piecewise polynomial structure and constraint satisfaction.

Key Insights

  • Analytical Solutions: By reducing the optimization problem to a fourth-order polynomial, the method bypasses iterative gradient descent, avoiding local minima and high latency.
  • Dimensionality Scaling: The method scales efficiently with the number of axes. For a 3D drone, the system only needs to check a handful of candidate detours (e.g., over, under, left, right) to identify the fastest path.

Evaluation and Results

The system was evaluated using MATLAB simulations and extensive "fuzz testing" involving over 10 million random trajectories with randomized start/target states.

  • Latency: The entire pipeline, including collision checking and candidate generation, takes less than 6 ms on a single mobile CPU core (Intel i7-4710MQ).
  • Efficiency: Detours are highly optimized; in test scenarios, avoiding a moving obstacle added as little as 0.02 seconds to a 7.31-second flight.
  • Robustness: Fuzz testing confirmed the solver's stability across millions of edge-case scenarios.

Conclusion and Future Work

While the current method is exceptionally fast and time-optimal, it assumes obstacles are axis-aligned hyperrectangles and requires perfect knowledge of obstacle states. Future work may involve extending the geometry to more complex shapes and incorporating uncertainty modeling to handle sensor noise. The authors have released the code as open source to facilitate integration into existing MAV control stacks.

Summary updated

Abstract

In this work, we propose a method to efficiently compute smooth, time-optimal trajectories for micro aerial vehicles (MAVs) evading a moving obstacle. Our approach first computes an n-dimensional trajectory from the start- to an arbitrary target state including position, velocity and acceleration. It respects input- and state-constraints and is thus dynamically feasible. The trajectory is then efficiently checked for collisions, exploiting the piecewise polynomial formulation. If collisions occur, viastates are inserted into the trajectory to circumvent the obstacle and still maintain time-optimality. These viastates are described by position, velocity, and acceleration. The evaluation shows that the computational demands of the proposed method are minimal such that obstacle avoidance can begin within few milliseconds. Optimality of generated trajectories, combined with the ability for frequent online re-planning from non-hover initial conditions, make the approach well suited for evasion of suddenly perceived obstacles during fast flight.
BibTeX
@inproceedings{beul2019fast,
  author = {Marius Beul and Sven Behnke},
  title = {{Fast Time-optimal Avoidance of Moving Obstacles for High-Speed MAV Flight}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=PGUe3549kL},
}
Figure