← Back to work
03 · Engineering

Multi-Drone Motion Planning

RRT-Connect & Decision Making under Uncertainty

Multi-Drone Motion Planning result figure
Overview

Completed two motion planning assessments. The first implemented centralized Bi-directional RRT-Connect in a 3K-dimensional configuration space for multi-drone collision-free path planning. The second implemented Monte Carlo Tree Search with UCT and progressive widening for decision making under uncertainty, using simulation-guided action selection and smart rollouts.

Results
↑ Team Size
↓ Success Rate
↑ Env. Complexity
↑ Planning Time
↑ Action Space
↓ Success Rate
↑ Planning Budget
↑ Success Rate
Process
01
Assessment 1 — Bidirectional RRT-Connect
Centralized Multi-Drone Motion Planning
  • → Model each drone as a 3D position (x, y, z)
  • → Construct a 3K-dimensional joint configuration space
  • → Grow two trees from the start and goal configurations
  • → Randomly sample configurations and extend the trees
  • → Check collision-free paths and connect the two trees
  • → Extract and validate the final path
  • → Analyse performance across different environment complexities and team sizes
Explore:
  • → Environment Complexity: Harder environments required more iterations and planning time, while narrow passages reduced the success rate to 76.7%.
  • → Team Size: As the number of drones increased, planning time, tree size, and path length also increased, with success dropping from 100% for 1–4 drones to 73.3% for 8 drones.
02
Assessment 2 — MCTS-UCT
Decision Making under Uncertainty
  • → Use UCT to balance exploration and exploitation
  • → Apply progressive widening to control the growing action space
  • → Use simulation-guided action selection and smart rollouts
  • → Backpropagate discounted rewards through the search tree
  • → Analyse performance across different team sizes and planning budgets
Explore:
  • → Team Size: With 8 possible actions per drone, the joint action space grew from 8 to 4,096 actions as the team size increased from 1 to 4 drones. Under a fixed planning budget, success dropped from 83% to 10%.
  • → Planning Budget: Increasing the planning time from 0.5 to 3.5 s/step improved success from 16.7% to 56.7%, with diminishing returns beyond roughly 2–3 s/step.
Stack
PythonRRT-ConnectMCTSMDP
Notes

What surprised me most was how quickly complexity became the main challenge in multi-drone planning. In RRT-Connect, the joint configuration space grew with the number of drones, while in MCTS-UCT, the joint action space grew exponentially. Across both assessments, I found that improving planning quality often came with a higher computational cost. This project gave me a better understanding of the trade-offs involved in designing scalable planning algorithms.