Conflict detection and resolution using predicted aircraft trajectories

• US 9,087,452 B2
• Filed: 05/24/2013
• Issued: 07/21/2015
• Est. Priority Date: 05/25/2012
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: del Pozo de Poza, Isabel, Vilaplana, Miguel, Valenzuela, Alfonso, Vazquez, Rafael, Rivas, Damian
• Primary Examiner(s): Jabr, Fadey
• Assistant Examiner(s): HEINLE, COURTNEY D
• Application Number:
  US13/902,632
• Publication Number:
  US 20130317733A1
• Time in Patent Office: 788 Days
• Field of Search: 701/123
• US Class Current: 1/1
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 5/0013 with a ground station
• CPC Class Codes: G08G 5/0039 Modification of a flight plan
• CPC Class Codes: G08G 5/0043 Traffic management of multiple aircrafts from the ground G08G5/003 takes precedence; data processing specially designed for resource management, e.g. scheduling or allocating time, human or machine resources G06Q10/06
• CPC Class Codes: G08G 5/0082 for monitoring traffic from a ground station radar or analogous systems specially adapted for traffic control G01S13/91
• CPC Class Codes: G08G 5/045 Navigation or guidance aids, e.g. determination of anti-collision manoeuvers radar or analogous systems specially adapted for anti-collision between aircraft G01S13/933

Abstract

A method of detecting conflicts between aircraft passing through managed airspace, and to resolving the detected conflicts strategically. The method may include obtaining intended trajectories of aircraft through the airspace and time constraints corresponding to time of arrival at specified locations, detecting conflicts in the intended trajectories, forming a set of the conflicted aircraft, calculating one or more revised trajectories for the conflicted aircraft such that the conflicts are resolved and the time constraints met, and advising the conflicted aircraft subject to revised trajectories of the revised trajectories.

Claims

1. A computer implemented method of managing airspace through which a plurality of aircraft are flying, comprising:

obtaining user-preferred aircraft intent data of the aircraft that describe unambiguously the user-preferred trajectories of the aircraft through the airspace;

obtaining time constraints for at least some of the aircraft, each time constraint comprising a user-preferred time of arrival at a common location;

calculating the corresponding user-preferred trajectories from the user-preferred aircraft intent data;

calling an initial conflict detection procedure comprising comparing the calculated user-preferred trajectories to identify a plurality of conflicts between user-preferred trajectories, and identifying a plurality of conflicted aircraft predicted to fly the conflicting trajectories;

grouping the plurality of conflicts into a conflict dependent network;

selecting resolution actions for a set of the plurality of conflicted aircraft within a given conflict dependent network from a set of joint candidate resolution strategies derived from a set of predefined joint candidate resolution patterns;

gathering all joint candidate resolution patterns for each conflict dependent network;

selecting a most equitable joint candidate resolution pattern for each conflict dependent network;

transmitting to the plurality of conflicted aircraft the most equitable joint candidate resolution pattern; and

ordering the plurality of conflicted aircraft to follow the most equitable joint candidate resolution pattern.

2. The method of claim 1, further comprising:

calling an initial avoidance procedure comprising revising the user-preferred aircraft intent data of the plurality of conflicted aircraft in a way that is configured to achieve the primary objective of resolving conflicts; and

calling a recovery procedure comprising determining if the user-preferred times of arrival are met by the revised trajectories and, if not, further revising the revised aircraft intent data of the associated aircraft in a way that is configured to achieve a secondary objective of meeting the time constraints.

3. The method of claim 2, comprising:

ordering the aircraft according to their user-preferred times of arrival, in order of increasing lateness of time of arrival;

processing each aircraft from the list in turn, the processing of each aircraft comprising;

determining if the aircraft is conflicted; and

if the aircraft is conflicted, calling the initial avoidance and recovery procedures.

4. The method of claim 3, further comprising a further conflict detection procedure and a further avoidance procedure, wherein:

the further conflict detection procedure comprises;

comparing calculated trajectories, including both the revised trajectories of aircraft subject to revised aircraft intent data and the user-preferred trajectories of the aircraft not subject to revised aircraft intent data, to identify any conflicts between trajectories; and

if conflicts are identified during the further conflict detection procedure, identifying the still-conflicted aircraft and calling the further avoidance procedure or

if conflicts are not detected during the further conflict detection procedure, continuing to call the recovery procedure; and

the further avoidance procedure comprises;

revising the user-preferred aircraft intent data of one or more still-conflicted aircraft in at least a partially random way, calculating the corresponding revised trajectories and calling a further round of the further conflict detection procedure.

5. The method of claim 4, wherein the processing of each aircraft comprises:

calling the initial avoidance procedure and revising the user-preferred aircraft intent data of the aircraft in at least a partially random way, calculating the corresponding revised trajectory from the revised aircraft intent data, and calling the further conflict detection procedure;

calling the recovery procedure and determining if the user-preferred times of arrival are met by the revised trajectories and, if not, further revising the revised aircraft intent data of the associated aircraft in a way that minimizes the difference between the revised time of arrival and the user-preferred time of arrival and calling the further conflict detection procedure.

6. The method of claim 5, wherein the further conflict detection procedure comprises:

identifying any conflicts between trajectories by comparing the revised trajectory of the aircraft currently being processed with the calculated trajectories, including both the revised trajectories of aircraft subject to revised aircraft intent data and the user-preferred trajectories of the aircraft not subject to revised aircraft intent data, of conflict-free aircraft and only the conflicted aircraft already processed.

7. The method of claim 6, the further conflict detection procedure further comprises:

