UAV decision and control system

• US 8,186,589 B2
• Filed: 01/10/2007
• Issued: 05/29/2012
• Est. Priority Date: 01/11/2006
• Status: Active Grant

• Current Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD., Carmel-Haifa University Economic corp. Ltd. (University of Haifa)
• Original Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD., Carmel-Haifa University Economic corp. Ltd. (University of Haifa)
• Inventors: Ben Asher, Yosef, Feldman, Sharoni, Gurfil, Pinchas
• Primary Examiner(s): ST CYR, DANIEL
• Application Number:
  US12/160,779
• Publication Number:
  US 20100163621A1
• Time in Patent Office: 1,966 Days
• Field of Search: 231/411, 231/412, 231/413, 701/23, 701/25, 701/36, 701/200
• US Class Current: 235/411
• 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 (DAV'"'"'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 can calculate the required velocity and heading independently and each UAV communicates control information comprising flocking data with said UAV'"'"'s closest neighbors only;

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

for communicating attack target list and flocking information both from a root node of a tree comprising one of the UAVs, downstream towards other nodes comprising others of the UAVs in sub-trees depending from the root node and from each node upstream towards the root node;

the root node gathers task assignment and flocking data calculated by the UAVs in the root'"'"'s sub-trees, calculates global functions, task assignment and flocking data for the UAVs in the tree;

the root node distributes said global functions, task assignment and flocking data back to the UAVs in the root'"'"'s 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

independently 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, wherein the system comprises two or more armed UAV'"'"'s, the flocking means, the wireless ad-hoc communications means and the task assignment means.

3. The hierarchical system according to claim 1, wherein the system comprises two or more armed UAV'"'"'s, the flocking means and the task assignment means.

4. The hierarchical system according to claim 1, wherein the system comprises two or more armed UAV'"'"'s, the wireless ad-hoc communications means and the task assignment means.

5. The hierarchical system according to claim 1, wherein the system comprises two or more armed UAV'"'"'s, the flocking means and the wireless ad-hoc communications means.

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 the 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;

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 an independent 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 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 the root'"'"'s sub-trees, calculating global functions, task assignment and flocking data for the tree;

(iii) calculating global functions, task assignment and flocking data for the tree;

(iv) distributing by the root node said global functions, task assignment and flocking data back to the root'"'"'s sub-trees;

(v) improving the overall efficiency of the UAV'"'"'s in the tree in conditions where communication between the UAV'"'"'s is constantly disrupted due to dynamic changes in the field, by a constant flow of upstream and downstream data,

wherein each UAV can calculate the required velocity and heading independently and each UAV communicates control information comprising flocking data with said UAV'"'"'s closest neighbors only.