Methods and systems for displaying a taxi clearance

• US 8,731,811 B2
• Filed: 10/20/2011
• Issued: 05/20/2014
• Est. Priority Date: 10/20/2011
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Bilek, Jan, Pokorny, Ondrej, Marczi, Tomas
• Primary Examiner(s): Jabr, Fadey
• Assistant Examiner(s): HEINLE, COURTNEY D
• Application Number:
  US13/277,682
• Publication Number:
  US 20130103297A1
• Time in Patent Office: 943 Days
• Field of Search: 701/120, 701/528, 701/532, 701/537, 701/538
• US Class Current: 701/120
• CPC Class Codes: G08G 5/0021 located in the aircraft
• CPC Class Codes: G08G 5/065 Navigation or guidance aids, e.g. for taxiing or rolling

Abstract

Methods and systems are provided for completing and displaying a taxi clearance for an aircraft at an airport. One exemplary method involves receiving an input taxi clearance including a first taxi path of a plurality of taxi paths at the airport and a second taxi path of the plurality of taxi paths that succeeds the first taxi path in the input taxi clearance, and determining a plurality of possible taxi routes between the first taxi path and the second taxi path. The method continues by identifying an optimal taxi route from among the plurality of possible taxi routes, and graphically indicating that the taxi clearance for the aircraft includes the optimal taxi route between the first taxi path and the second taxi path.

Claims

1. A method of displaying a taxi clearance for an aircraft, the method comprising:

receiving an input taxi clearance including a first taxi path of a plurality of taxi paths at an airport and a second taxi path of the plurality of taxi paths, the second taxi path succeeding the first taxi path in the input taxi clearance, a discontinuity existing between the first taxi path and the second taxi path;

constructing an oriented graph data structure based on the plurality of taxi paths at the airport;

determining the discontinuity exists in the input taxi clearance between the first taxi path and the second taxi path;

identifying one or more starting nodes of the oriented graph data structure based on the first taxi path, the one or more starting nodes representing one or more locations along the first taxi path where the aircraft may exit the first taxi path by excluding, from the one or more starting nodes, a first node of the oriented graph data structure that corresponds to a location where the aircraft will enter the first taxi path;

identifying one or more destination nodes of the oriented graph data structure based on the second taxi path, the one or more destination nodes being associated with the second taxi path, wherein a second node of the oriented graph data structure that corresponds to an intersection of the second taxi path and a next succeeding taxi path of the input taxi clearance is excluded from the one or more destination nodes;

determining, by a processing system, a plurality of possible taxi routes between the first taxi path and the second taxi path using the oriented graph data structure, wherein each possible taxi route of the plurality of possible taxi routes comprises a route between a starting node of the one or more starting nodes and a destination node of the one or more destination nodes;

identifying an optimal taxi route from among the plurality of possible taxi routes; and

graphically indicating, on a display device associated with the aircraft, that the taxi clearance for the aircraft includes the optimal taxi route between the first taxi path and the second taxi path.

2. The method of claim 1, wherein identifying the optimal taxi route comprises identifying a first taxi route of the plurality of possible taxi routes as having a shortest length relative to remaining taxi routes of the plurality of possible taxi routes.

3. The method of claim 1, wherein identifying the optimal taxi route comprises identifying a first taxi route of the plurality of possible taxi routes as having a lowest complexity relative to remaining taxi routes of the plurality of possible taxi routes.

4. The method of claim 1, wherein identifying the optimal taxi route comprises identifying a first taxi route of the plurality of possible taxi routes as having a lowest number of runway crossings relative to remaining taxi routes of the plurality of possible taxi routes.

5. The method of claim 1, wherein identifying the optimal taxi route comprises excluding a first taxi route of the plurality of possible taxi routes based on a length of the first taxi route relative to a length of the optimal taxi route.

6. The method of claim 1, wherein identifying the optimal taxi route comprises excluding a first taxi route of the plurality of possible taxi routes based on a complexity of the first taxi route relative to a complexity of the optimal taxi route.

7. The method of claim 1, wherein identifying the optimal taxi route comprises excluding a first taxi route of the plurality of possible taxi routes based on a number of runway crossings of the first taxi route relative to a number of runway crossings of the optimal taxi route.

8. The method of claim 1, wherein identifying the optimal taxi route comprises:

identifying a first subset of the plurality of possible taxi routes based on lengths of the plurality of possible taxi routes, the first subset including the optimal taxi route;

identifying a second subset of the first subset of possible taxi routes based on a number of runway crossings for the possible taxi routes of the first subset, the second subset including the optimal taxi route;

identifying a third subset of the second subset of possible taxi routes based on relative complexities of the possible taxi routes of the second subset; and

identifying an individual taxi route of the plurality of possible taxi routes as the optimal taxi route when the third subset includes only the individual taxi route.

9. The method of claim 8, wherein:

identifying the first subset comprises excluding one or more taxi routes of the plurality of possible taxi routes having a length greater than a length of the optimal taxi route;

identifying the second subset comprises excluding one or more taxi routes of the first subset having a number of runway crossings greater than a number of runway crossings for the optimal taxi route; and

identifying the third subset comprises excluding one or more taxi routes of the second subset having a number of taxi paths greater than a number of taxi paths of the optimal taxi route.

10. The method of claim 1, each possible route including one or more edges between one of the one or more starting nodes and one of the one or more destination nodes, wherein identifying the optimal taxi route comprises:

determining, for each possible route, a total length based on weighted lengths of the one or more edges of the respective possible route; and

