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

Marius Beul, Sven Behnke

Introduction

High-speed autonomous flight for Micro Aerial Vehicles (MAVs) requires a delicate balance between time-optimality and dynamic feasibility. While global planners are effective at pathfinding, they often struggle with real-time updates in dynamic environments. Conversely, reactive controllers are fast but frequently produce sub-optimal, jerky paths. Researchers at the University of Bonn have proposed a novel trajectory planner that bridges this gap, enabling MAVs to dodge moving obstacles with minimal time penalties by utilizing piecewise polynomial representations and a rapid "viastate" insertion method.

Problem Statement

The primary challenge in high-speed flight is maintaining a trajectory that respects physical limits on velocity, acceleration, and jerk while reacting to sudden obstacles. Existing solutions typically fall into two categories: computationally intensive global planners or fast but sub-optimal reactive controllers. This work aims to provide a mathematically optimal solution capable of running within a standard control loop (100Hz+), allowing for near-instantaneous evasive maneuvers.

Methodology

The proposed pipeline consists of three main components: trajectory generation, collision detection, and viastate insertion.

Trajectory Generation via Partially Defined States

Trajectories are modeled using piecewise constant jerk, resulting in 3rd-order polynomials. A significant innovation is the handling of partially defined target states. By allowing certain variables (like velocity in a specific direction) to remain "free," the solver can automatically optimize these values to minimize total flight time.

Dynamic feasibility of the generated trajectories, showing position, velocity, acceleration, and jerk profiles over time.

Efficient Collision Detection

Collision detection is formulated as a root-finding problem rather than a spatial search. By calculating the zero-crossings of the combined MAV and obstacle functions, the system can identify potential collisions with very low computational overhead.

Viastate Insertion for Avoidance

When a collision is detected, the algorithm inserts an intermediate "viastate" to steer the MAV around the obstacle. The system evaluates multiple potential maneuvers (e.g., over, under, left, right) to find the most time-efficient path. To avoid heavy numerical optimization, the optimal velocity at these viastates is determined using pre-calculated analytical solutions and polynomial fitting of "time-to-target" curves.

3D visualization of multiple candidate avoidance trajectories generated to bypass a dynamic obstacle.

Key Insights

  • Flexible State Definition: Using "NaN" (Not a Number) for undefined target dimensions allows the solver to pick the most efficient velocity or acceleration, providing greater flexibility than fixed-velocity dodge maneuvers.
  • Temporal Disconnection: Avoidance is achieved by "temporally disconnecting" the axes. By shifting the timing of one axis, the MAV can pass an obstacle's boundary earlier or later than the others, effectively dodging it.
  • Analytical Efficiency: By deriving analytical solutions for trajectory segments instead of relying on generic optimizers, the system achieves microsecond-level computation times.

Evaluation and Results

The method was rigorously tested using MATLAB simulations and extensive "fuzz testing" across 10 million random scenarios to ensure robustness. Key results include:

  • Computational Performance: The entire avoidance pipeline computes four optimal trajectories in less than 6 milliseconds on a standard laptop CPU.
  • Minimal Detour Penalty: In flight tests, the time penalty for avoiding a moving obstacle was as low as 0.02 seconds compared to the original, non-obstructed trajectory.
  • Scalability: The approach scales efficiently with the number of axes, making it applicable to higher-dimensional control problems.

Conclusion and Future Work

This research demonstrates a high-speed, time-optimal trajectory planner suitable for dynamic environments. While the current model assumes constant obstacle motion during the planning window, its high replanning rate mitigates this limitation. Future work may involve incorporating sensor uncertainty and expanding the system's capabilities for more cluttered, complex environments where global planning remains a necessity.

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},
}

Loading related content...

Figure