🤖 AI

Declarative Problem Solving in UAM Strategic Deconfliction

This paper proposes an Answer Set Programming (ASP) approach for strategic deconfliction in Urban Air Mobility, demonstrating through benchmarking against Constraint Programming that ASP offers superior execution speed and scalability for small to medium-sized flight planning scenarios.

Original authors: Gioacchino Sterlicchio, Angelo Oddi, Riccardo Rasconi, Francesca Alessandra Lisi

Published 2026-07-24

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Gioacchino Sterlicchio, Angelo Oddi, Riccardo Rasconi, Francesca Alessandra Lisi

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 the sky above our cities is about to get a lot busier. Instead of just a few airplanes and helicopters, we are looking at a future filled with thousands of electric flying vehicles—like giant drones and air taxis—zipping between skyscrapers to deliver packages or take people to work. This is called Urban Air Mobility (UAM). The big problem? If everyone flies whenever they want, they will crash into each other or get stuck in a massive aerial traffic jam. To fix this, scientists need a way to plan everyone's flight paths before they even take off. This is called "strategic deconfliction," which is just a fancy way of saying "making sure no two flying things try to be in the same spot at the same time." To solve this, researchers use special computer languages that act like super-smart puzzle solvers. One type of solver is called "Constraint Programming" (CP), which is like a very strict librarian who checks every single rule before letting a book out. Another type is "Answer Set Programming" (ASP), which is more like a creative architect who quickly sketches out many possible blueprints and picks the best one that fits all the safety rules.

This paper introduces a new system called STRADA, which uses that creative architect approach (ASP) to solve the UAM traffic puzzle. The authors, a team of researchers from Italy, wanted to see if this creative approach could handle the chaos of a busy city sky better than the strict librarian approach (CP). They built a digital model of the sky using "lanes" (like invisible highways in the air) and simulated thousands of flying vehicles trying to move through them. They tested their system by making the number of vehicles grow and by making the time windows for takeoff wider or narrower.

The results were a bit like a race between a sprinter and a marathon runner. When the number of flying vehicles was small or medium (up to about 300), the ASP system (STRADA) was incredibly fast, finding safe flight plans in seconds. It was much quicker than the CP system, which took a long time to find even a single solution. However, the ASP system had a catch: it used a lot of computer memory. When the team tried to simulate a very crowded sky with 5,000 vehicles or very wide takeoff windows, the ASP system ran out of memory and crashed, like a brain trying to hold too many thoughts at once. The CP system, on the other hand, was slower but much better at managing its memory; it didn't crash as easily, even though it took forever to finish the work.

In short, the paper suggests that for small to medium-sized city skies, the creative ASP approach is the winner because it is fast and efficient. But if the sky gets too crowded or the planning rules get too loose, the system hits a wall. The authors conclude that while their new method is a great first step for managing future air traffic, they need to find ways to make it handle even bigger crowds without running out of memory. They also plan to test their ideas on real-world data and different computer systems to see if it holds up in the real world.

Technical Summary: Declarative Problem Solving in UAM Strategic Deconfliction

Problem Definition

The paper addresses Urban Air Mobility (UAM) Strategic Deconfliction (SD), a critical layer of Air Traffic Management focused on pre-flight planning. As the demand for aerial vehicles (drones, air taxis, eVTOLs) increases in densely populated areas, the risk of mid-air collisions and conflicts with existing traffic rises. The core problem is to generate a set of scheduled flight paths such that no two aircraft violate a specified safety distance or headway ( $h$ ) in either time or space.

The problem is formalized as a couple $(N, F)$ , where $N$ is a directed graph representing the airspace network (nodes as entry/exit points or waypoints, edges as one-way corridors) and $F$ is the set of flights to be scheduled. Each flight $f_i$ is defined by its route (an acyclic sub-graph), start/end nodes, speed, and a requested launch time interval $[e_i, l_i]$ . The objective is to assign a specific route and a departure time for each flight such that:

Flights depart within their requested intervals.
Flights sharing a starting node have distinct departure times separated by at least $h$ .
Flights occupying the same node or lane at any point maintain a safe temporal separation of at least $h$ .
The total delay (difference between actual launch time and earliest requested time) is minimized.

