Search-based Planning of Dynamic MAV Trajectories Using Local Multiresolution State Lattices

Daniel Schleich, Sven Behnke

Abstract

Search-based methods that use motion primitives can incorporate the system's dynamics into the planning and thus generate dynamically feasible MAV trajectories that are globally optimal. However, searching high-dimensional state lattices is computationally expensive. Local multiresolution is a commonly used method to accelerate spatial path planning. While paths within the vicinity of the robot are represented at high resolution, the representation gets coarser for more distant parts. In this work, we apply the concept of local multiresolution to high-dimensional state lattices that include velocities and accelerations. Experiments show that our proposed approach significantly reduces planning times. Thus, it increases the applicability to large dynamic environments, where frequent replanning is necessary.

Introduction

Planning trajectories for Micro Aerial Vehicles (MAVs) requires more than simple geometric pathfinding; it necessitates finding paths that respect the vehicle's dynamic constraints. State lattices offer a solution by unrolling pre-calculated motion primitives into a graph. However, the high dimensionality of these state spaces—incorporating position, velocity, and acceleration—often leads to a computational bottleneck. In dynamic environments where real-time obstacle avoidance is critical, standard A* searches on uniform grids can take several seconds, which is unacceptable for safe flight. This paper addresses the challenge by introducing local multiresolution to high-dimensional state lattices.

Methodology

The core of the proposed approach is the Local Multiresolution State Lattice. By varying the resolution based on the distance from the MAV, the planner focuses computational resources where they are most needed.

Local Multiresolution Grid

The environment is partitioned into levels. Level-1, immediately surrounding the drone, maintains the highest spatial and velocity resolution. As the distance increases, the resolution halves at each subsequent level. This significantly prunes the search tree in distant regions while maintaining precision for immediate maneuvers.

The local multiresolution concept: (a) shows the multi-level grid structure, and (b) provides a detailed view of the connectivity between nodes at different resolutions.

Adaptive Motion Primitives and Snapping

To maintain graph connectivity across varying resolution levels, the system utilizes adaptive motion primitives. Instead of fixed trajectories, the endpoints of primitives are "snapped" to the nearest grid corners of the current resolution level. This is achieved by slightly adjusting the acceleration of the primitive, ensuring a valid and continuous graph structure without complex transition logic.

Adaptive motion primitives: (a) illustrates the original primitives with red arrows indicating the adjustment required to (b) snap the endpoints to the grid corners.

Heuristics and Expansion

To further accelerate the A search, the authors precompute optimal costs for 1D sub-problems (X, Y, and Z axes) and store them in lookup tables. Additionally, they introduce a Level-Based Expansion Scheme. This modification prevents A from becoming trapped in exhaustive searches of fine-grained nodes when a slightly more "expensive" but much faster coarse path is available at a higher level.

Experimental Results

The method was evaluated in a simulated 128x128m outdoor environment using the RotorS simulator and OctoMap. In 100 random trajectory tasks, the multiresolution approach demonstrated significant improvements over uniform-resolution baselines:

  • Computational Speed: Mean maximum replanning time dropped from 3.54 seconds to 0.19–0.30 seconds.
  • Reliability: The multiresolution approach achieved a 100% success rate in complex scenarios where the baseline only succeeded 71% of the time within node limits.
  • Efficiency: The trade-off for this speed was minimal, with trajectory costs increasing by only 5-6% compared to the global optimum.

Conclusion

By applying local multiresolution to high-dimensional state lattices, this research enables real-time, dynamically feasible trajectory planning for MAVs. The combination of adaptive snapping and a level-based expansion scheme overcomes the traditional computational hurdles of state-lattice search. Future work aims to extend this to third-order systems (incorporating jerk) and integrate moving obstacle predictions directly into the heuristic search.

Summary updated

Abstract

Search-based methods that use motion primitives can incorporate the system's dynamics into the planning and thus generate dynamically feasible MAV trajectories that are globally optimal. However, searching high-dimensional state lattices is computationally expensive. Local multiresolution is a commonly used method to accelerate spatial path planning. While paths within the vicinity of the robot are represented at high resolution, the representation gets coarser for more distant parts. In this work, we apply the concept of local multiresolution to high-dimensional state lattices that include velocities and accelerations. Experiments show that our proposed approach significantly reduces planning times. Thus, it increases the applicability to large dynamic environments, where frequent replanning is necessary.
BibTeX
@inproceedings{schleich2021search,
  author = {Daniel Schleich and Sven Behnke},
  title = {{Search-based Planning of Dynamic MAV Trajectories Using Local Multiresolution State Lattices}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2021},
  url = {https://openreview.net/forum?id=ZUsR4VNXgAR},
}
Figure