Airport taxi route generator

1. A method comprising:

displaying, in a graphical user interface (GUI) of a computer, a map of a plurality of airport taxiways;

receiving a start point on the map;

receiving an endpoint on the map;

generating, automatically, a path for an aircraft to take to navigate the plurality of airport taxiways from the start point to the endpoint by:

receiving a relational database that defines points and edges for the map of the plurality of airport taxiways;

converting the relational database into a directed graph by:

generating a base layer using the relational database;

generating a corrected base layer by correcting the base layer;

generating nodes and edges from graphical data in the corrected base layer;

verifying that the nodes and edges are connected and routable such that there is a path from any one node to any other single node; and

exporting the nodes and edges as the directed graph; and

generating the path by querying the directed graph; and

superimposing the path on the map in the GUI.

2. The method of claim 1 , further comprising:

updating a keyboard on the GUI based on the path generated.

3. The method of claim 2 , further comprising:

receiving, based on a user interaction with the GUI, a waypoint or path change command;

generating a revised path by revising the path based on the waypoint or path change command;

removing a superimposition of the path on the map in the GUI; and

superimposing the revised path on the map in the GUI.

4. The method of claim 1 , further comprising:

updating the GUI to display only a subset of all possible waypoints or path change commands that can be used to subsequently change the endpoint or the path, the subset comprising permissible endpoints, waypoints, and path commands.

5. The method of claim 1 , further comprising:

receiving, prior to generating, a constraint from a controller,

wherein generating the path further comprises generating the path to obey the constraint.

6. The method of claim 1 , further comprising:

minimizing, using the directed graph, a distance for the path between the start point and the endpoint.

7. A non-transitory computer readable storage medium storing computer readable program code which, when executed by a processor, performs a computer-implemented method comprising:

displaying, in a graphical user interface (GUI) of a computer, a map of a plurality of airport taxiways;

receiving a start point on the map;

receiving an endpoint on the map;

generating, automatically, a path for an aircraft to take to navigate the plurality of airport taxiways from the start point to the endpoint by:

receiving a relational database that defines points and edges for the map of the plurality of airport taxiways;

converting the relational database into a directed graph by:

generating a base layer using the relational database;

generating a corrected base layer by correcting the base layer;

generating nodes and edges from graphical data in the corrected base layer;

verifying that the nodes and edges are connected and routable such that there is a path from any one node to any other single node; and

exporting the nodes and edges as the directed graph; and

generating the path by querying the directed graph; and

superimposing the path on the map in the GUI.

8. The method of claim 1 , wherein generating the path comprises:

applying an expanded Dijkstra algorithm comprising a Dijkstra algorithm constrained by a delayed label domination algorithm that penalizes disfavored possible paths, wherein the disfavored possible paths comprise those paths that violate a constraint.

9. The method of claim 1 , further comprising:

updating, concurrently with receiving the start point and the endpoint, the directed graph to ensure at least one connection between the start point and the endpoint.

10. The method of claim 1 , wherein generating the base layer comprises:

importing and normalizing taxiway guidance lines, taxiway holding positions, runway exit lines, and runway centerlines, and assigning persistent identifiers using the relational database.

11. The method of claim 1 , wherein correcting the base layer comprises an action selected from the group consisting of:

replacing an incomplete section of the directed graph by forcing approaching edges to meet at a corresponding node;

removing an invalid edge or an invalid node;

renaming an unknown label; and

receiving a manual correction to the base layer.

12. The method of claim 1 , further comprising:

adding an edge or a node to ensure that all nodes and all edges are connected and routable.

13. A system comprising:

a computer comprising:

a processor;

a data repository in communication with the processor; and

a display device in communication with the processor and configured to display a graphical user interface (GUI),

wherein the data repository stores computer readable program code which, when executed by the processor, performs a computer-implemented method comprising:

displaying, in the graphical user interface (GUI), a map of a plurality of airport taxiways;

receiving a start point on the map;

receiving an endpoint on the map;

generating, automatically, a path for an aircraft to take to navigate the plurality of airport taxiways from the start point to the endpoint by:

receiving a relational database that defines points and edges for the map of the plurality of airport taxiways;

converting the relational database into a directed graph by:

generating a base layer using the relational database;

generating a corrected base layer by correcting the base layer;

generating nodes and edges from graphical data in the corrected base layer;

verifying that the nodes and edges are connected and routable such that there is a path from any one node to any other single node; and

exporting the nodes and edges as the directed graph; and

generating the path by querying the directed graph; and

superimposing the path on the map in the GUI.

14. The system of claim 13 , wherein the display device and the GUI are configured to receive graphical input that designates the start point and the endpoint.

15. The system of claim 13 , wherein:

the data repository stores the relational database.

16. The system of claim 15 , wherein the computer readable program code for generating the base layer comprises computer readable program code for:

importing and normalizing taxiway guidance lines, taxiway holding positions, runway exit lines, and runway centerlines, and assigning persistent identifiers using the relational database.

17. The system of claim 13 , wherein the computer readable program code further comprises computer readable program code for:

updating a keyboard on the GUI based on the path generated.

18. The system of claim 17 , wherein the computer readable program code further comprises computer readable program code for:

receiving, based on a user interaction with the GUI, a waypoint or path change command;

generating a revised path by revising the path based on the waypoint or path change command;

removing a superimposition of the path on the map in the GUI; and

superimposing the revised path on the map in the GUI.

19. The system of claim 13 , wherein the computer readable program code further comprises computer readable program code for:

receiving, prior to generating, a constraint from an air traffic controller,

wherein generating the path further comprises generating the path to obey the constraint.

20. The non-transitory computer readable storage medium of claim 7 , wherein the computer-implemented method further comprises:

receiving, prior to generating, a constraint from a controller, wherein generating the path further comprises generating the path to obey the constraint.