Multi-UAV 3D Path Planning — RRT* + OSM

A modular Python research project for planning collision-free 3-D trajectories for multiple UAVs in real urban environments, using OpenStreetMap building data and the RRT* algorithm.

---

Features

• Real map data — downloads building footprints and street networks from OpenStreetMap via OSMnx, or loads a local .osm file.
• 3-D obstacle extrusion — each building polygon is extruded to its OSM height (or a configurable default) for full 3-D collision checking.
• RRT and RRT* — vanilla RRT and the asymptotically-optimal RRT* with KDTree nearest-neighbour queries and the rewire step.
• Shortcut smoothing — removes redundant waypoints while respecting obstacle geometry.
• Multi-UAV deconfliction — trajectories are synchronised onto a common time grid; pairwise conflicts are detected and resolved via altitude offset or delay strategies.
• Visualisation — dark-themed 2-D map view, 3-D matplotlib render, and a frame-by-frame animation.
• Fallback synthetic map — runs offline with a procedurally-generated city grid when OSM data is unavailable.

---

Project structure

multi_uav_rrt/
├── main.py                     # Orchestration pipeline
├── config.py                   # All tunable parameters
├── requirements.txt
│
├── environment/
│   ├── osm_loader.py           # OSMnx download / local file parsing
│   ├── building_map.py         # 3-D polygon obstacle collection
│   └── occupancy_map.py        # Optional voxel grid representation
│
├── planners/
│   ├── node.py                 # RRT tree node dataclass
│   ├── state_space.py          # 3-D state space + sampling
│   ├── rrt.py                  # Vanilla RRT
│   └── rrt_star.py             # RRT* with KDTree + rewire
│
├── smoothing/
│   └── path_smoothing.py       # Shortcut smoothing + uniform resampling
│
├── multi_uav/
│   ├── collision_detection.py  # Pairwise conflict detection
│   ├── trajectory_edit.py      # Altitude-offset and delay resolution
│   └── trajectory_sync.py      # Common time-grid synchronisation
│
├── visualization/
│   ├── plot2d.py               # Top-down 2-D map
│   ├── plot3d.py               # 3-D extruded buildings + paths
│   └── plot_animation.py       # Animated drone playback
│
└── utils/
    ├── geometry.py             # Point-to-segment distance, path length
    └── conversions.py          # Lat/lon ↔ local metres helpers

---

Installation

# 1. Clone / unzip the project
cd multi_uav_rrt

# 2. Create a virtual environment (recommended)
python -m venv .venv
source .venv/bin/activate      # Windows: .venv\Scripts\activate

# 3. Install dependencies
pip install -r requirements.txt

Note: osmnx requires libspatialindex for R-tree indexing. On Ubuntu/Debian: sudo apt install libspatialindex-dev On macOS (Homebrew): brew install spatialindex

---

Quick start

python main.py

On first run the script downloads OSM data for Connaught Place, New Delhi (configurable in config.py). If the network is unavailable it falls back to a synthetic city grid automatically.

---

Configuration (config.py)

Parameter	Default	Description
LOCATION_NAME	"Connaught Place, New Delhi, India"	OSMnx place name
MAP_RADIUS_M	500	Download radius (metres)
OSM_CRS	"EPSG:32643"	UTM CRS — change for other cities
DEFAULT_BUILDING_HEIGHT	20.0	Fallback height when OSM tag absent
NUM_UAVS	3	Number of UAVs to plan for
RRT_STEP_SIZE	8.0	Maximum tree extension per iteration (m)
RRT_MAX_ITERATIONS	3000	Iteration budget per UAV
SAFETY_DISTANCE	6.0	Minimum inter-UAV separation (m)
UAV_MIN_ALTITUDE	5.0	Minimum flight altitude AGL (m)
UAV_MAX_ALTITUDE	80.0	Maximum flight altitude AGL (m)

Changing the city

Find the correct UTM EPSG for your city at epsg.io and update OSM_CRS.

# London
LOCATION_NAME = "City of London, London, UK"
OSM_CRS       = "EPSG:32630"

# New York
LOCATION_NAME = "Midtown Manhattan, New York, USA"
OSM_CRS       = "EPSG:32618"

---

Using the animation

from visualization.plot_animation import animate_trajectories
import matplotlib.pyplot as plt

anim = animate_trajectories(bmap, synced, starts, goals)
plt.show()

# Save as GIF (requires Pillow)
anim.save("uav_flight.gif", writer="pillow", fps=20)

---

Using the planner as a library

from environment.building_map import BuildingMap
from planners.state_space import StateSpace3D
from planners.rrt_star import RRTStar
import geopandas as gpd

# Load your own GeoDataFrame of building polygons
gdf = gpd.read_file("my_buildings.gpkg")
bmap = BuildingMap(gdf, default_height=15.0)

space = StateSpace3D(xmin=-200, xmax=200, ymin=-200, ymax=200, zmin=5, zmax=80)
planner = RRTStar(space=space, bmap=bmap, step_size=8, max_iter=5000)

path = planner.plan(start=[-150, -150, 10], goal=[150, 150, 20])

---

Architecture overview

OSM data (osmnx)
    │
    ▼
BuildingMap          ← polygon obstacles + 3-D collision API
    │
    ├─► StateSpace3D  ← 3-D bounding box, sampling, steer
    │        │
    │        ▼
    │     RRTStar     ← plan(start, goal) → raw waypoints
    │
    ├─► shortcut_smoothing  → smooth waypoints
    │
    ├─► synchronise_trajectories  → common time grid
    │
    ├─► detect_conflicts  → list[Conflict]
    │
    ├─► resolve_by_altitude_offset  → edited trajectories
    │
    └─► plot_2d / plot_3d / animate_trajectories

---

Extending the project

Add a new conflict-resolution strategy Implement a function with the signature:

def resolve_by_xxx(
    trajectories: Dict[int, List[np.ndarray]],
    conflicts: List[Conflict],
    **kwargs,
) -> Dict[int, List[np.ndarray]]: ...

and call it in main.py instead of (or after) resolve_by_altitude_offset.

Swap in the voxel occupancy map

from environment.occupancy_map import OccupancyMap3D
omap = OccupancyMap3D(bmap, resolution=2.0)
# Pass omap.segment_collides as the collision checker to the planner

Add dynamic obstacles Subclass BuildingMap and override segment_collides to include time-varying geometry.

---

Known limitations

• The shortcut smoother is randomised; results vary between runs (set seed for reproducibility).
• Very dense urban areas (> 500 buildings in a 200 m radius) may slow per-iteration collision checking — reduce MAP_RADIUS_M or enable the voxel occupancy map for faster lookups.
• Altitude-offset conflict resolution is greedy; it does not re-check the shifted trajectory against buildings. For safety-critical applications, re-run the planner after each altitude shift.

---

References

• Karaman, S. & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. IJRR.
• Boeing, G. (2017). OSMnx: New methods for acquiring, constructing, analysing, and visualising complex street networks. Computers, Environment and Urban Systems.