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