🤖 AI

Multi UAVs Preflight Planning in a Shared and Dynamic Airspace

This paper proposes DTAPP-IICR, a scalable and delivery-time aware prioritized planning framework that combines a novel 4D single-agent planner with iterative conflict resolution to enable efficient preflight planning for large-scale UAV fleets in dynamic, shared urban airspace.

Original authors: Amath Sow, Mauricio Rodriguez Cesen, Fabiola Martins Campos de Oliveira, Mariusz Wzorek, Daniel de Leng, Mattias Tiger, Fredrik Heintz, Christian Esteve Rothenberg

Published 2026-02-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Amath Sow, Mauricio Rodriguez Cesen, Fabiola Martins Campos de Oliveira, Mariusz Wzorek, Daniel de Leng, Mattias Tiger, Fredrik Heintz, Christian Esteve Rothenberg

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a future where the sky above our cities is filled with thousands of delivery drones, like a busy swarm of mechanical bees. They are dropping off pizza, medicine, and packages to your doorstep. But here's the problem: the sky isn't empty. There are "No-Fly Zones" (like temporary storm clouds or restricted areas around hospitals) that open and close at specific times, and the drones come in all different sizes and speeds.

If you try to plan the flight paths for 1,000 of these drones all at once using old-school methods, the computer would get overwhelmed, like a traffic cop trying to direct every car in a city simultaneously. It would either crash the system or take hours to find a solution.

This paper introduces a new, smarter way to plan these flights called DTAPP-IICR. Think of it as a super-organized air traffic control system designed specifically for a chaotic, dynamic sky.

Here is how it works, broken down into simple concepts:

1. The "Urgency Queue" (Prioritized Planning)

Imagine a busy coffee shop. Instead of trying to serve everyone at the exact same time, the barista calls out orders based on who needs their drink the most urgently.

How the paper does it: The system looks at all the drone missions and sorts them by urgency. The drones that have the tightest deadlines get to pick their path first. This prevents the system from getting stuck trying to solve a million problems at once.

2. The "Smart Solo Pilot" (SFIPP-ST)

Once a drone is picked to fly, it needs a pilot to plot its course. But this isn't a normal pilot; it's a "Smart Solo Pilot" (the SFIPP-ST algorithm).

The Challenge: The pilot has to avoid static buildings (hard obstacles) and temporary "No-Fly Zones" (like a construction zone that is only active between 2:00 PM and 2:30 PM).
The Trick: Unlike old planners that say "If you hit a wall, stop immediately," this pilot is flexible. It says, "If I might bump into another drone, I'll add a little 'penalty' to my score, but I won't stop. I'll keep looking for a better path." It treats potential collisions as "soft" bumps rather than hard walls, allowing it to find a route that is mostly clear.
The Roundtrip: It doesn't just plan the trip to the house; it plans the whole loop: fly there, wait for the package handover, and fly back home.

3. The "Directional Shortcut" (Pruning)

Imagine you are walking through a giant 3D maze made of cubes. At every step, you could go up, down, left, right, forward, backward, or diagonally in 26 different directions. Checking all 26 options at every single step is slow.

The Analogy: The paper introduces a "Directional Shortcut." If you are trying to get to the North-East corner of the maze, the system mostly looks at neighbors that are also North-East. It ignores the paths going South or West because they are moving you away from the goal.
The Safety Net: If the shortcut accidentally blocks the only way out, the system instantly switches back to checking all directions. This makes the planning 50% faster without ever getting stuck.

4. The "Group Therapy" (Iterative Conflict Resolution)

Even with the best planning, sometimes two drones still end up on a collision course. Maybe Drone A and Drone B both thought the same spot was safe.

The Old Way: You'd have to scrap the whole plan and start over from scratch.
The New Way (DTAPP-IICR): The system identifies the specific drones that are "fighting" (the conflict). It takes only those drones out of the plan and asks them to "re-plan" their paths, while everyone else stays put. It's like a group therapy session where only the people arguing get to speak, while the rest of the group waits.
The Graph: It uses a "Conflict Graph" (a map of who is fighting whom) to decide exactly which drones need to re-plan, ensuring the solution gets better with every round until everyone is happy.

Why This Matters

The researchers tested this on a computer with up to 1,000 drones flying in a city with moving "No-Fly Zones."

Old methods (like the ones used in standard traffic software) gave up or took forever when the number of drones got high.
This new method successfully planned paths for 1,000 drones with a near-perfect success rate.

In a nutshell:
This paper teaches us how to organize a massive, chaotic sky full of different-sized drones by letting the most urgent ones go first, giving them a flexible pilot that ignores minor bumps, using shortcuts to find the goal faster, and only re-planning the specific drones that get into trouble. It turns a "traffic jam in the sky" into a smooth, flowing river of delivery drones.

1. Problem Definition

The paper addresses the challenge of preflight planning for large-scale Unmanned Aerial Vehicle (UAV) fleets operating in shared, dynamic, low-altitude urban airspace. The specific problem involves:

