UAV DECISION AND CONTROL SYSTEM

• US 20100163621A1
• Filed: 01/10/2007
• Published: 07/01/2010
• Est. Priority Date: 01/11/2006
• Status: Active Grant

• Current Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD. (Technion-Israel Institute Of Technology), Carmel-Haifa University Economic corp. Ltd. (University of Haifa)
• Original Assignee: UAB Research Foundation (University of Alabama System), Carmel-Haifa University Economic corp. Ltd. (University of Haifa)
• Inventors: Ben-Asher, Yosef, Feldman, Sharoni, Gurfil, Pinchas
• Granted Patent: US 8,186,589 B2
• Time in Patent Office: Days
• US Class Current: 235/412
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/104 involving a plurality of aircrafts, e.g. formation flying traffic control systems for aircraft G08G5/00

Abstract

The present invention relates to a hierarchical system and method for task assignment (TA), coordination and communication of multiple Unmanned Aerial Vehicles (UAV'"'"'s) engaging multiple attack targets and conceives an ad-hoc routing algorithm for synchronization of target lists utilizing a distributed computing topology. Assuming limited communication bandwidth and range, coordination of UAV motion is achieved by implementing a simple behavioral flocking algorithm utilizing a tree topology for target list routing. The TA algorithm is based on a graph-theoretic approach, in which a node locates all the detectable targets, identifies them and computes its distance to each target. The node then produces an attack plan that minimizes the sum of distances of the UAV'"'"'s in the subtree of a given node to the targets.

Claims

1. A hierarchical multiple UAV decision and control system comprising two or more armed UAV'"'"'s dispatched onto a theater environment in order to search, detect and attack time-critical attack targets, and at least two of the following means:

(i) flocking means based on a behavioral heuristic algorithm wherein said algorithm controls the velocity and heading of the UAV'"'"'s and is configured so that each UAV communicates with its closest neighbors only, and control information comprising flocking data propagates from node to node using a tree management or hierarchical protocol;

(ii) wireless ad-hoc communications means between the UAV'"'"'s as follows;

for communicating attack target list and flocking information both from the root downstream towards other nodes in the sub-trees and from each node upstream towards the root;

the root node gathers task assignment and flocking data calculated by its sub-trees, calculates global functions, task assignment and flocking data for the tree;

the root node distributes said global functions, task assignment and flocking data back to its sub-trees;

in conditions where communication between the UAV'"'"'s is constantly disrupted due to dynamic changes in the field, the constant flow of upstream and downstream data improves the overall efficiency of the UAV'"'"'s in the tree; and

(iii) task assignment means configured so that each UAV, using a graph-theoretic approach, locates all detectable attack targets;

identifies said attack targets;

computes the distance to each of said attack targets; and

produces an attack plan based on system parameters, such that said attack plan optimizes the distances between said UAV'"'"'s to said attack targets.

2. The hierarchical system according to claim 1, comprising:

(i) two or more armed UAV'"'"'s dispatched onto a theater environment in order to search, detect and attack time-critical attack targets;

(ii) flocking means based on a behavioral heuristic algorithm wherein said algorithm controls the velocity and heading of the UAV'"'"'s and is configured so that each UAV communicates with its closest neighbors only, and control information comprising flocking data propagates from node to node using a tree management or hierarchical protocol;

(iii) wireless ad-hoc communications means between the UAV'"'"'s as follows;

for communicating attack target list and flocking information both from the root downstream towards other nodes in the sub-trees and from each node upstream towards the root;

the root node gathers task assignment and flocking data calculated by its sub-trees, calculates global functions, task assignment and flocking data for the tree;

the root node distributes said global functions, task assignment and flocking data back to its sub-trees;

in conditions where communication between the UAV'"'"'s is constantly disrupted due to dynamic changes in the field, the constant flow of upstream and downstream data improves the overall efficiency of the UAV'"'"'s in the tree; and

(iv) task assignment means configured so that each UAV, using a graph-theoretic approach, locates all detectable attack targets;

identifies said attack targets;

computes the distance to each of said attack targets; and

produces an attack plan based on system parameters, such that said attack plan optimizes the distances between said UAV'"'"'s to said attack targets.

3. The hierarchical system according to claim 1, comprising:

(i) two or more armed UAV'"'"'s dispatched onto a theater environment in order to search, detect and attack time-critical attack targets;

(ii) flocking means based on a behavioral heuristic algorithm wherein said algorithm controls the velocity and heading of the UAV'"'"'s and is configured so that each UAV communicates with its closest neighbors only, and control information comprising flocking data propagates from node to node using a tree management or hierarchical protocol; and

(iii) task assignment capabilities configured so that each UAV, using a graph-theoretic approach, locates all detectable attack targets;

identifies said attack targets;

computes the distance to each of said attack targets; and

produces an attack plan based on system parameters, such that said attack plan optimizes the distances between said UAV'"'"'s to said attack targets.

4. The hierarchical system according to claim 1, comprising:

(i) two or more armed UAV'"'"'s dispatched onto a theater environment in order to search, detect and attack time-critical attack targets;

(ii) wireless ad-hoc communications means between the UAV'"'"'s as follows;

for communicating attack target list and flocking information both from the root downstream towards other nodes in the sub-trees and from each node upstream towards the root;

the root node gathers task assignment and flocking data calculated by its sub-trees, calculates global functions, task assignment and flocking data for the tree;

the root node distributes said global functions, task assignment and flocking data back to its sub-trees;

in conditions where communication between the UAV'"'"'s is constantly disrupted due to dynamic changes in the field, the constant flow of upstream and downstream data improves the overall efficiency of the UAV'"'"'s in the tree; and

(iii) task assignment capabilities configured so that each UAV, using a graph-theoretic approach, locates all detectable attack targets;

identifies said attack targets;

computes the distance to each of said attack targets; and

produces an attack plan based on system parameters, such that said attack plan optimizes the distances between said UAV'"'"'s to said attack targets.

5. The hierarchical system according to claim 1, comprising:

(i) two or more armed UAV'"'"'s dispatched onto a theater environment in order to search, detect and attack time-critical attack targets;

(ii) flocking means based on a behavioral heuristic algorithm wherein said algorithm controls the velocity and heading of the UAV'"'"'s and is configured so that each UAV communicates with its closest neighbors only, and control information comprising flocking data propagates from node to node using a tree management or hierarchical protocol; and

(iii) wireless ad-hoc communications means between the UAV'"'"'s as follows;

for communicating attack target list and flocking information both from the root downstream towards other nodes in the sub-trees and from each node upstream towards the root;

the root node gathers task assignment and flocking data calculated by its sub-trees, calculates global functions, task assignment and flocking data for the tree;

the root node distributes said global functions, task assignment and flocking data back to its sub-trees;

in conditions where communication between the UAV'"'"'s is constantly disrupted due to dynamic changes in the field, the constant flow of upstream and downstream data improves the overall efficiency of the UAV'"'"'s in the tree.

6. The hierarchical system according to claim 1, wherein said task assignment capabilities are configured so that:

(i) each node Ui in a tree (or a sub-tree) locates all detectable attack targets, identifies them and computes its distance to each attack target;

the attack target ID is the attack target location;

(ii) at each time step t (i), a node v constructs a weighted bipartite graph B_v[t(i)] representing the distances between each Ui and Tj related to the sub-tree rooted at v;

(iii) three events that lead to the creation of a new bipartite graph B_v[t(i)] include;

(a) a new B_u[t(i+1)], is received from one of v'"'"'s children;

(b) a new, B_Fv[t(i+1)] is received from v'"'"'s father; and

(c) there is a change in the attack target list L of v, as a new attack target is detected or an old attack target disappears or is destroyed;

In each of these events, a new B_v[t(i+1)], is computed by merging B_u[t(i+1)] or B_Fv[t(i+1)] or L into B_v[t(i+1)];

(iv) the node v computes a minimum weighted matching M_v[t(i+1)] of B_v[t(i+1)] obtaining an attack plan that minimizes the sum of distances of the UAV'"'"'s in the sub-tree of v to their attack targets;

$d^{*}=\underset{i,j\in <br><br>B_v<br><br>\left[t<br><br>\left(l+1\right)\right]}{\sum <br><br>}<br><br>d_{\mathrm{ij}}$

(v) when a node v receives an attack plan M_Fv[t(i+1)] from its father, it checks to see if it is assigned a new attack target;

if so, it abandons its current attack target and starts to engage the assigned attack target; and

(vi) the attack plan M_Fv[t(i+1)], is sent to all the children of the current node.

7. The hierarchical system according to claim 1, wherein said system parameters include:

movement vector of each attack target, movement vector of each UAV, types of weapons carried by each UAV, quantity and type of ammunition left for each UAV, future estimated position of each attack target after one or more engagements, future estimated position of each UAV after one or more engagements, and prioritization of attack targets.

8. The hierarchical system according to claim 1, wherein attack targets are identified using a first sensor.

9. The hierarchical system according to claim 8, wherein said first sensor is a Ground Moving Target Indicator radar.

10. The hierarchical system according to claim 1, wherein a second sensor tracks identified attack targets and guides missiles launched against said attack targets.

11. The hierarchical system according to claim 10, wherein said second sensor is an electro-optical sensor.

12. The hierarchical system according to claim 10, wherein attack targets, detected using a first sensor, are attacked at most once within the field-of-view of the second sensor.

13. The hierarchical system according to claim 1, wherein at least one UAV operates autonomously and calculates its own attack target list and route autonomously when said UAV does not have any established communication links with other UAV'"'"'s.

14. The hierarchical system according to claim 1, wherein flocking capabilities include:

cohesion;

alignment;

collision avoidance;

obstacle avoidance; and

migration.

15. The hierarchical system according to claim 1, wherein said wireless ad-hoc communication means use the Metrical Routing Algorithm configured to:

(i) organize all nodes in the field as rooted trees;

(ii) only nodes that belong to the same tree can create sessions among themselves;

(iii) all nodes try to organized themselves in a single tree;

(iv) every node in the field has a unique node ID and virtual coordinates can change depending on the changes in the tree structure;

(v) every tree is identified by the tree name which is the ID of the root node;

(vi) nodes periodically send beacons, every node that receives a beacon checks whether said beacon comes from a node in a different tree; and

(vii) if said beacon comes from a node belonging to a different tree then a fusion process is initiated between the two trees according to a fusion protocol in order to fuse the two trees into a single tree.

16. The hierarchical system according to claim 15, wherein said fusion protocol is configured as follows:

(i) the protocol should not cause active sessions to break;

(ii) all trees with nodes within transmission range of the beacons must fuse into a single tree eventually;

(iii) when two trees are being fused, most updates should be made to the nodes of the tree with the least amount of nodes;

(iv) the highest amount of nodes should be transferred from one tree to the other in each step of the fusion protocol; and

(v) the protocol is fully distributed and defined at the level of pairs of nodes.

17. The hierarchical system according to claim 1 wherein communication between the UAV'"'"'s is constantly disrupted due to dynamic changes in the field.

18. The hierarchical system according to claim 1 wherein at any given time each UAV has a valid task assignment plan.

19. The hierarchical system according to claim 1, wherein optimization of the distances between said UAV'"'"'s to said attack targets is done by minimizing the sum of distances of said UAV'"'"'s to said attack targets.

20. A hierarchical multiple Unmanned Aerial Vehicle (UAV) decision and control system comprising flocking means based on a behavioral heuristic algorithm wherein said algorithm controls the velocity and heading of the UAV'"'"'s and is configured so that each UAV communicates with its closest neighbors only, and control information comprising flocking data propagates from node to node using a tree management or hierarchical protocol.

21. A hierarchical multiple UAV decision and control system comprising task assignment capabilities wherein each UAV, using a graph-theoretic approach, locates all detectable attack targets;

identifies said attack targets;

computes the distance to each of said attack targets; and

produces an attack plan based on system parameters, such that said attack plan optimizes the distances between said UAV'"'"'s to said attack targets.

22. A wireless ad-hoc communications method for communicating between multiple UAV'"'"'s organized in a hierarchical decision tree structure, the method comprising the steps of:

(i) communicating attack target list and flocking information both from the root downstream towards other nodes in the sub-trees and from each node upstream towards the root;

(ii) gathering by the root node task assignment and flocking data calculated by its sub-trees, calculating global functions, task assignment and flocking data for the tree; and

(iii) distributing by the root node said global functions, task assignment and flocking data back to its sub-trees.