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.
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.
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