🤖 AI

Solution space path planning for supporting en-route air traffic control

This paper presents a computationally efficient and interpretable solution-space path-planning algorithm for en-route air traffic control that integrates multiple conflict detection methods with human-centric design principles to generate conflict-free paths in milliseconds while accommodating operational constraints and shifting optimization goals.

Original authors: Yiyuan Zou, Wenying Lyu, Clark Borst

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yiyuan Zou, Wenying Lyu, Clark Borst

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 Europe is a giant, busy highway, but instead of cars, it's filled with airplanes. The people in charge of keeping everyone safe and moving smoothly are Air Traffic Controllers (ATCos). Their job is incredibly hard: they have to make sure no two planes crash into each other, all while keeping the traffic flowing efficiently.

For a long time, computers have tried to help controllers by automatically plotting new paths for planes when they get too close. But here's the problem: these computer programs often act like "black boxes." They spit out a solution, but the controller doesn't understand how the computer got there, or why it chose that specific route. Because they don't trust the "magic," controllers often ignore the computer's help and do the work themselves.

This paper introduces a new way to help controllers called Solution Space Path Planning (SSPP). Think of it not as a robot that takes over the steering wheel, but as a super-smart co-pilot that draws a map of all the safe places a plane can go right now.

The Core Idea: The "Safe Zone" Map

Imagine you are walking through a crowded room. You want to get to the door, but people are moving around.

Old Way: A computer tells you, "Turn left 30 degrees and walk 5 steps." You do it, but you don't know if there's a better way or why that was the only choice.
The SSPP Way: The computer draws a glowing green circle around you showing every single spot you can step to without bumping into anyone. It highlights the "no-go" zones in red (where people are) and the "go" zones in green. You can then pick the path that feels right, knowing you have a clear view of all your options.

The goal of this paper is to make that "green circle" appear instantly, even when there are dozens of planes moving at once.

How They Made It Fast (The "Shadow" Trick)

Calculating where it's safe to fly is like trying to see if a path is blocked by a wall.

The Slow Way: You check every single step one by one to see if a wall is in the way. This takes forever.
The SSPP Way: The researchers used a clever trick called Shadowcasting. Imagine standing in a dark room with a flashlight. The light hits the walls and casts shadows behind the furniture. The computer does this digitally: it calculates the "shadows" cast by other planes and obstacles. If a spot is in the "shadow" of a conflict, it's unsafe. If it's in the light, it's safe. This allows the computer to instantly know which areas are reachable without checking every single point individually.

Three Ways to Spot Danger

To figure out where the "shadows" (conflicts) are, the team tested three different methods:

The Ruler Method (Distance-based): Measures the exact distance between planes. It's very accurate but takes a lot of math to calculate for every pair of planes.
The Calendar Method (Time-interval-based): Checks if two planes will be in the same spot at the same time. It's good for busy traffic but can be a bit too cautious, blocking off safe paths unnecessarily.
The "Conflict Zone" Method (Zone-based): This is the paper's big innovation. Instead of checking point-by-point, it draws a "danger zone" around a crossing plane (like a moving bubble). If your path enters that bubble, you're in trouble. This method is the fastest because it lets the "Shadowcasting" trick work perfectly, quickly identifying safe paths.

Two Types of Pathfinders

The researchers built two versions of their algorithm:

SSPPV (The Sprinter): This version looks at individual points (like stepping stones). It is incredibly fast—calculating a new path in about 3.7 milliseconds (faster than a human blink). It's perfect for the split-second decisions controllers need during a busy shift.
SSPPE (The Marathon Runner): This version looks at pairs of points (like the path between two stones). It explores more possibilities and finds slightly better paths in complex situations, but it takes longer to compute.

The Results

When they tested these tools in a simulation of the busy airspace over the Netherlands (Maastricht Upper Area Control Centre):

Speed: The "Sprinter" (SSPPV) using the "Conflict Zone" method was the winner. It found safe paths in under 4 milliseconds, which is fast enough for real-time use.
Accuracy: It successfully found safe paths for planes in almost every scenario (98.5% success rate), even when there were many planes and obstacles.
Flexibility: The system can be tuned. If a controller wants the absolute fastest route, the computer finds it. If they want to keep planes further apart for extra safety, the computer can adjust to prioritize distance over speed.

Why This Matters

The paper argues that for automation to work in the sky, it needs to be transparent. Controllers need to see the "why" behind the suggestion. By using this "Solution Space" approach, the computer doesn't just give an answer; it shows the whole landscape of safe options.

The main takeaway is that by combining a visual way of thinking (the solution space) with a very fast way of calculating (shadowcasting and conflict zones), we can build tools that controllers will actually trust and use, making the skies safer and more efficient without taking the human out of the loop.

Technical Summary: Solution Space Path Planning for Supporting En-Route Air Traffic Control

Problem Statement
Despite advancements in Air Traffic Management (ATM) automation, the operational adoption of path-planning algorithms in tactical Air Traffic Control (ATC) remains limited. A primary barrier is the misalignment between algorithmic design priorities (often focusing on pure optimality) and the needs of Air Traffic Controllers (ATCos), who require solutions that are interpretable, operationally compliant, and computationally efficient. Existing tools, such as Solution Space Diagrams (SSD) or Travel Space Representations (TSR), offer high interpretability but often restrict the solution space to simplified representations (e.g., single intermediate waypoints), potentially missing optimal paths. Conversely, advanced path-planning algorithms (e.g., A*, SIPP, TO-AA-SIPP) often lack transparency ("black-box" nature) or fail to incorporate specific ATC constraints like turning angle limits and procedural routing rules. This paper addresses the challenge of designing a decision-support algorithm that balances interpretability, computational efficiency, operational compliance, and solution optimality for en-route conflict-free path planning.