an order of arrival check procedure comprising identifying order of arrival errors by comparing the revised trajectory of the aircraft currently being processed with the calculated trajectory of the preceding aircraft to identify instances where the aircraft currently being processed is predicted to arrive at the common location before the preceding aircraft; and

if a conflict and/or an order of arrival error is identified during the further conflict detection procedure, calling the further avoidance procedure

or

if a conflict and an order of arrival error is not detected during the further conflict detection procedure, continuing to call the recovery procedure or, if the further conflict detection procedure was called by the recovery procedure, continuing to the step of transmitting revised trajectories.

8. The method of claim 5, comprising revising aircraft intent data using a randomly generated parameter such as speed, altitude or position.

9. The method of claim 8, wherein the predefined joint candidate resolution patterns include templates that define:

increasing speed, decreasing speed, shortening a trajectory by removing a waypoint, lengthening a trajectory by adding a waypoint, increasing altitude and decreasing altitude.

10. The method of claim 9, comprising:

determining if a conflict arises because the aircraft being processed is catching up on the preceding aircraft or is being caught up by the following aircraft, and

if the aircraft being processed is catching up the preceding aircraft, randomly selecting a candidate resolution strategy from templates that define decreasing speed and lengthening a trajectory by adding a waypoint,

or

if the aircraft being processed is being caught up by the following aircraft, randomly selecting a candidate resolution strategy from templates that define increasing speed, and shortening a trajectory by removing a waypoint.

11. The method of claim 1, comprising an additional, optimisation procedure comprising further revising revised aircraft intent data of the plurality of aircraft to minimize a cost function calculated from revised aircraft intent data, and calling the further conflict detection procedure.

12. The method of claim 11, comprising performing the optimisation procedure as a global function that considers all revised aircraft data globally.

13. The method of claim 12, wherein the cost function is calculated from all revised aircraft intent data and is a measure of how unfairly or inequitably deviations in revised trajectories are spread amongst aircraft subject to revised aircraft intent data.

14. The method of claim 3, wherein processing of each aircraft comprises an additional, optimisation procedure comprising further revising the revised aircraft intent data of the aircraft being processed to minimize a cost function calculated from revised aircraft intent data.

15. The method of claim 12 wherein the cost function is a measure of how much the revised trajectory deviates from the user-preferred trajectory.

16. The method of claim 15, wherein the cost function is a measure of how much the lateral path defined by the revised aircraft intent data deviates from the lateral path defined by the user-preferred aircraft intent data.

17. The method of claim 1, wherein the airspace is a terminal airspace around an airport and the time constraint comprises a user-preferred time of arrival at the airport.

18. A system for managing airspace through which a plurality of aircraft are flying, the system comprising:

a computer apparatus;

a non-transitory computer readable medium comprising instructions stored thereon, that when executed by the computer apparatus, causes the computer apparatus to;

obtain user-preferred aircraft intent data of the aircraft that describe unambiguously the user-preferred trajectories of the aircraft through the airspace;

obtain time constraints for at least some of the aircraft, each time constraint comprising a user-preferred time of arrival at a common location;

calculate the corresponding user-preferred trajectories from the user-preferred aircraft intent data;

call an initial conflict detection procedure comprising comparing the calculated user-preferred trajectories to identify a plurality of conflicts between user-preferred trajectories, and identifying a plurality of conflicted aircraft predicted to fly the conflicting trajectories;

group the plurality of conflicts into a conflict dependent network;

select resolution actions for a set of the plurality of conflicted aircraft within a given conflict dependent network from a set of joint candidate resolution strategies derived from a set of predefined joint candidate resolution patterns;

gather all joint candidate resolution patterns for each conflict dependent network;

calling an initial conflict resolution procedure comprising revising the user preferred

select a most equitable joint candidate resolution pattern for each conflict dependent network;

transmit to the plurality of conflicted aircraft the most equitable joint candidate resolution pattern; and

order the plurality of conflicted aircraft to follow the most equitable joint candidate resolution pattern.

19. The system of claim 18 further comprising:

calling an initial avoidance procedure comprising revising the user-preferred aircraft intent data of a plurality of conflicted aircraft in a way that is configured to achieve the primary objective of resolving conflicts; and

calling a recovery procedure comprising determining if the user-preferred times of arrival are met by the revised trajectories and, if not, further revising the revised aircraft intent data of the associated aircraft in a way that is configured to achieve the secondary objective of meeting the time constraints.

20. A non-transitory computer readable medium having stored thereon a computer program for managing airspace through which a plurality of aircraft are flying, the computer program comprising instructions that when executed by a computer apparatus causes the computer apparatus to:

obtain user-preferred aircraft intent data of the aircraft that describe unambiguously the user-preferred trajectories of the aircraft through the airspace;

obtain time constraints for at least some of the aircraft, each time constraint comprising a user-preferred time of arrival at a common location;

calculate the corresponding user-preferred trajectories from the user-preferred aircraft intent data;

call an initial conflict detection procedure comprising comparing the calculated user-preferred trajectories to identify a plurality of conflicts between user-preferred trajectories, and identifying a plurality of conflicted aircraft predicted to fly the conflicting trajectories;

group the plurality of conflicts into a conflict dependent network;

select resolution actions for a set of the plurality of conflicted aircraft within a given conflict dependent network from a set of joint candidate resolution strategies derived from a set of predefined joint candidate resolution patterns;

gather all joint candidate resolution patterns for each conflict dependent network;

select a most equitable joint candidate resolution pattern for each conflict dependent network;

transmit to the plurality of conflicted aircraft the most equitable joint candidate resolution pattern; and

order the plurality of conflicted aircraft to follow the most equitable joint candidate resolution pattern.