Hierarchical Quadrotor Planning & Decision-Making
Task: Navigate a quadrotor through increasingly complex indoor environments (open → cluttered → maze-like) visiting multiple goal checkpoints, while avoiding both known static obstacles and unknown dynamic ones that appear mid-flight.
Solution: A three-layer hierarchical architecture combining global path planning with local reactive control. A roadmap (PRM or Sukharev grid) is built once from the static map, and A*/Dijkstra computes shortest paths for each goal. An MPPI (Model Predictive Path Integral) controller follows this path in real-time, sampling thousands of candidate trajectories to track the reference while dodging unknown obstacles. A low-level PD attitude controller handles drone stabilisation. The system is evaluated in 2D and 3D simulation using gym-pybullet-drones.
Pipeline
- Layer 1 — Global Planning (offline, once): Build roadmap from static map: PRM (random sampling) or Sukharev grid (uniform spacing). For each goal checkpoint: graph search (A* or Dijkstra) → output sequence of collision-free waypoints
- Layer 2 — Local Planning (online, every timestep): Resample waypoints to uniform spacing → MPPI controller samples K random acceleration sequences, simulates each rollout over N steps, scores on tracking + velocity + effort + collision, weighted average → best acceleration, apply first command only (receding horizon) → deviates from path to dodge unknown obstacles
- Layer 3 — Attitude Control (stabilisation): Acceleration → roll/pitch via differential flatness → PD controller stabilises orientation → drone executes motion in simulation
Design Choices, Challenges & Insights
- PRM gives 20% shorter paths but grid is 6× faster and deterministic
- Dijkstra unexpectedly beat A* in maze environments due to heuristic overhead
- MPPI dodges unknown obstacles that PID blindly crashes into
- Rollouts and horizon must scale together or performance degrades
- Roadmap built once, reused for all goals — query time under 1 second
- MPPI is derivative-free, handles non-convex obstacles naturally
- Best config (K=2000, N=30) runs at only 1.2 Hz — needs GPU for real-time
