# US 2021/0173700 A1 · Task Allocation for Vehicles

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0173700 A1
- Document ID: US20210173700A1
- Status: Published application
- Kind: A1
- Application number: 16/704,326
- Filed: 2019-12-05
- Published: 2021-06-10
- Earliest claimed: 2019-12-05
- Assignees: Aurora Flight Sciences Corporation
- Applicants: Aurora Flight Sciences Corporation
- Inventors: Jeffery Saunders
- Web page: https://patentgrep.com/patent/US20210173700A1

## CPC

- G05D 1/0027: {involving a plurality of vehicles, e.g. fleet or convoy travelling (fleet control of land vehicles from a control room G05D1/0297; traffic control systems for road vehicles G08G1/00; for marine craft G08G3/00; for aircraft G08G5/00)}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G05D 1/104: {involving a plurality of aircrafts, e.g. formation flying (traffic control systems for aircraft G08G5/00)}
- G06F 16/245: Query processing
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- B64U 30/10: Wings
- B64U 30/295: Rotors arranged in the wings
- B64U 30/296: Rotors with variable spatial positions relative to the UAV body (foldable or collapsible rotors B64U30/293)
- B64U 30/40: Empennages, e.g. V-tails (foldable or collapsible UAVs B64U20/50)
- B64U 2101/30: for imaging, photography or videography
- B64U 2201/10: autonomous, i.e. by navigating independently from ground or air stations, e.g. by using inertial navigation systems [INS]
- B64U 2201/20: Remote controls
- G05D 1/0088: {characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours (using knowledge based models G06N5/00)}
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- B64U: UNMANNED AERIAL VEHICLES [UAV]; EQUIPMENT THEREFOR

## Abstract

Methods and apparatus are provided for allocating tasks to be performed by one or more autonomous vehicles to achieve a mission objective. Generally, a task allocation system identifies a final task associated with a given mission objective, identifies predecessor tasks necessary to complete the final task, generates one or more candidate tasks sequences to accomplish the mission objective, generates a task allocation tree based on the candidate task sequences, and searches the task allocation tree to find a task allocation plan that meets a predetermined selection criteria (e.g., lowest cost). Based on the task allocation plan, the task allocation system determines a task execution plan and generates control data for controlling one or more autonomous vehicles to complete the task execution plan.

## Claims

### Claim 1

A method, implemented by a processing circuit, of allocating task among one or more vehicles, the method comprising:
determining one or more candidate task sequences that achieve a mission objective, each candidate task sequence comprising a plurality of tasks;
generating, based on the one or more candidate task sequences, a task allocation tree representing a plurality of potential task allocation plans for allocating the tasks in one or more of the candidate task sequences among one or more vehicles, wherein:
the task allocation tree comprises a root node and a plurality of child nodes, each of the plurality of child nodes corresponding to a possible allocation of one of the tasks in one of the candidate task sequences to one of the one or more vehicles; and
each task allocation plan comprises a unique path through the task allocation tree from the root node through one or more child nodes to a leaf node;
searching the task allocation tree for a task allocation plan that meets a predetermined selection criterion;
generating a task execution plan based on a selected task allocation plan; and
generating control data for at least one of the vehicles to implement the task execution plan.

### Claim 2 (depends on 1)

The method of claim 1, wherein determining one or more candidate task sequences that achieve a mission objective comprises determining, for at least one of the plurality of tasks, a preset sequence of steps stored in a linear data structure to perform the task.

### Claim 3 (depends on 1)

The method of claim 1 wherein determining the one or more candidate task sequences that achieve the mission objective comprises, for each candidate task sequence:
determining a final task; and
successively querying a data structure to identify for each task, beginning with the final task, the next predecessor task, if any, until an initial predecessor task in the candidate task sequence is reached.

### Claim 4 (depends on 1)

The method of claim 1 wherein determining the one or more candidate task sequences that achieve the mission objective comprises, for each candidate task sequence:
determining the final task; and
successively querying a task object for the final task and a task object for each predecessor task in the candidate task sequence to determine the next predecessor task, if any, until an initial predecessor task in the candidate task sequence is reached.

### Claim 5 (depends on 1)

