DYNAMIC TASK ALLOCATION IN AN AUTONOMOUS MULTI-UAV MISSION

• US 20170131727A1
• Filed: 11/04/2016
• Published: 05/11/2017
• Est. Priority Date: 11/06/2015
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Kurdi, Heba Abdullatif, How, Jonathan Patrick
• Granted Patent: US 10,203,701 B2
• Time in Patent Office: Days
• CPC Class Codes: 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
• CPC Class Codes: G05D 1/104 involving a plurality of aircrafts, e.g. formation flying traffic control systems for aircraft G08G5/00
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 50/00 Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism healthcare informatics G16H

Abstract

A mechanism for dynamically allocating tasks among multiple UAVs operating autonomously during a mission is discussed. Task assignment is adjusted by each UAV dynamically during the mission based on criteria related to the individual UAV'"'"'s operational status and/or mission parameters. Task allocation is determined independently without group communication between the UAVs actively taking part in the mission and without direct communication to a ground-based controller. A communication UAV provides a shared memory space that may be utilized by each UAV in determining its own task allocation.

Claims

1. A system for dynamically adjusting task allocation for an unmanned aerial vehicle (UAV) during a multi-UAV mission without communication to a ground control station, the system comprising:

a plurality of UAVs to execute tasks, each of the plurality of UAVs having a processor and a communication interface; and

a communication UAV having a processor, a communication interface, and a memory storing a geographic layout representation of a mission environment, each of the plurality of UAVs configured to separately communicate with the communication UAV to receive a status of the mission;

wherein each of the plurality of UAVs is further configured to;

receive initial values for system variables based on mission parameters for the multi-UAV mission and a first and second criteria associated with a task allocation for the UAV,

determine a first task to be executed by the UAV based on an initial comparison of the first criteria and a value related to a mission parameter or a physical characteristic of the UAV;

execute the respectively determined first tasks;

monitor, individually within each of the plurality of UAVs, the value related to the mission parameter or the physical characteristic of the UAV;

compare, individually within each of the plurality of UAVs, the value related to the mission parameter or the physical characteristic with the first criteria;

detect, in at least one of the plurality of UAVs, based on the comparing, that the first criteria is satisfied;

determine for the at least one of the plurality of UAVs, a second task to be executed by the at least one of the plurality of UAVs based on satisfaction of the first criteria, the second task different from the first task; and

execute with the at least one of the plurality of UAVs the determined second task.

2. The system of claim 1, wherein the physical characteristic of the UAV is at least one of a power level, a battery level, and a fuel level.

3. The system of claim 1, wherein the value related to a mission parameter is one of an elapsed mission time or a size of a region explored.

4. The system for claim 1, wherein the initial system variables include one or more of a crowd tolerance indicating an acceptable distance between two or more UAVs, a speed of the UAV, a distance from the ground at which the UAV is to operate and a search block size.

5. The system for claim 1, wherein each of the plurality of UAVs separately communicates with a communication UAV to receive a status of the mission and to receive information stored in a memory of the communication UAV, the information representing a virtual representation of an environment for the multi-UAV mission.

6. A method for dynamically adjusting task allocation for an unmanned aerial vehicle (UAV) during a multi-UAV mission without communication to a ground control station, the method comprising:

receiving at each of a plurality of UAVs in the multi-UAV mission, initial values for system variables based on mission parameters for the multi-UAV mission and a first and second criteria associated with a task allocation for the UAV, each of the plurality of UAVs including a processor and communication interface;

determining, respectively within each of the plurality of UAVs, a first task to be executed by the UAV based on an initial comparison of the first criteria and a value related to a mission parameter or a physical characteristic of the UAV;

executing, with each of the plurality of UAVs, the respectively determined first tasks;

monitoring, individually within each of the plurality of UAVs, the value related to the mission parameter or the physical characteristic of the UAV;

comparing, individually within each of the plurality of UAVs, the value related to the mission parameter or the physical characteristic with the first criteria;

detecting, in at least one of the plurality of UAVs, based on the comparing, that the first criteria is satisfied;

determining for the at least one of the plurality of UAVs, a second task to be executed by the at least one of the plurality of UAVs based on satisfaction of the first criteria, the second task different from the first task; and

executing with the at least one of the plurality of UAVs the determined second task.

7. The method of claim 6, further comprising:

comparing, the value related to the mission parameter or the physical characteristic with the second criteria; and

detecting in the at least one of the plurality of UAVs, based on the comparing, that the second criteria is satisfied;

determining a third task to be executed by the at least one of the plurality of UAVs based on satisfaction of the second criteria, the third task different from the first and second tasks; and

executing with the at least one of the plurality of UAVs the determined third task.

8. The method of claim 6, wherein the physical characteristic of the UAV is at least one of a power level, a battery level, and a fuel level.

9. The method of claim 6, wherein the value of the physical characteristic of the UAV indicates an operating stamina of the UAV.

10. The method of claim 6, wherein the value related to a mission parameter is one of an elapsed mission time or a size of a region explored.

11. The method of claim 6, wherein the initial system variables include one or more of a crowd tolerance indicating an acceptable distance between two or more UAVs, a speed of the UAV, a distance from the ground at which a UAV is to operate and a search block size.

12. The method of claim 11, wherein determining the second task for the at least one of the plurality of UAVs comprises adjusting, by the at least one of the plurality of UAVs, one or more of the initial system variables based on the second task.

