Dynamic task allocation in an autonomous multi-UAV mission

• US 10,203,701 B2
• Filed: 11/04/2016
• Issued: 02/12/2019
• 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
• Primary Examiner(s): Khatib, Rami
• Application Number:
  US15/344,014
• Publication Number:
  US 20170131727A1
• Time in Patent Office: 830 Days
• Field of Search: None
• 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 that individual UAV of the plurality of UAVs;

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

execute the respectively determined first task;

monitor the value related to the mission parameter or the physical characteristic of the individual UAV, the monitoring occurring within the individual UAV;

compare the value related to the mission parameter or the physical characteristic with the first criteria, the comparing occurring within the individual UAV;

detect, in the individual UAV, based on the comparing, that the first criteria is satisfied;

autonomously determine for the individual UAV, a second task to be executed by the individual UAV based on satisfaction of the first criteria, the second task different from the first task; and

execute with the individual UAV the determined second task.

2. The system of claim 1, wherein the physical characteristic of the individual UAV of the plurality of UAVs 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 of claim 1, wherein the initial values of the system variables include one or more of a crowd tolerance indicating an acceptable distance between two or more UAVs of the plurality of UAVs, a speed of the individual UAV of the plurality of UAVs, a distance from the ground at which the individual UAV of the plurality of UAVs is to operate, and a search block size.

5. The system of claim 1, wherein each of the plurality of UAVs separately communicates with the 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 that individual UAV of the plurality of UAVs, each of the plurality of UAVs including a processor and communication interface;

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

executing, with the individual UAV, the respectively determined first task;

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

comparing the value related to the mission parameter or the physical characteristic with the first criteria, the comparing occurring within the individual UAV;

detecting, in the individual UAV, based on the comparing, that the first criteria is satisfied;

autonomously determining for the individual UAV, a second task to be executed by the individual UAV based on satisfaction of the first criteria, the second task different from the first task; and

executing with the individual UAV 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 individual UAV, based on the comparing, that the second criteria is satisfied;

determining a third task to be executed by the individual UAV based on satisfaction of the second criteria, the third task different from the first and second tasks; and

executing with the individual UAV the determined third task.

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

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

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 values of the system variables include one or more of a crowd tolerance indicating an acceptable distance between two or more UAVs of the plurality of UAVs, a speed of the individual UAV of the plurality of UAVs, a distance from the ground at which the individual UAV of the plurality of UAVs is to operate, and a search block size.

12. The method of claim 11, wherein determining the second task for the individual UAV comprises adjusting, by the individual UAV, 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 that individual UAV of the plurality of UAVs;

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

execute, with the individual UAV, the respectively determined first task;

monitor the value related to the mission parameter or the physical characteristic of the individual UAV of the plurality of UAVs, the monitoring occurring within the individual UAV;

compare the value related to the mission parameter or the physical characteristic with the first criteria, the comparing occurring within the individual UAV;

detect, in the individual UAV, based on the comparing, that the first criteria is satisfied;

autonomously determine for the individual UAV, a second task to be executed by the individual UAV based on satisfaction of the first criteria, the second task different from the first task; and

execute with the individual UAV the determined second task.

20. The medium of claim 19, wherein the physical characteristic of the individual UAV of the plurality of UAVs 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 values of the system variables include one or more of a crowd tolerance indicating an acceptable distance between two or more UAVs of the plurality of UAVs, a speed of the individual UAV of the plurality of UAVs, a distance from the ground at which the individual UAV of the plurality of UAVs 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 that individual UAV, each of the plurality of UAVs including a processor and communication interface;

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

executing, with the individual UAV, the respectively determined first task;

monitoring the power level of the individual UAV of the plurality of UAVs, the monitoring occurring within the individual UAV;

comparing the power level of the individual UAV of the plurality of UAVs with the first criteria, the comparing occurring within the individual UAV;

detecting, in the individual UAV, based on the comparing, that the first criteria is satisfied;

autonomously determining for the individual UAV, a second task to be executed by the individual UAV based on satisfaction of the first criteria, the second task different from the first task; and

executing with the individual UAV 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 that individual UV of the plurality of UVs, each of the plurality of UVs including a processor and communication interface;

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

executing, with the individual UV, the respectively determined first task;

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

comparing the value related to the mission parameter or the physical characteristic with the first criteria, the comparing occurring within the individual UV;

detecting, in the individual UV, based on the comparing, that the first criteria is satisfied;

autonomously determining for the individual UV, a second task to be executed by the individual UV based on satisfaction of the first criteria, the second task different from the first task; and

executing with the individual UV the determined second task.

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

on ground, in water or under water.