The method of claim 1 wherein generating the task allocation tree comprises:
receiving one or more constraints related to the objective; and
generating the task allocation tree based on the candidate task sequences and the received constraints.

### Claim 6 (depends on 1)

The method of claim 1 wherein searching the task allocation tree for a task allocation plan comprises:
calculating costs associated with one or more of the child nodes in the task allocation tree; and
searching the task allocation tree for a lowest cost plan.

### Claim 7 (depends on 6)

The method of claim 6 wherein searching the task allocation tree for a lowest cost plan comprises performing a branch and bound search of the task allocation tree.

### Claim 8 (depends on 6)

The method of claim 6 wherein calculating costs associated with one or more of the child nodes in the task allocation tree comprises computing an initial cost estimate for one or more of the child nodes in the task allocation tree based on a heuristic calculation to reduce processing time.

### Claim 9 (depends on 8)

The method of claim 8 further comprising selecting an initial task allocation plan based on the initial cost estimate.

### Claim 10 (depends on 9)

The method of claim 9 wherein calculating costs associated with one or more of the child nodes further comprises computing a refined cost estimate for one or more child nodes.

### Claim 11 (depends on 10)

The method of claim 10 further comprising selecting or reselecting a task allocation scheme based on the refined cost estimate.

### Claim 12 (depends on 1)

The method of claim 1 wherein generating a task execution plan based on a selected task allocation plan comprises generating, for each of one or more vehicles, at least one of:
a vehicle maneuvering schedule;
a sensor schedule; or
a control schedule for effector controls.

### Claim 13 (depends on 1)

The method of claim 1 wherein further comprising transmitting at least a portion of the task execution plan or control data to one or more of the vehicles to which tasks have been allocated.

### Claim 14

A task allocation system, the task allocation system comprising:
a task sequencing module configured to determine one or more candidate task sequences that achieve a mission objective, each candidate task sequence comprising a plurality of tasks;
a task allocation module configured to:
generate, based on the one or more candidate task sequences, a task allocation tree representing a plurality of potential task allocation plans for allocating the tasks in one or more of the candidate task sequences among one or more autonomous vehicles, wherein:
the task allocation tree comprises a root node and a plurality of child nodes, each of the plurality of child nodes corresponding to a possible allocation of one of the tasks in one of the candidate task sequences to one of the one or more vehicles; and
each task allocation plan comprises a unique path through the task allocation tree from the root node through one or more child nodes to a leaf node; and
search the task allocation tree for a task allocation plan that meets a predetermined selection criterion;
a plan generation module configured to generate a task execution plan based on a selected task allocation plan; and
a plan execution module configured to generate control data for at least one of the vehicles to implement the task execution plan.

### Claim 15 (depends on 14)

The task allocation system of claim 14 wherein the task sequencing module is further configured to, for each candidate task:
determine a final task in at least one candidate task sequence; and
for each candidate task sequence, successively query a data structure to identify for each task, beginning with the final task, the next predecessor task, if any, until an initial predecessor task in the candidate task sequence is reached.

### Claim 16 (depends on 14)

The task allocation system of claim 14 wherein the task sequencing module is further configured to, for each candidate task:
determining a final task in at least one candidate task sequence; and
successively querying a task object for the final task and a task object for each predecessor task in the candidate task sequence to determine the next predecessor task, if any, until an initial predecessor task in the candidate task sequence is reached.

### Claim 17 (depends on 14)

The task allocation system of claim 14 wherein the task allocation module is further configured to:
receive one or more constraints related to the objective; and
generate the task allocation tree based on the candidate task sequences and the received constraints.

### Claim 18 (depends on 14)

The task allocation system of claim 14 wherein the task allocation module is further configured to:
calculate costs associated with one or more of the child nodes in the task allocation tree; and
search the task allocation tree for a lowest cost plan.

### Claim 19 (depends on 18)

The task allocation system of claim 18 wherein the task allocation module is further configured to perform a branch and bound search of the task allocation tree to find the lowest cost plan.

### Claim 20 (depends on 18)

The task allocation system of claim 18 wherein the task allocation module is further configured to compute an initial cost estimate for one or more of the child nodes in the task allocation tree based on a heuristic calculation to reduce processing time.