13. The method of claim 6, wherein each of the plurality of UAVs separately communicates with a communication UAV to receive a status of the mission and to receive information stored in a memory of the communication UAV, the information representing a virtual representation of an environment for the multi-UAV mission.

14. The method of claim 13, wherein the multi-UAV mission is a Search and Rescue mission and the environment includes regions to search and rescue human survivors, each region including at least two blocks, the status of mission indicating whether particular regions or blocks have been explored.

15. The method of claim 14, wherein the first task is to perform a search of an unexplored block.

16. The method of claim 13, wherein the multi-UAV mission is a Survey and Treat mission, and the environment includes regions in which to survey and treat livestock or crops, each region including at least two blocks, the status of the mission indicating whether particular regions or blocks have been surveyed.

17. The method of claim 13, wherein the multi-UAV mission is an Inspection mission, and the environment includes regions in which to inspect equipment or machinery, each region including at least two blocks, the status of the mission indicating whether particular regions or blocks have been inspected.

18. The method of claim 13, wherein the multi-UAV mission is a Monitoring mission, and the environment includes regions in which to monitor physical objects, each region including at least two blocks, the status of the mission indicating whether particular regions or blocks have been monitored.

19. A non-transitory computer readable medium storing instructions executable by a processing device, the instructions implementing a method for dynamically adjusting task allocation for an unmanned aerial vehicle (UAV) during a multi-UAV mission without communication to a ground control station, execution of the instructions causing a plurality of UAVs to:

receive at each of the plurality of UAVs in the multi-UAV mission, initial values for system variables based on mission parameters for the multi-UAV mission and a first and second criteria associated with a task allocation for the UAV;

determine, respectively within each of the plurality of UAVs, a first task to be executed by the UAV based on an initial comparison of the first criteria and a value related to a mission parameter or a physical characteristic of the UAV;

execute, with each of the plurality of UAVs, the respectively determined first tasks;

monitor, individually within each of the plurality of UAVs, the value related to the mission parameter or the physical characteristic of the UAV;

compare, individually within each of the plurality of UAVs, the value related to the mission parameter or the physical characteristic with the first criteria;

detect, in at least one of the plurality of UAVs, based on the comparing, that the first criteria is satisfied;

determine for the at least one of the plurality of UAVs, a second task to be executed by the at least one of the plurality of UAVs based on satisfaction of the first criteria, the second task different from the first task; and

execute with the at least one of the plurality of UAVs the determined second task.

20. The medium of claim 19, wherein the physical characteristic of the UAV is at least one of a power level, a battery level, and a fuel level.

21. The medium of claim 19, wherein the value related to a mission parameter is one of an elapsed mission time or a size of a region explored.

22. The medium for claim 19, wherein the initial system variables include one or more of a crowd tolerance indicating an acceptable distance between two or more UAVs, a speed of the UAV, a distance from the ground at which the UAV is to operate and a search block size.

23. The medium for claim 19, wherein each of the plurality of UAVs separately communicates with a communication UAV to receive a status of the mission and to receive information stored in a memory of the communication UAV, the information representing a virtual representation of an environment for the multi-UAV mission.

24. A method for dynamically adjusting task allocation for an unmanned aerial vehicle (UAV) during a multi-UAV mission without communication to a ground control station, the method comprising:

receiving at each of a plurality of UAVs in the multi-UAV mission, initial values for system variables based on mission parameters for the multi-UAV mission and a first and second criteria associated with a task allocation for the UAV, each of the plurality of UAVs including a processor and communication interface;

determining, respectively within each of the plurality of UAVs, a first task to be executed by the UAV based on an initial comparison of the first criteria and a power level of the UAV;

executing, with each of the plurality of UAVs, the respectively determined first tasks;

monitoring, individually within each of the plurality of UAVs, the power level of the UAV;

comparing, individually within each of the plurality of UAVs, the power level of the UAV with the first criteria;

detecting, in at least one of the plurality of UAVs, based on the comparing, that the first criteria is satisfied;

determining for the at least one of the plurality of UAVs, a second task to be executed by the at least one of the plurality of UAVs based on satisfaction of the first criteria, the second task different from the first task; and

executing with the at least one of the plurality of UAVs the determined second task.

25. A method for dynamically adjusting task allocation for an unmanned vehicle (UV) during a multi-UV mission without communication to a ground control station, the method comprising:

receiving at each of a plurality of UVs in the multi-UV mission, initial values for system variables based on mission parameters for the multi-UV mission and a first and second criteria associated with a task allocation for the UV, each of the plurality of UVs including a processor and communication interface;

determining, respectively within each of the plurality of UVs, a first task to be executed by the UV based on an initial comparison of the first criteria and a value related to a mission parameter or a physical characteristic of the UV;

executing, with each of the plurality of UVs, the respectively determined first tasks;

monitoring, individually within each of the plurality of UVs, the value related to the mission parameter or the physical characteristic of the UV;

comparing, individually within each of the plurality of UVs, the value related to the mission parameter or the physical characteristic with the first criteria;

detecting, in at least one of the plurality of UVs, based on the comparing, that the first criteria is satisfied;

determining for the at least one of the plurality of UVs, a second task to be executed by the at least one of the plurality of UAVs based on satisfaction of the first criteria, the second task different from the first task; and

executing with the at least one of the plurality of UVs the determined second task.

26. The method of claim 25, wherein the UV is operable in one or more of:

on ground, in water or under water.