Source-linked AI summary
Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
Tobias Stollenwerk, Bryan O'Gorman, Davide Venturelli, Salvatore Mandrà, Olga Rodionova, Hok K. Ng, Banavar Sridhar, Eleanor G. Rieffel, Rupak Biswas
TL;DR
The paper addresses conflicts among wind-optimal flight trajectories, which can arise when routes exploit favorable winds. It maps a simplified delay-only conflict-resolution problem to QUBO and evaluates its hardness, discretization, and feasibility on quantum annealers; the reported results identify limits associated with problem size and modeling choices.
Problem
Wind-optimal routes can conflict, so their trajectories must be modified to avoid conflicts between flights.
Source: §I · p. 1, §II · p. 2Method
The paper maps a simplified, departure-delay-only conflict-resolution problem to QUBO and uses conflict-graph structure to identify smaller instances.
Source: §I · p. 1, §III · p. 3Results
Conflict-free solutions are already hard to find for flight sets involving more than 12 flights; larger delay bounds increase hardness, while finer discretization improves solution quality but decreases D-Wave 2X success probability.
Source: §I · pp. 1–2, §VII · p. 10Takeaways & Limitations
The preprocessing algorithm is general and can be applied to existing conflict-resolution methods to improve solution speed and quality.
Source: §VII · p. 10The study restricts its main analysis to time delays, an unrealistic simplification that must be extended to include practically relevant aspects.
Source: §VII · p. 9
Abstract
from arXiv · showhide
We present the mapping of a class of simplified air traffic management (ATM) problems (strategic conflict resolution) to quadratic unconstrained boolean optimization (QUBO) problems. The mapping is performed through an original representation of the conflict-resolution problem in terms of a conflict graph, where nodes of the graph represent flights and edges represent a potential conflict between flights. The representation allows a natural decomposition of a real world instance related to wind-optimal trajectories over the Atlantic ocean into smaller subproblems, that can be discretized and are amenable to be programmed in quantum annealers. In the study, we tested the new programming techniques and we benchmark the hardness of the instances using both classical solvers and the D-Wave 2X and D-Wave 2000Q quantum chip. The preliminary results show that for reasonable modeling choices the most challenging subproblems which are programmable in the current devices are solved to optimality with 99% of probability within a second of annealing time.
I. INTRODUCTION
The paper studies resolving conflicts among wind-optimal flights and maps a simplified, departure-delay-only version of the problem to QUBO. It examines instance hardness, discretization, and quantum-annealer feasibility, while specifying how conflicts and delay objectives are represented.
I. INTRODUCTION
- Wind-optimal trajectories minimize fuel costs in the presence of forecast winds, but exploiting favorable winds makes these routes likely to conflict.Rising air traffic and a saturated air-traffic network motivate exploring such routes and their deconfliction.Source: §I · p. 1
- The paper maps conflict resolution for wind-optimal trajectories to QUBO, using departure delays alone and tunable discretization to trade solution quality against computational effort.The main analysis neglects maneuvers and examines problem structure beyond quantum annealing.Source: §I · p. 1
- Problems are hard in general and become harder as the maximum allowed departure delay increases.The study extracts natural subsets from wind-optimal trajectories to analyze this hardness.Source: §I · p. 1
- Finer discretization increases solution quality, while a sufficiently large maximum departure delay is enough for an acceptable solution.The discretization’s effect on solution quality is examined using classical solvers.Source: §I · p. 1
- The sufficient penalty weights for hard constraints were found to be largely independent of the problem instances.Source: §I · p. 2
- Larger problem sizes and finer discretizations decrease D-Wave 2X success probability because of the machine’s limited precision.The study embedded and ran smaller problem instances.Source: §I · p. 2
II. PROBLEM SPECIFICATION
- A conflict cluster groups trajectory-point conflicts between the same two flights when all intermediate points also conflict, allowing one constraint to address the cluster.Figure 1 illustrates potential conflicts and the cluster criterion.Source: §II · p. 2, Figure 1 · p. 3
- The simplified problem permits only departure delays and minimizes unweighted total arrival delay across flights, leaving maneuver choices for future work.The underlying task modifies wind-optimal trajectories to avoid conflicts between flights.Source: §II · pp. 2–3
III. INSTANCES
The conflict graph decomposes the transatlantic flight instance into connected components, most of which are small at a 60-minute maximum delay. Component treewidth grows approximately linearly with component size, and its slope increases with the maximum delay, indicating harder instances.
III. INSTANCES
- The analysis uses 984 transatlantic flights from July 29, 2012, each at constant cruising altitude and speed.The authors note that their methods can generalize beyond these properties.Source: §III · p. 3
- At dmax = 60 minutes, approximately 75% of connected components contain no more than 10 flights.The conflict graph grows denser as dmax increases and eventually saturates.Source: §III · p. 3, Figure 3 · p. 4
- For dmax = 60, conflict-graph vertex degrees approximately follow a power law, and the exponent decreases as dmax increases.The flatter degree distribution at larger delays corresponds to trajectory structure mattering less.Source: §III · p. 4, Figure 4 · p. 4, Figure 5 · p. 4
- Treewidth scales approximately linearly with component size, and the slope increases with maximum delay, indicating that larger-delay instances are harder.The linear fit represents components with more than 50 flights.Source: §III · p. 4, Figure 6 · p. 5, Figure 7 · p. 5
IV. DISCRETIZING THE CONFIGURATION SPACE
The section examines how discretizing and bounding departure delays affects solution quality and the size of the optimization space. Finer discretization improves solutions, while moderate delay bounds often suffice; larger connected components also challenge the classical solver used for these instances.
IV. DISCRETIZING THE CONFIGURATION SPACE
- Encoding departure delays with resolution ∆d and maximum dmax limits the configuration space; the study compares restricted optima with the continuous, unbounded-delay problem.The discretization determines the available delay choices, and larger configuration spaces require more qubits.Source: §IV · p. 5
- The largest I60 instance had 257 flights and 4,068 potential conflicts; ICM results for the studied instance sizes were judged globally optimal with exceedingly high probability.ICM is a classical heuristic and is not guaranteed to return the global optimum in general.Source: §IV · p. 5
- For I18, all investigated instances but one needed a maximum delay threshold d0_max ≤ 6 minutes; finer discretization improved solution quality.For the 19-flight, 47-conflict instance, total delay was nearly independent of the maximum delay except at dmax = 3.Source: §IV · pp. 5–6, Figure 8 · p. 5
- For I60 instances with a 60-minute maximum delay, total optimized delay decreased as ∆d decreased; 17 of 26 instances had zero delay at every tested resolution.The color coding in Fig. 9 counts instances with the same total delay.Source: §IV · p. 6, Figure 9 · p. 6
- ICM could not optimize connected components with more than 12 flights, as larger components increasingly resembled fully connected graphs rather than trees.ICM performs best on almost-planar problems, and its performance quickly decreases for fully connected ones.Source: §IV · p. 6
V. MAPPING TO QUBO
The section maps the departure-delay-only conflict-resolution model to QUBO, with a more general mapping provided in the appendix.
V. MAPPING TO QUBO
- The main-text QUBO mapping covers conflict resolution limited to departure delays; the appendix gives a more general mapping.Source: §V · p. 6
A. Binary encoding
The binary encoding represents each flight’s discretized departure delay with one-hot variables. Penalty terms enforce the encoding and penalize conflicts in the QUBO cost.
A. Binary encoding
- Each flight’s departure delay is represented by Nd + 1 binary variables in a one-hot encoding.Source: A. Binary encoding · p. 6
- A penalty function with sufficiently large λencoding makes cost-minimizing states satisfy the delay encoding constraint.Source: A. Binary encoding · p. 6
- The QUBO cost includes the total delay contribution and a penalty for actualized conflicts.Source: A. Binary encoding · p. 6
B. Softening the constraints
The section examines penalty weights for enforcing QUBO constraints and then describes quantum annealing and its hardware embedding requirements. The D-Wave 2X experiments use restricted delay settings, while practical annealing may return approximate rather than ground states.
B. Softening the constraints
- For instances up to 7 flights and 9 conflicts, the valid penalty-weight region had a box-like boundary, suggesting the conflict and encoding weights were independent.The figure’s example uses a Max-SAT solver to find exact solutions for the QUBO-derived instances.Source: B. Softening the constraints · p. 7, Figure 11 · p. 7
VI. QUANTUM ANNEALING
- The D-Wave 2X study restricted instances to dmax = Dmax = 18 and ∆d ∈ {3, 6, 9}.Source: §VI · p. 7
A. Background
- Quantum annealing aims for a problem Hamiltonian’s ground state, but noise and other factors mean it may only approximately minimize the function; embedding maps problem variables to connected qubit sets.A hardware graph may not contain the problem graph directly, so graph-minor embedding uses qubit sets and intra-logical couplings.Source: A. Background · p. 7
B. Embedding
The QUBO instances require minor embedding to fit the D-Wave Chimera connectivity, increasing the number of binary variables. The authors used heuristic embeddings and selected the one with the fewest physical qubits for each instance.
B. Embedding
- Minor embedding maps QUBOs onto the Chimera architecture, increasing the number of binary variables.The instances' graph structures were not directly suitable for calculation on the D-Wave machine.Source: B. Embedding · p. 7
- Heuristic embeddings were generated for instances up to Nf = 50 and Nc = 104 on D-Wave 2X and Nf = 64 and Nc = 261 on D-Wave 2000Q, depending on discretization.For each instance, up to five embeddings were generated and the one using the fewest physical qubits was selected.Source: B. Embedding · pp. 7–8
- Figure 12 relates physical-qubit counts to logical-qubit counts for the I18 QUBO instances embedded on D-Wave 2000Q.Source: Figure 12 · p. 8
C. Success Probability
The authors evaluated annealing success against an exact solver using time to solution at 99% probability. Success depends on instance size and discretization, as well as the ferromagnetic coupling used in embedding; tuning that coupling improves performance, while limited hardware precision constrains larger and finer instances.
C. Success Probability
- Success probability decreases for larger instances and finer discretizations, with limited QUBO specification precision proposed as the main cause.Time-to-solution at 99% probability was used as the runtime measure, and annealing time was set to 20 µs.Source: C. Success Probability · p. 8
- Figure 13 reports median T99 across flight and conflict counts, while Figure 15 compares fixed and optimal JF couplings.The figures use percentile error bars; Figure 13 compares D-Wave 2X and 2000Q, and Figure 15 reports results for optimal JF.Source: Figure 13 · p. 8, C. Success Probability · pp. 8–9, Figure 15 · p. 9
- The success probability depends on the intra-logical-qubit coupling JF: weak coupling can break qubit chains, while strong coupling can exceed machine precision.An intermediate optimal Jopt_F maximizes success probability; the authors swept JF from −1.25 to −0.125 in units of the largest embedded-Ising coefficient.Source: C. Success Probability · p. 8
- Success probability falls as the maximum coefficient ratio Cmax rises, vanishing around Cmax ≈ 30, near the D-Wave 2000Q precision of about 1/30.The authors relate this to longer time-to-solutions for larger instances and finer discretizations.Source: C. Success Probability · p. 9
VII. CONCLUSIONS
The paper maps a simplified wind-optimal-trajectory conflict-resolution problem to a QUBO and introduces preprocessing to reduce potential conflicts. Its conclusions emphasize the difficulty of larger delay-only instances, the hardware limits on the studied models, and the need to extend the formulation for practical relevance.
VII. CONCLUSIONS
- Restricting the problem to time delays is explicitly described as unrealistic; practical relevance requires adding all practically relevant aspects to the QUBO.The simplification is presented as a proof of principle that enables runs on existing annealers at a reasonable scale.Source: §VII · p. 9
- The proposed QUBO mapping simplifies conflict resolution to minimum trajectory modifications, with departure delays as the optimized variables for transatlantic wind-optimal trajectories.The study used actual North Atlantic trajectories from July 29, 2012; the method may potentially include other maneuvers.Source: §VII · pp. 9–10
- Preprocessing removes conflicts that cannot occur under a maximum delay and clusters adjacent conflicts, reducing potential conflicts while revealing conflict-graph topology.The authors state that it can be applied to existing conflict-resolution methods to improve solution speed and quality.Source: §VII · p. 10
- Larger problem sizes and finer discretizations suppress success probability because of D-Wave's limited precision; the study focused on excluding maneuvers to keep variables few.Source: §VII · p. 10
- Finding conflict-free solutions is already hard for flight sets involving more than 12 flights when only departure delays are allowed.The performance analysis covered classical and quantum heuristics on this QUBO model.Source: §VII · p. 10
APPENDIX
The appendix presents a more general deconfliction mapping and discusses finite-set variable encodings. One-hot encoding is used in the described mappings, while unary and binary alternatives trade qubit use and precision against modeling constraints.
APPENDIX
- The appendix describes a mapping to QUBO for a more general deconflicting problem than the main text covers.Source: APPENDIX · p. 10
A. Alternative encodings
- One-hot encoding represents a variable over a finite set with one bit per value and requires exactly one bit to be one.The mappings in the main text and appendix use this encoding.Source: A. Alternative encodings · p. 10
- Binary encoding uses fewer qubits than one-hot encoding but requires greater precision; unary encoding can require minimal precision but cannot express some quadratic pairwise constraints without ancillary bits.The appendix recommends unary encoding when variables appear only in a sum of bits.Source: A. Alternative encodings · p. 10
- The generalized encoding penalty function enforces exactly one active bit for each set of bits Xi.Source: A. Alternative encodings · p. 10
B. Global trajectory modifications
Global trajectory modifications represent each flight’s departure delay and spatial transformation with finite-valued QUBO variables. The formulation computes pairwise conflict assignments and combines encoding, consistency, delay, and conflict costs.
B. Global trajectory modifications
- Each flight’s departure delay and spatial-transformation parameter must take values from finite sets represented by indicator QUBO variables.The indicators encode whether each variable equals a particular allowed value.Source: B. Global trajectory modifications · pp. 10–11
- For every flight pair, the method computes in polynomial time the delay and transformation assignments that produce a conflict.The assignments that produce conflicts form the set B_i,j.Source: B. Global trajectory modifications · p. 11
- The objective combines encoding, consistency, delay, and conflict terms, with consistency enforced among single-flight and pairwise delay indicators.A nonnegative penalty is zero if and only if z=xy; the total cost is minimized.Source: B. Global trajectory modifications · p. 11
C. Local trajectory modifications
Local trajectory modifications offer several QUBO-mapped ways to resolve conflicts through changes near conflicts or delays accumulated between them. The section describes selected models and leaves a full accounting for future work.
C. Local trajectory modifications
- The section describes selected local-modification models and leaves a full accounting of possible mappings for future work.The modifications are made near conflicts, unlike global trajectory modifications.Source: C. Local trajectory modifications · p. 11
1) Exclusive avoidance
- Exclusive avoidance assigns each conflict to one flight’s trajectory change using one bit per conflict, assuming those changes create no new potential conflicts.The assumption can be partially relaxed by adding penalty terms for interactions between modifications.Source: 1) Exclusive avoidance · p. 11
2) Flexible avoidance
- Flexible avoidance permits passive resolution when flights are already relatively delayed and combines encoding, delay, consistency, and conflict costs.The difference in accumulated delays at a conflict is represented with indicator bits.Source: 2) Flexible avoidance · p. 11
3) Interstitial delays
- Interstitial delays are variables inserted between successive conflicts, encoded with bits, so conflicts are avoided through accumulated delays.Each delay is introduced after the previous conflict and before reaching the next one.Source: 3) Interstitial delays · pp. 11–12