Efficient allocation of resources in a fleet management system

1 . A non-transitory computer-readable medium having logic stored thereon that, in response to execution by one or more processors of a computing system, cause the computing system to perform actions for managing resources of a fleet of unmanned aerial vehicles (UAVs), the actions comprising:

creating, by the computing system, a mission record and one or more candidate records, wherein each candidate record of the one or more candidate records represents one or more resources for accomplishing a mission represented by the mission record;

adding, by the computing system, a mission node representing the mission record to a resource competition network graph (RCN graph);

adding, by the computing system, one or more candidate nodes representing the one or more candidate records to the RCN graph;

determining, by the computing system, an optimized allocation of candidate records to mission records using at least a subgraph of the RCN graph;

determining a candidate record to commit to a mission record;

updating, by the computing system, the RCN graph to commit the candidate record to the mission record; and

transmitting, by the computing system, commands to one or more resources of the candidate record committed to the mission record to execute the mission represented by the mission record;

wherein the RCN graph includes:

a mission layer;

a candidate layer;

one or more candidate layer edges that connect candidate nodes in the candidate layer to indicate that the connected candidate nodes conflict with each other;

one or more cross-layer edges that connect candidate nodes in the candidate layer and mission nodes in the mission layer; and

one or more mission layer edges that connect mission nodes in the mission layer to indicate that the mission nodes are connected to conflicting candidate nodes.

2 . The non-transitory computer-readable medium of claim 1 , wherein adding the one or more candidate nodes representing the one or more candidate records to the RCN graph includes:

determining, by the computing system, a set of potentially conflicting candidate nodes in the RCN graph for a new candidate node using a geospatial lookup table; and

for each potentially conflicting candidate node having a conflict with the new candidate node, creating a candidate layer edge in the RCN graph connecting the potentially conflicting candidate node having the conflict with the new candidate node.

3 . The non-transitory computer-readable medium of claim 2 , wherein adding the one or more candidate nodes representing the one or more candidate records to the RCN graph further includes:

for each potentially conflicting candidate node having a conflict with the new candidate node, creating a mission layer edge between the mission node and a conflicting mission node associated with the potentially conflicting candidate node having the conflict.

4 . The non-transitory computer-readable medium of claim 1 , wherein updating the RCN graph to commit the candidate record to the mission record includes operations comprising:

removing a candidate node representing the candidate record;

removing neighboring candidate nodes connected to the candidate node;

removing edges connected to any of the candidate node or the neighboring candidate nodes;

removing a mission node representing the mission record; and

removing edges connected to the mission node.

5 . The non-transitory computer-readable medium of claim 4 , wherein the operations of updating the RCN graph to commit the candidate record to the mission record are rolled back if not all constituent mutation operations succeed.

6 . The non-transitory computer-readable medium of claim 1 , wherein determining the optimized allocation of candidate records to mission records using at least a subgraph of the RCN graph includes:

determining a mutated subgraph of the RCN graph since a previous optimized allocation of candidate records; and

conducting an optimization over the mutated subgraph to allocate candidate records to the mission records.

7 . The non-transitory computer-readable medium of claim 6 , wherein conducting the optimization includes using at least one of an integer programming solver, an exhaustive search allocation, a random priority candidate allocation, an auction optimization, a stochastic optimization, a belief propagation allocation, or a population technique.

8 . The non-transitory computer-readable medium of claim 1 , wherein determining the candidate record to commit to the mission record includes receiving a command to commit the candidate record to the mission record from a mission planning and assignment system.

9 . The non-transitory computer-readable medium of claim 1 , wherein the actions further comprise:

creating, by the computing system, a batch associated with a predetermined batch time span and a given geographical area associated with a first mutation applied to the RCN graph in volatile memory;

collecting, by the computing system, additional mutations applied to the RCN graph during the predetermined batch time span and associated with mission nodes or candidate nodes within the given geographical area;

upon the expiration of the predetermined batch time span, applying the mutations in the batch to the RCN graph in non-volatile memory; and