identifying a first subset of the plurality of possible routes, wherein the possible routes of the first subset have lower total lengths relative to remaining possible routes of the plurality of possible routes.

11. The method of claim 10, wherein identifying the optimal taxi route further comprises:

determining, for each possible route of the first subset, a number of runway crossings for the respective possible route; and

identifying a second subset of the first subset of possible routes, wherein the possible routes of the second subset have fewer runway crossings relative to remaining possible routes of the first subset.

12. The method of claim 11, wherein identifying the optimal taxi route further comprises:

determining, for each possible route of the second subset, a number of taxi paths for the respective possible route; and

identifying a first possible route of the second subset having a lowest number of taxi paths as the optimal taxi route.

13. The method of claim 1, wherein determining the plurality of possible taxi routes comprises excluding any taxi route between a starting node of the one or more starting nodes and a destination node of the one or more destination nodes that indicates a redundancy in the taxi clearance.

14. A method of displaying a taxi clearance for an aircraft on a display device onboard the aircraft, the method comprising:

receiving an input taxi clearance for the aircraft, the input taxi clearance including a first taxi path of a plurality of taxi paths at an airport and a second taxi path of the plurality of taxi paths, wherein the second taxi path succeeds the first taxi path in the input taxi clearance;

determining that the first taxi path and the second taxi path do not intersect;

determining, by a processing system, a plurality of possible taxi routes between the first taxi path and the second taxi path in response to determining that the first taxi path and the second taxi path do not intersect, each possible taxi route including one or more taxi paths of the plurality of taxi paths, wherein determining the plurality of possible taxi routes comprises;

constructing an oriented graph data structure based on the plurality of taxi paths at the airport;

identifying one or more starting nodes of the oriented graph data structure based on the first taxi path, the one or more starting nodes representing one or more locations along the first taxi path where the aircraft may exit the first taxi path;

identifying one or more destination nodes of the oriented graph data structure based on the second taxi path, the one or more destination nodes being associated with the second taxi path, wherein a first node of the oriented graph data structure that corresponds to an intersection of the second taxi path and a next succeeding taxi path of the input taxi clearance is excluded from the one or more destination nodes; and

determining the plurality of possible taxi routes using the oriented graph data structure, wherein each possible taxi route of the plurality of possible taxi routes comprises a route between a starting node of the one or more starting nodes and a destination node of the one or more destination nodes;

identifying a first taxi route from among the plurality of possible taxi routes as an optimal taxi route between the first taxi path and the second taxi path; and

displaying, on the display device, a graphical representation of the taxi clearance including the optimal taxi route inserted between the first taxi path and the second taxi path.

15. The method of claim 14, wherein identifying the first taxi route comprises selecting, from the plurality of possible taxi routes, a first subset of possible taxi routes based on respective lengths of the possible taxi routes of the first subset relative to respective lengths of remaining possible taxi routes of the plurality of possible taxi routes, wherein the respective lengths of the possible taxi routes of the first subset are less than the respective lengths of the remaining possible taxi routes of the plurality of possible taxi routes.

16. The method of claim 15, wherein identifying the first taxi route further comprises selecting, from the first subset, a second subset of possible taxi routes based on a number of runway crossings of the possible taxi routes of the second subset relative to a respective number of runway crossings of remaining possible taxi routes of the first subset, wherein the number of runway crossings of the possible taxi routes of the second subset are less than the number of runway crossings of the remaining possible taxi routes of the first subset.

17. The method of claim 16, wherein identifying the first taxi route further comprises selecting, from the second subset, the first taxi route based on a complexity of the first taxi route relative to remaining possible taxi routes of the second subset.

18. A system comprising:

a display device;

a data storage element configured to maintain information pertaining to a plurality of taxi paths; and

a processing system coupled to the display device and the data storage element, wherein the processing system is configured to;

receive an input taxi clearance including a first taxi path of the plurality of taxi paths and a second taxi path of the plurality of taxi paths, the second taxi path succeeding the first taxi path, a discontinuity existing between the first taxi path and the second taxi path;

construct an oriented graph data structure based on the information maintained by the data storage element;

determine the discontinuity exists in the input taxi clearance between the first taxi path and the second taxi path;

identify one or more starting nodes of the oriented graph data structure based on the first taxi path, the one or more starting nodes representing one or more locations along the first taxi path where an aircraft may exit the first taxi path, wherein a first node of the oriented graph data structure that corresponds to a location where the aircraft will enter the first taxi path is excluded from the one or more starting nodes;

identifying one or more destination nodes of the oriented graph data structure based on the second taxi path, the one or more destination nodes being associated with the second taxi path, wherein a second node of the oriented graph data structure that corresponds to an intersection of the second taxi path and a next succeeding taxi path of the input taxi clearance is excluded from the one or more destination nodes;

determine a plurality of possible taxi routes between the first taxi path and the second taxi path using the oriented graph data structure, wherein each possible taxi route of the plurality of possible taxi routes comprises a route between a starting node of the one or more starting nodes and a destination node of the one or more destination nodes;

identify an optimal taxi route from among the plurality of possible taxi routes based on the information maintained by the data storage element; and

graphically indicate the optimal taxi route on the display device.

19. The system of claim 18, wherein:

the display device is onboard the aircraft;

the display device has a map of an airport having the plurality of taxi paths displayed thereon; and

the processing system is configured to graphically indicate the optimal taxi route by displaying a graphical representation of a taxi clearance including the optimal taxi route between the first taxi path and the second taxi path overlying the map.