Drone air traffic control and flight plan management
One embodiment provides a method comprising receiving a flight plan request for a drone. The flight plan request comprises a drone identity, departure information, and arrival information. The method further comprises constructing a modified flight plan for the drone based on the flight plan request, wherein the modified flight plan represents an approved, congestion reducing, and executable flight plan for the drone, and the modified flight plan comprises a sequence of four-dimensional (4D) cells representing a planned flight path for the drone. For each 4D cell of the modified flight plan, the method further comprises attempting to place an exclusive lock on behalf of the drone on the 4D cell, and in response to a failure to place the exclusive lock on behalf of the drone on the 4D cell, rerouting the modified flight plan around the 4D cell to a random neighboring 4D cell.
1. A method comprising:
partitioning a map of available air space within a control zone into multiple multi-dimensional cell structures, wherein the multiple multi-dimensional cell structures are defined by a tree data structure comprising a plurality of nodes, and each node of the tree data structure corresponds to one or more of the multiple multi-dimensional cell structures and comprises an interval of a dimension of the available air space;
reducing air traffic congestion within the control zone by:
in response to an increase in frequency of conflicts within the control zone, repartitioning at least one of the multiple multi-dimensional cell structures by splitting a leaf node of the tree data structure into multiple leaf nodes when a corresponding measure of activity of the leaf node exceeds a first pre-determined threshold; and
in response to a decrease in the frequency of conflicts within the control zone, merging at least two of the multiple multi-dimensional cell structures by merging at least two leaf nodes of the tree data structure into one leaf node when a corresponding measure of activity of each of the at least two leaf nodes is less than a second pre-determined threshold;
locking, on behalf of a drone when no conflicts exist with other drones, one or more of the multiple multi-dimensional cell structures available for locking; and
controlling flight of the drone within the control zone based on a flight plan comprising the one or more multi-dimensional cell structures locked on behalf of the drone;
wherein, in the method, at least one leaf node of the tree data structure maintains a list that includes one or more active multi-dimensional cell structures for which a lock has been placed on behalf of the drone.
2. The method of claim 1 , wherein each of the multiple multi-dimensional cell structures is a four dimensional cell structure.
3. The method of claim 1 , wherein each of the multiple multi-dimensional cell structures has a density that varies in each dimension based on volume of local traffic and the frequency of conflicts within the control zone.
4. The method of claim 1 , wherein the reducing further comprises:
maintaining a count of lock conflicts for the control zone; and
determining whether the count of lock conflicts for the control zone exceeds a pre-determined threshold.
5. The method of claim 4 , wherein the repartitioning occurs in response to determining the count of lock conflicts for the control zone exceeds the pre-determined threshold.
6. A system comprising a computer processor, a computer-readable hardware storage medium, and program code embodied with the computer-readable hardware storage medium for execution by the computer processor to implement a method comprising:
partitioning a map of available air space within a control zone into multiple multi-dimensional cell structures, wherein the multiple multi-dimensional cell structures are defined by a tree data structure comprising a plurality of nodes, and each node of the tree data structure corresponds to one or more of the multiple multi-dimensional cell structures and comprises an interval of a dimension of the available air space;
reducing air traffic congestion within the control zone by:
in response to an increase in frequency of conflicts within the control zone, repartitioning at least one of the multiple multi-dimensional cell structures by splitting a leaf node of the tree data structure into multiple leaf nodes when a corresponding measure of activity of the leaf node exceeds a first pre-determined threshold; and
in response to a decrease in the frequency of conflicts within the control zone, merging at least two of the multiple multi-dimensional cell structures by merging at least two leaf nodes of the tree data structure into one leaf node when a corresponding measure of activity of each of the at least two leaf nodes is less than a second pre-determined threshold;
locking, on behalf of a drone when no conflicts exist with other drones, one or more of the multiple multi-dimensional cell structures available for locking; and
controlling flight of the drone within the control zone based on a flight plan comprising the one or more multi-dimensional cell structures locked on behalf of the drone;
wherein, in the method, at least one leaf node of the tree data structure maintains a list that includes one or more active multi-dimensional cell structures for which a lock has been placed on behalf of the drone.
7. The system of claim 6 , wherein each of the multiple multi-dimensional cell structures is a four dimensional cell structure.
8. The system of claim 6 , wherein each of the multiple multi-dimensional cell structures has a density that varies in each dimension based on volume of local traffic and the frequency of conflicts within the control zone.
9. The system of claim 6 , wherein the reducing further comprises:
maintaining a count of lock conflicts for the control zone; and
determining whether the count of lock conflicts for the control zone exceeds a pre-determined threshold.
10. The system of claim 9 , wherein the repartitioning occurs in response to determining the count of lock conflicts for the control zone exceeds the pre-determined threshold.
11. A non-transitory computer program product comprising a computer-readable hardware storage device having program code embodied therewith, the program code being executable by a computer to implement a method comprising:
partitioning a map of available air space within a control zone into multiple multi-dimensional cell structures, wherein the multiple multi-dimensional cell structures are defined by a tree data structure comprising a plurality of nodes, and each node of the tree data structure corresponds to one or more of the multiple multi-dimensional cell structures and comprises an interval of a dimension of the available air space;
reducing air traffic congestion within the control zone by:
in response to an increase in frequency of conflicts within the control zone, repartitioning at least one of the multiple multi-dimensional cell structures by splitting a leaf node of the tree data structure into multiple leaf nodes when a corresponding measure of activity of the leaf node exceeds a first pre-determined threshold; and
in response to a decrease in the frequency of conflicts within the control zone, merging at least two of the multiple multi-dimensional cell structures by merging at least two leaf nodes of the tree data structure into one leaf node when a corresponding measure of activity of each of the at least two leaf nodes is less than a second pre-determined threshold;
locking, on behalf of a drone when no conflicts exist with other drones, one or more of the multiple multi-dimensional cell structures available for locking; and
controlling flight of the drone within the control zone based on a flight plan comprising the one or more multi-dimensional cell structures locked on behalf of the drone;
wherein, in the method, at least one leaf node of the tree data structure maintains a list that includes one or more active multi-dimensional cell structures for which a lock has been placed on behalf of the drone.
12. The computer program product of claim 11 , wherein each of the multiple multi-dimensional cell structures is a four dimensional cell structure.
13. The computer program product of claim 11 , wherein each of the multiple multi-dimensional cell structures has a density that varies in each dimension based on volume of local traffic and the frequency of conflicts within the control zone.
14. The computer program product of claim 11 , wherein the reducing further comprises:
maintaining a count of lock conflicts for the control zone; and
determining whether the count of lock conflicts for the control zone exceeds a pre-determined threshold.
15. The computer program product of claim 14 , wherein the repartitioning occurs in response to determining the count of lock conflicts for the control zone exceeds the pre-determined threshold.