Drone management data structure

• US 10,417,917 B2
• Filed: 03/08/2016
• Issued: 09/17/2019
• Est. Priority Date: 03/08/2016
• Status: Active Grant

• Current Assignee: DoorDash, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Blomberg, Jeanette L., Butler, Eric K., Chandra, Anca A., Chowdhary, Pawan R., Griffin, Thomas D., Jadav, Divyesh, Moore, Robert J., Strong, Jr., Hovey R.
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Chiu, Katriel Y
• Application Number:
  US15/064,551
• Publication Number:
  US 20170263134A1
• Time in Patent Office: 1,288 Days
• Field of Search: None
• CPC Class Codes: G08G 5/0013 with a ground station
• CPC Class Codes: G08G 5/0026 located on the ground
• CPC Class Codes: G08G 5/0039 Modification of a flight plan
• CPC Class Codes: G08G 5/0056 in an emergency situation, e.g. hijacking
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft
• CPC Class Codes: G08G 5/0082 for monitoring traffic from a ground station radar or analogous systems specially adapted for traffic control G01S13/91

Abstract

One embodiment provides a method comprising maintaining a multi-dimensional data structure partitioned into cells utilizing a tree data structure (“tree”) comprising intervals for each dimension of a multi-dimensional space. To partition an interval for a node of the tree into multiple subintervals, multiple leaf nodes (“leaves”) are generated, each leaf descending from the node. To merge multiple intervals for multiple nodes of the tree, a parent node (“parent”) and multiple leaves descending from the parent are generated, the parent and the leaves are time constrained, and the leaves are scheduled for a merger. When transient data in cells included in a list that corresponds to a leaf scheduled for merger expires, each cell in the list is converted into a cell for inclusion in a different list corresponding to a parent of the leaf, each leaf of the parent removed, and the parent turned into a leaf.

Claims

1. A method, comprising:

maintaining a multi-dimensional data structure partitioned into a plurality of cells representing a multi-dimensional air space within an air traffic control zone, wherein the plurality of cells are defined by a tree data structure comprising a plurality of nodes, each node of the tree data structure comprises an interval of a dimension of the multi-dimensional air space, one or more nodes of the tree data structure are associated with one or more lists of cells from the plurality of cells, and the plurality of cells include sparse and transient data; and

reducing air traffic congestion and a number of conflicts within the air traffic control zone among flight plans for drones by;

in response to receiving a flight plan request for a drone, locking one or more cells of the plurality of cells on behalf of the drone, and returning a flight plan comprising the one or more locked cells, wherein flight of the drone within the air traffic control zone is controlled in accordance with the flight plan;

in response to an increase in the number of conflicts within the air traffic control zone, repartitioning the plurality of cells into more cells available for locking by partitioning an interval of a node of the tree data structure into multiple subintervals via generating multiple leaf nodes corresponding to the multiple subintervals, wherein each leaf node descends from the node; and

in response to a decrease in the number conflicts in the air traffic control zone, repartitioning the plurality of cells into fewer cells available for locking by merging multiple intervals of multiple nodes of the tree data structure via generating a parent node and multiple leaf nodes descending from the parent node, wherein the parent node and the multiple leaf nodes are time constrained, and the multiple leaf nodes are scheduled for a merger.

2. The method of claim 1, wherein each cell of the plurality of cells implicitly points to a hash table of transient data, and a hash function is applied when concatenating multiple intervals of multiple nodes of the tree data structure during a merger of the multiple intervals.

3. The method of claim 1, wherein a merger of multiple intervals of multiple nodes of the tree data structure is determined based on a measure of activity associated with lists of cells associated with the multiple nodes.

4. The method of claim 1, wherein a partition of an interval of a node of the tree data structure is determined based on a measure of activity associated with a list of cells associated with the node.

5. The method of claim 2, wherein a time constraint associated with a node of the tree data structure indicates whether a piece of information should be associated with the node based on time or times associated with the piece of information.

16. The method of claim 1, wherein reducing air traffic congestion and a number of conflicts within the air traffic control zone among flight plans for drones further comprises:

in response to expiration of transient data in lists of cells associated with all but one leaf node of the tree data structure scheduled for merger, converting each cell of a list of cells associated with the one leaf node into a different cell for inclusion in a different list of cells associated with a parent node of the one leaf node, removing each leaf node of the parent node, and turning the parent node into a leaf node.

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:

maintaining a multi-dimensional data structure partitioned into a plurality of cells representing a multi-dimensional air space within an air traffic control zone, wherein the plurality of cells are defined by a tree data structure comprising a plurality of nodes, each node of the tree data structure comprises an interval of a dimension of the multi-dimensional air space, one or more nodes of the tree data structure are associated with one or more lists of cells from the plurality of cells, and the plurality of cells include sparse and transient data; and

