Optimizing aircraft path planning

Patent metadata

Field	Value
Publication number	US-2020380877-A1
Application number	US-201916720906-A
Country	US
Kind code	A1
Filing date	Dec 19, 2019
Priority date	May 28, 2019
Publication date	Dec 3, 2020
Grant date	—

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.

First claim

1 . A quantum-computing aircraft path planning system, the system comprising a classical computing system and a quantum computing system communicatively coupled to one another, the classical computing system configured to:
receive state data from a plurality of aircraft, the state data specifying position data and heading data for each of the plurality of aircraft; generate one or more respective first groups of mutually exclusive maneuverability options for each of the plurality of aircraft; and the quantum computing system configured to generate a first solution representing, for each of the one or more respective first groups of mutually exclusive maneuverability options for each of the plurality of aircraft, a respective lowest-cost first maneuverability option for the respective aircraft.

2 . The system of claim 1 , wherein the classical computing system is configured to:
calculate, based on the state data, a first respective distance to a target for each of the plurality of aircraft; and calculate, based on the state data, a first respective inter-aircraft repulsion for each of the plurality of aircraft, wherein the one or more respective first groups of mutually exclusive maneuverability options are generated based on the first respective distance to the target for each of the plurality of aircraft and based on the first respective inter-aircraft repulsion for each of the plurality of aircraft.

3 . The system of claim 2 , wherein:
the classical computing system is configured to:
calculate, based at least in part on the respective lowest-cost first maneuverability option for each of the plurality of aircraft, a second respective distance to target for each of the plurality of aircraft and a second respective inter-craft repulsion for each of the plurality of aircraft, wherein the second respective distances to target and second respective inter-craft repulsions represent a subsequent time-step with respect to the first respective distance to target and first respective inter-craft repulsion; and
generate one or more respective second groups of mutually exclusive maneuverability options for each of the plurality of respective aircraft, wherein the one or more respective second groups of mutually exclusive maneuverability options are generated based on the second respective distance to the target for each of the plurality of aircraft and based on the second respective inter-aircraft repulsion for each of the plurality of aircraft; and
the quantum computing system is configured to generate a second solution representing, for each of the one or more respective second groups of mutually exclusive maneuverability options for each of the plurality of aircraft, a respective lowest-cost second maneuverability option for the respective aircraft.

4 . The system of claim 1 , wherein the one or more respective first groups of mutually exclusive maneuverability options include data representing a quadratic unconstrained binary optimization, the data representing the quadratic unconstrained binary optimization including a plurality of matrices.

5 . The system of claim 4 , wherein the data representing the quadratic unconstrained binary optimization comprises a plurality of total distances-to-target.

6 . The system of claim 5 , wherein each of the plurality of total distances-to-target is equal to a sum of a distance-to-target for each of the plurality of aircraft for a given group of mutually exclusive qubits.

7 . The system of claim 4 , wherein the data representing the quadratic unconstrained binary optimization comprises a plurality of total intercraft-repulsion costs.

8 . The system of claim 7 , wherein each of the plurality of total intercraft-repulsion costs is equal to a sum of an intercraft repulsion cost for each of the plurality of aircraft for a given group of mutually exclusive qubits.

9 . The system of claim 1 , wherein the path planning system is configured to transmit a control signal, from a control system to one or more of the plurality of aircraft, the control signal comprising instructions for navigation of the one or more of the plurality of aircraft based on the first solution.

10 . The system of claim 1 , wherein the classical computing system is configured to transmit the one or more groups of mutually exclusive maneuverability options to the quantum computing system, and
the quantum computing system is configured to transmit the generated solution to the classical computing system.

11 . The system of claim 1 , wherein the one or more respective first groups of maneuverability options represent one or more of: a change in direction, a change in speed, and a change in altitude.

12 . The system of claim 1 , wherein the generating the one or more respective first groups of maneuverability options comprises:
determining a zone for the respective aircraft based on the state data; and generating the one or more groups of respective first maneuverability options in accordance with one or more maneuverability option constraints applicable to the determined zone.

13 . A method for optimizing aircraft control, the method comprising:
communicatively coupling a classing computing system and a quantum computing system to one another;
at the classical computing system:
receiving state data from a plurality of aircraft, the state data specifying position data and heading data for each of the plurality of aircraft;
generating one or more respective first groups of mutually exclusive maneuverability options for each of the plurality of aircraft;

at the quantum computing system, generating a first solution representing, for each of the one or more respective first groups of mutually exclusive maneuverability options for each of the plurality of aircraft, a respective lowest-cost first maneuverability option for the respective aircraft.

14 . The method of claim 13 , further comprising:
at the classical computing system:
calculating, based on the state data, a first respective distance to a target for each of the plurality of aircraft; and
calculating, based on the state data, a first respective an inter-aircraft repulsion for each of the plurality of aircraft,
wherein the one or more respective first groups of mutually exclusive maneuverability options are generated based on the first respective distance to the target for each of the plurality of aircraft and based on the first respective inter-aircraft repulsion for each of the plurality of aircraft.

15 . The method of claim 14 , further comprising:
at the classical computing system:
calculating, based at least in part on the respective lowest-cost first maneuverability option for each of the plurality of aircraft, a second respective distance to target for each of the plurality of aircraft and a second respective inter-craft repulsion for each of the plurality of aircraft, wherein the second respective distances to target and second respective inter-craft repulsions represent a subsequent time-step with respect to the first respective distance to target and first respective inter-craft repulsion; and
generating one or more respective second groups of mutually exclusive maneuverability options for each of the plurality of respective aircraft, wherein the one or more respective second groups of mutually exclusive maneuverability options are generated based on the second respective distance to the target for each of the plurality of aircraft and based on the second respective inter-aircraft repulsion for each of the plurality of aircraft; and
at the quantum computing system, generating a second solution representing, for e

Assignees

• Noblis Inc

Inventors

• James Scott

Classifications

• G08G5/727

  from a ground station · CPC title

• G08G5/76

  for monitoring atmospheric conditions · CPC title

• G08G5/22

  located on the ground · CPC title

• G08G5/56

  for two or more aircraft · CPC title

• G08G5/32 Primary

  for flight plan preparation · CPC title