Methodology
The study proposes Solution Space Path Planning (SSPP), an algorithm that structures the search process around a human-interpretable solution space. The core philosophy is to explicitly represent and efficiently explore the set of all feasible, conflict-free actions.

Solution Space Generation:
At each search step, the algorithm generates a "solution space" representing all reachable nodes from the current position. This process integrates several constraints:
- Static Obstacles: Visibility is determined using a recursive shadowcasting algorithm (adapted from field-of-view concepts) rather than traditional line-of-sight, which improves efficiency by avoiding repeated examinations of nodes near obstacles.
- Dynamic Obstacles (Conflict Detection): Three distinct intent-based conflict detection methods are integrated to identify reachable nodes:
  - Distance-based: Uses the Closest Point of Approach (CPA) metric to check if the minimum separation (5 nmi) is violated.
  - Time-interval-based: Maps aircraft trajectories to grid cells with time intervals (similar to Safe Interval Path Planning, SIPP) to detect temporal overlaps.
  - Zone-based: Inspired by the Highly Interactive Problem Solver (HIPS), this method constructs "conflict zones" (static obstacles) based on velocity obstacles and flight duration. These zones are then used with shadowcasting to generate a field of view for dynamic obstacles in a single pass.
Search Variants:
Two variants of SSPP are developed based on how search nodes are defined within the A* search framework:
- SSPPV (Vertex-based): Treats each grid vertex as a node. It allows any-angle turns at vertices, generating straighter paths without post-hoc smoothing.
- SSPPE (Edge-based): Treats each pair of vertices (an edge) as a node, effectively creating a 4D search space ( $R^2 \times R^2$ ). This variant explores a larger state space to potentially find more optimal solutions by considering the incoming heading more rigorously.
Objective Function Extension:
While the baseline SSPP minimizes time delay, an extension is proposed to handle a trade-off between delay minimization and aircraft separation. A weighted cost function allows operators to balance these objectives, enhancing solution robustness.

Key Contributions

Interpretability and Operational Compliance: The SSPP framework generates "white-box" solutions that align with ATC cognitive processes. It overcomes limitations of traditional A* by producing straighter paths with fewer turns and supports multiple intermediate waypoints, adhering to constraints like turning angle limits (60°) and minimum waypoint distances.
Computational Efficiency: The integration of shadowcasting with zone-based conflict detection allows for rapid generation of solution spaces. This enables real-time "what-if" probing, a critical requirement for tactical ATC.
Algorithmic Variants: The introduction of SSPPV and SSPPE provides a trade-off between speed and search depth. SSPPV is shown to be significantly faster while maintaining competitive solution quality.
Conflict Detection Comparison: The study systematically evaluates three conflict detection methods (distance, time-interval, zone) within the SSPP framework, providing empirical data on their performance regarding speed and success rates.

Results
Experiments were conducted using a web-based simulator on the Delta sector of the Maastricht Upper Area Control Centre (MUAC) airspace, with scenarios ranging from 2 to 20 aircraft.

Performance of Conflict Detection:
- Zone-based detection demonstrated the best computational performance. When paired with SSPPV and a 5 nmi grid, it computed paths in an average of 3.69 ms.
- Distance-based detection offered the highest accuracy (99.67% success rate with 5 nmi grid) but was slower (approx. 12.53 ms for SSPPV).
- Time-interval-based detection was the most conservative, resulting in higher delays and lower success rates (dropping to ~79.93% with 20 aircraft and 5 nmi grid).
- The zone-based method was found to be approximately 3.29 times faster than the distance-based method and 2.27 times faster than the time-interval-based method under standard conditions.
Algorithm Variants (SSPPV vs. SSPPE):
- SSPPV was approximately 3.77 times faster than SSPPE while offering competitive effectiveness in minimizing delay and maintaining separation.
- SSPPE achieved slightly higher success rates in complex scenarios but incurred significantly higher computational costs (e.g., >1,400 ms in some high-density scenarios), making it less suitable for time-critical tactical operations.
- Reducing the grid size (e.g., from 5 nmi to 2.5 nmi) improved success rates but drastically increased runtime, highlighting the trade-off between resolution and speed.
Robustness Extension:
The extension balancing delay and separation showed that increasing the weight on separation successfully increased the average separation distance, though this came at the cost of increased delay and, in high-density scenarios, reduced success rates due to the "first-come-first-served" constraint.

Significance and Claims
The paper claims that SSPP offers a strong foundation for practical integration into future ATC decision-support systems. Its primary contribution lies in demonstrating how path-planning algorithms can be effectively aligned with human use and operational requirements. By combining a structured, interpretable solution space representation with controller-aligned decision logic, the approach enables fast, targeted exploration of rich solution sets. The authors assert that SSPPV, particularly when paired with zone-based conflict detection, is suitable for time-critical tactical operations and interactive real-time probing, bridging the gap between algorithmic efficiency and the need for transparent, human-centric automation in safety-critical environments. The work does not claim to replace human controllers but to provide a tool that enhances their ability to manage complexity and understand the consequences of their actions.