rolling back any applied mutations from the batch if any of the mutations in the batch are not successfully applied.

10 . A computer-implemented method for managing resources of a fleet of unmanned aerial vehicles (UAVs), the method comprising:

creating, by a computing system, a mission record and one or more candidate records, wherein each candidate record of the one or more candidate records represents one or more resources for accomplishing a mission represented by the mission record;

adding, by the computing system, a mission node representing the mission record to a resource competition network graph (RCN graph);

adding, by the computing system, one or more candidate nodes representing the one or more candidate records to the RCN graph;

determining, by the computing system, an optimized allocation of candidate records to mission records using at least a subgraph of the RCN graph;

determining a candidate record to commit to a mission record;

updating, by the computing system, the RCN graph to commit the candidate record to the mission record; and

transmitting, by the computing system, commands to one or more resources of the candidate record committed to the mission record to execute the mission represented by the mission record;

wherein the RCN graph includes:

a mission layer;

a candidate layer;

one or more candidate layer edges that connect candidate nodes in the candidate layer to indicate that the connected candidate nodes conflict with each other;

one or more cross-layer edges that connect candidate nodes in the candidate layer and mission nodes in the mission layer; and

one or more mission layer edges that connect mission nodes in the mission layer to indicate that the mission nodes are connected to conflicting candidate nodes.

11 . The computer-implemented method of claim 10 , wherein adding the one or more candidate nodes representing the one or more candidate records to the RCN graph includes:

determining, by the computing system, a set of potentially conflicting candidate nodes in the RCN graph for a new candidate node using a geospatial lookup table; and

for each potentially conflicting candidate node having a conflict with the new candidate node, creating a candidate layer edge in the RCN graph connecting the potentially conflicting candidate node having the conflict with the new candidate node.

12 . The computer-implemented method of claim 11 , wherein adding the one or more candidate nodes representing the one or more candidate records to the RCN graph further includes:

for each potentially conflicting candidate node having a conflict with the new candidate node, creating a mission layer edge between the mission node and a conflicting mission node associated with the potentially conflicting candidate node having the conflict.

13 . The computer-implemented method of claim 10 , wherein updating the RCN graph to commit the candidate record to the mission record includes operations comprising:

removing a candidate node representing the candidate record;

removing neighboring candidate nodes connected to the candidate node;

removing edges connected to any of the candidate node or the neighboring candidate nodes;

removing a mission node representing the mission record; and

removing edges connected to the mission node.

14 . The computer-implemented method of claim 13 , wherein the operations of updating the RCN graph to commit the candidate record to the mission record are rolled back if not all constituent mutation operations succeed.

15 . The computer-implemented method of claim 10 , wherein determining the optimized allocation of candidate records to mission records using at least a subgraph of the RCN graph includes:

determining a mutated subgraph of the RCN graph since a previous optimized allocation of candidate records; and

conducting an optimization over the mutated subgraph to allocate candidate records to the mission records.

16 . The computer-implemented method of claim 15 , wherein conducting the optimization includes using at least one of an integer programming solver, an exhaustive search allocation, a random priority candidate allocation, an auction optimization, a stochastic optimization, a belief propagation allocation, or a population technique.

17 . The computer-implemented method of claim 10 , wherein determining the candidate record to commit to the mission record includes receiving a command to commit the candidate record to the mission record from a mission planning and assignment system.

18 . The computer-implemented method of claim 10 , further comprising:

creating, by the computing system, a batch associated with a predetermined batch time span and a given geographical area associated with a first mutation applied to the RCN graph in volatile memory;

collecting, by the computing system, additional mutations applied to the RCN graph during the predetermined batch time span and associated with mission nodes or candidate nodes within the given geographical area;

upon the expiration of the predetermined batch time span, applying the mutations in the batch to the RCN graph in non-volatile memory; and

rolling back any applied mutations from the batch if any of the mutations in the batch are not successfully applied.