Methodology

The authors propose STRADA (Scalable Trajectory Resolution Architecture for Deconfliction using ASP), a framework based on Answer Set Programming (ASP). This approach contrasts with traditional numerical methods and existing Constraint Programming (CP) encodings.

1. Modeling Approach

STRADA models the SD problem using a lane-based airspace structure where lanes are directed graphs. The framework supports two variations:

Constant Speed: All flights maintain a fixed speed across all lanes.
Variable Speed: Speeds can be adjusted per lane to account for obstacles or weather, requiring a modification to the speed predicate in the encoding.

The ASP encoding (implemented using the clingo solver) utilizes:

Facts: To define the network topology (nodes, edges, lengths), headway constraints, and flight specifications (routes, speeds, time windows).
Rules: To compute the Estimated Time of Arrival (ETA) for flights traversing lanes based on distance and speed.
Integrity Constraints: To eliminate invalid answer sets where safety constraints are violated (e.g., two flights at the same node with insufficient time separation, or two flights on the same lane crossing paths).
Optimization: A #minimize directive is used to minimize the sum of delays across all flights.

2. Comparative Baseline

The ASP approach is benchmarked against a Constraint Programming (CP) encoding (solved using Minizinc/Gecode). CP defines the problem via variables, domains, and constraints, aiming to find a solution that satisfies all conditions.

Key Contributions

The paper makes three primary contributions:

ASP Formalization: It provides the first logic-based formalization of the UAM Strategic Deconfliction problem, defining the necessary conditions for conflict-free trajectory planning.
STRADA Framework: It introduces a complete framework that models the air network topology, the drone fleet, and the SD encoding, capable of handling both constant and variable speed scenarios.
Empirical Evaluation: It presents a comprehensive scalability analysis comparing STRADA (ASP) against CP across varying flight volumes, launch interval sizes, and network topologies (Intracity, Intercity, Airport Shuttle, and synthetic grids).

Experimental Results

Experiments were conducted on a laptop (AMD Ryzen 5, 8GB RAM) with a 900-second timeout. The study varied the number of flights (15–400), launch intervals (5–50 minutes), and network sizes (3x3 to 5x5 grids).

Execution Time vs. Scalability:
- ASP (STRADA): Demonstrates superior execution speed for small to medium problem sizes (e.g., fewer flights, narrower intervals). However, it struggles with scalability as complexity increases. For high flight counts (300+) or large launch intervals, ASP frequently hits the time limit or exhausts memory (Out-of-Memory errors), exhibiting a "combinatorial explosion" during the grounding phase.
- CP: Generally requires significantly more execution time than ASP, often failing to find optimal solutions within the time limit for even moderate problem sizes. However, CP demonstrates more stable and efficient memory usage across varying problem sizes, rarely hitting memory limits where ASP fails.
Network Topology Impact:
- Execution time for ASP grows linearly with the number of flights but increases non-linearly with network size due to the generation of more atoms and rules.
- A critical threshold was observed in the 5x5 grid with 5,000 flights, where memory usage spiked from ~80 MB to 7.10 GB, indicating the current model's limits for high-density scenarios.

Significance and Claims

The paper claims to introduce the first ASP-based formulation for UAM Strategic Deconfliction. The authors highlight three key advantages of their approach:

Simplified and Readable Modeling: The declarative nature of ASP allows for concise representation of complex constraints.
Support for Complex Optimization: ASP effectively handles the combinatorial nature of trajectory planning.
Adaptability: The framework can accommodate changes in specifications (e.g., variable speeds) without major reprogramming.

The study concludes that while ASP offers faster execution for smaller, real-time strategic deconfliction tasks, its scalability is currently limited by memory constraints in high-density scenarios. Conversely, CP offers better memory stability but suffers from poor time performance. The authors note that the current experimental parameters align with contemporary UAM benchmarks but suggest that future work must validate the model against real-world datasets and explore cross-platform solver performance to fully assess scalability in high-density urban environments.