Environment: A 4D space (3D grid + time) containing static obstacles (buildings, trees) and Temporal No-Fly Zones (NFZs) that activate and deactivate at specific times.
Agents: A heterogeneous fleet of UAVs with varying physical profiles (radii), speeds, and start times.
Mission Structure: Unlike standard point-to-point pathfinding, missions are roundtrips (Hub $\to$ Delivery Location $\to$ Wait $\to$ Hub).
Constraints:
- Hard Constraints: Strict avoidance of static obstacles and active NFZs.
- Soft Constraints: Inter-agent collisions (pursuit, head-on, intersection) are modeled as soft constraints to allow for iterative resolution rather than immediate rejection.
- Objective: Minimize total flowtime (total flight time) while ensuring collision-free, NFZ-compliant trajectories for all agents.

The authors argue that existing Multi-Agent Path Finding (MAPF) methods (like Batch CBS/ECBS) lack the scalability and flexibility required for dense, dynamic Unmanned Traffic Management (UTM) scenarios, particularly when handling heterogeneous agents and temporal constraints.

2. Methodology: DTAPP-IICR

The authors propose DTAPP-IICR (Delivery-Time Aware Prioritized Planning with Incremental and Iterative Conflict Resolution), a two-tier framework consisting of:

A. SFIPP-ST (Single-Agent Planner)

A novel 4D single-agent planner designed to handle heterogeneous profiles and temporal NFZs.

Safe Flight Intervals (SFI): The planner precomputes contiguous time intervals where a voxel is free from hard obstacles and active NFZs.
Soft Conflict Modeling: Instead of treating other agents as hard obstacles, SFIPP-ST treats their trajectories as soft constraints. It calculates a "conflict cost" based on geometric overlap (using continuous-time envelopes) and penalizes these in the search cost function.
Search Algorithm: An A*-like search that prioritizes nodes with lower conflict costs ( $c$ ) first, then minimizes travel time ( $f = g + h$ ).
Directional Pruning: To accelerate the search in a 26-connected 3D grid, the authors introduce a completeness-preserving directional pruning heuristic. It prioritizes neighbors that align with the goal vector (direction sector) but includes a fallback mechanism to expand all neighbors if pruning eliminates all valid moves, ensuring the algorithm remains complete.

B. DTAPP-IICR (Multi-Agent Framework)

A prioritized planning framework that integrates the single-agent planner with iterative conflict resolution.

Prioritization: UAVs are sorted by delivery urgency (start time $t_{init}$ ).
Initial Planning: Each UAV plans a roundtrip path sequentially using SFIPP-ST, treating previously planned paths as dynamic obstacles.
Iterative Conflict Resolution (LNS):
- If conflicts remain, the system identifies a subset of conflicting agents using a Geometric Conflict Graph.
- It employs Large Neighborhood Search (LNS): The paths of the selected conflicting agents are removed, and they are replanned sequentially while treating non-selected agents as fixed obstacles.
- This process repeats until a conflict-free solution is found or a time limit is reached.

3. Key Contributions

SFIPP-ST: A 4D single-agent planner that natively supports heterogeneous UAVs, strictly enforces temporal NFZs, and models inter-agent conflicts as soft constraints to facilitate iterative repair.
DTAPP-IICR Framework: An urgency-aware prioritized planner that combines sequential planning with LNS-based conflict resolution, specifically tailored for dense urban UTM environments.
Directional Pruning: A novel search acceleration technique that reduces the branching factor in 3D grids by up to 50% while mathematically guaranteeing search completeness.
Scalability: The framework successfully handles fleets of up to 1,000 UAVs in dynamic environments, a scale where traditional batch methods (CBS/ECBS) and standard priority-based methods fail.

4. Experimental Results

The authors evaluated the system using Monte Carlo simulations and a realistic city-scale map (400x400x25 grid) with varying obstacle densities and NFZ configurations.

Scalability (Up to 1,000 UAVs):
- DTAPP-IICR achieved a 100% success rate for fleets up to 1,000 UAVs.
- Batch CBS/ECBS failed to scale beyond small instances due to exponential complexity.
- Standard Priority Planning (PP) failed completely at 100 agents without pruning and struggled significantly with 250+ agents.
Runtime Efficiency:
- DTAPP-IICR was up to 15 times faster than standard Priority Planning.
- The directional pruning technique reduced runtime by 34–50% compared to the unpruned version.
Dynamic Constraints (Temporal NFZs):
- As the number of active NFZs increased, DTAPP-IICR maintained high success rates, whereas other methods (especially PP) saw success rates drop to 0% in dense scenarios.
- In a realistic urban simulation with 500 agents and 4 NFZs, DTAPP-IICR maintained an 89% success rate, while all other variants failed.
Comparison: The method outperformed Enhanced Conflict-Based Search (ECBS) and standard Priority Planning in both success rate and computation time, particularly in dense, dynamic environments.

5. Significance

This work provides a practical and scalable solution for the integration of UAVs into Unmanned Traffic Management (UTM) systems.

Regulatory Compliance: By strictly modeling temporal NFZs and heterogeneous vehicle profiles, it aligns with real-world aviation regulations (e.g., EASA U-Space).
Operational Feasibility: It demonstrates that high-density urban drone delivery is computationally feasible, overcoming the "curse of dimensionality" that plagues existing MAPF solvers.
Future Impact: The framework lays the groundwork for automated, conflict-free air traffic management in smart cities, moving beyond theoretical benchmarks to realistic, large-scale deployments. The code is released as an open-source project to encourage reproducibility and further research.