Optimizing aircraft path planning

Inventors

James, Scott

Abstract

Disclosed herein are systems and methods for optimizing air traffic control managing using a Quantum Annealing-based iterative path planning technique and algorithm that involves both classical and quantum computation components. The classical component can calculate the distances between aircraft and the target destination from a set of new, possible properties, such as aircraft location. The quantum component can select from the new, possible properties to minimize the distance of the aircraft to the target destination while ensuring adequate separation between aircraft. The algorithm can utilize qubits to represent maneuverability options for aircraft. The maneuverability options may be partitioned into a set of multiple qubits per aircraft. Each set may include a plurality of qubits that are representative of the sub options. The algorithm can utilize Quadratic Unconstrained Boolean Optimization (QUBO) to find the lowest cost-energy maneuverability option.

Core Innovation

The invention is a quantum-computing aircraft path planning system for air traffic control that couples a classical computing system with a quantum computing system. The classical computing system receives state data from a plurality of aircraft, the state data specifying position data and heading data for each aircraft, and generates one or more respective first groups of mutually exclusive maneuverability options for each aircraft.

The system partitions a plurality of qubits of the quantum computing system between the plurality of aircraft according to the one or more respective first groups of mutually exclusive maneuverability options for each aircraft. Each qubit partitioned to an aircraft represents a maneuverability option in the corresponding mutually exclusive maneuverability option group, and the quantum computing system generates a first solution that selects a respective lowest-cost first maneuverability option for each respective mutually exclusive maneuverability option group.

In an iterative manner, the optimization updates by computing subsequent time-step distances to target and inter-aircraft repulsion based on a previously selected lowest-cost maneuverability option, generating respective subsequent mutually exclusive maneuverability option groups, and having the quantum computing system generate a second solution selecting respective lowest-cost maneuverability options for the subsequent time-step. The quantum optimization uses a QUBO formulation that minimizes a cost corresponding to distance-to-target and inter-aircraft repulsion while enforcing mutually exclusive maneuverability options through qubit semantics and qubit exclusivity.

Claims Coverage

The independent claims cover a quantum-computing aircraft path planning system, a method, and a non-transitory computer-readable storage medium that use hybrid classical/quantum computation to select, for each aircraft, a lowest-cost maneuverability option from mutually exclusive option groups. Across the independent claims, the inventive features include state-based generation of mutually exclusive maneuverability option groups, qubit partitioning per aircraft to represent maneuverability options, and quantum generation of a lowest-cost solution for each option group.

The key claim coverage is the hybrid approach: classical computation uses aircraft position and heading state data to form mutually exclusive maneuverability option groups, qubits are partitioned so each aircraft’s option group is represented in the quantum system, and the quantum computing system outputs a lowest-cost maneuverability option for each aircraft within each mutually exclusive group.

Stated Advantages

Documented Applications

No documented applications found