reducing air traffic congestion and a number of conflicts within the air traffic control zone among flight plans for drones by;

in response to receiving a flight plan request for a drone, locking one or more cells of the plurality of cells on behalf of the drone, and returning a flight plan comprising the one or more locked cells, wherein flight of the drone within the air traffic control zone is controlled in accordance with the flight plan;

in response to an increase in the number of conflicts within the air traffic control zone, repartitioning the plurality of cells into more cells available for locking by partitioning an interval of a node of the tree data structure into multiple subintervals via generating multiple leaf nodes corresponding to the multiple subintervals, wherein each leaf node descends from the node; and

in response to a decrease in the number conflicts in the air traffic control zone, repartitioning the plurality of cells into fewer cells available for locking by merging multiple intervals of multiple nodes of the tree data structure via generating a parent node and multiple leaf nodes descending from the parent node, wherein the parent node and the multiple leaf nodes are time constrained, and the multiple leaf nodes are scheduled for a merger.

7. The system of claim 6, wherein each cell of the plurality of cells implicitly points to a hash table of transient data, and a hash function is applied when concatenating multiple intervals of multiple nodes of the tree data structure during a merger of the multiple intervals.

8. The system of claim 6, wherein a merger of multiple intervals of multiple nodes of the tree data structure is determined based on a measure of activity associated with lists of cells associated with the multiple nodes.

9. The system of claim 6, wherein a partition of an interval of a node of the tree data structure is determined based on a measure of activity associated with a list of cells associated with the node.

10. The system of claim 7, wherein a time constraint associated with a node of the tree data structure indicates whether a specific piece of information should be associated with the node based on time or times associated with the piece of information.

17. The system of claim 6, wherein reducing air traffic congestion and a number of conflicts within the air traffic control zone among flight plans for drones further comprises:

in response to an expiration of transient data in lists of cells associated with all but one leaf node of the tree data structure scheduled for merger, converting each cell of a list of cells associated with the one leaf node into a different cell for inclusion in a different list of cells associated with a parent node of the one leaf node, removing each leaf node of the parent node, and turning the parent node into a leaf node.

11. A 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:

maintaining a multi-dimensional data structure partitioned into a plurality of cells representing a multi-dimensional air space within an air traffic control zone, wherein the plurality of cells are defined by a tree data structure comprising a plurality of nodes, each node of the tree data structure comprises an interval of a dimension of the multi-dimensional air space, one or more nodes of the tree data structure are associated with one or more lists of cells from the plurality of cells, and the plurality of cells include sparse and transient data; and

reducing air traffic congestion and a number of conflicts within the air traffic control zone among flight plans for drones by;

in response to receiving a flight plan request for a drone, locking one or more cells of the plurality of cells on behalf of the drone, and returning a flight plan comprising the one or more locked cells, wherein flight of the drone within the air traffic control zone is controlled in accordance with the flight plan;

in response to an increase in the number of conflicts within the air traffic control zone, repartitioning the plurality of cells into more cells available for locking by partitioning an interval of a node of the tree data structure into multiple subintervals via generating multiple leaf nodes corresponding to the multiple subintervals, wherein each leaf node descends from the node; and

in response to a decrease in the number conflicts in the air traffic control zone, repartitioning the plurality of cells into fewer cells available for locking by merging multiple intervals of multiple nodes of the tree data structure via generating a parent node and multiple leaf nodes descending from the parent node, wherein the parent node and the multiple leaf nodes are time constrained, and the multiple leaf nodes are scheduled for a merger.

12. The computer program product of claim 11, wherein each cell of the plurality of cells implicitly points to a hash table of transient data, and a hash function is applied when concatenating multiple intervals of multiple nodes of the tree data structure during a merger of the multiple intervals.

13. The computer program product of claim 11, wherein a merger of multiple intervals of multiple nodes of the tree data structure is determined based on a measure of activity associated with lists of cells associated with the multiple nodes.

14. The computer program product of claim 11, wherein a partition of an interval of a node of the tree data structure is determined based on a measure of activity associated with a list of cells associated with the node.

15. The computer program product of claim 12, wherein a time constraint associated with a node of the tree data structure indicates whether a specific piece of information should be associated with the node based on time or times associated with the piece of information.

18. The computer program product of claim 11, wherein reducing air traffic congestion and a number of conflicts within the air traffic control zone among flight plans for drones further comprises:

in response to an expiration of transient data in lists of cells associated with all but one leaf node of the tree data structure scheduled for merger, converting each cell of a list of cells associated with the one leaf node into a different cell for inclusion in a different list of cells associated with a parent node of the one leaf node, removing each leaf node of the parent node, and turning the parent node into a leaf node.