Cooperative task assignment of multi-UAV system

Jun ZHANG, Jiahao XING

a School of Electronic and Information Engineering, Beihang University, Beijing 100191, China

b Key Laboratory of Advanced Technology of Near Space Information System (Beihang University), Ministry of Industry and Information Technology of China, Beijing 100191, China

c Advanced Research Institute of Multidisciplinary Science, Beijing Institute of Technology, Beijing 100081, China

KEYWORDS

Abstract With the rapid development of Unmanned Aerial Vehicle(UAV)technology,one of the emerging fields is to utilize multi-UAV as a team under autonomous control in a complex environment. Among the challenges in fully achieving autonomous control, Cooperative task assignment stands out as the key function. In this paper, we analyze the importance and difficulties of multi-UAV cooperative task assignment in characterizing scenarios and obtaining high-quality solutions.Furthermore, we present three promising directions for future research: Cooperative task assignment in a dynamic complex environment, in an unmanned-manned aircraft system and in a UAV swarm. Our goal is to provide a brief review of multi-UAV cooperative task assignment for readers to further explore.

Unmanned Aerial Vehicles (UAVs)have been under development for more than 100 years since the first unmanned aircraft was built in World War I. With the continuous advancement of technology,UAVs are playing an increasingly important role in both civil aviation and military affairs1,such as situation reconnaissance,target surveillance,meteorological monitoring and package delivery.However,due to the increase in the number and complexity of tasks,a single drone with limited size and capability often fails to meet the demands. As a result, multi-UAV are often utilized to cooperate as a team,leading to the rise of multi-UAV autonomous control technology. In general, multi-UAV autonomous control is a kind of complex technology encompassing multiple aspects, including task assignment, path planning and formation control.Multi-UAV cooperative task assignment stands out as an essential component of task accomplishment and UAV autonomous control systems.

Cooperative task assignment is to assign different sub-tasks and their order to each UAV while meeting the task requirements and UAV capabilities. In the past few years, extensive research has been conducted on multi-UAV cooperative task assignment2since the network flow optimization model3was first applied in distributing drones to targets. In addition,many research groups and institutions are working on related projects to implement actual verification experiments on multi-UAV cooperative task assignment. The growing attention in the current field brings out not only opportunities but also significant challenges. The remainder of this paper is devoted to expounding the importance and challenges of multi-UAV cooperative task assignment.

(1)Multi-UAV cooperative task assignment is the first step for UAVs to perform tasks cooperatively

Although UAV autonomous control includes multiple procedures,UAVs will not start to work cooperatively until a feasible and effective task execution plan or strategy is obtained.Multi-UAV cooperative task assignment is a global planning of environment, task requirements, and UAV resources. Efficiency in completing tasks will be significantly improved by a reasonable multi-UAV cooperative task assignment method.For instance, when inspecting an ILS facility at an airport, a flight inspection aircraft must perform several flights to check different subjects4,5.In the case of a large airport with multiple runways and ILS facilities,the flight inspection work takes significant time. By applying the multi-UAV cooperative task assignment method, a couple of UAV-based flight inspection systems can conduct the ILS checking simultaneously with different subjects in different facilities.This can reduce the inspection time significantly.By contrast,if there is no suitable multi-UAV cooperative task assignment plan, the system will reveal drawbacks instead of advantages,as sub-tasks between drones could be contradictory, leading to conflicts or even drone collisions.

(2)One of the crucial points of multi-UAV cooperative task assignment is characterizing real scenarios from different perspectives

These real task scenarios are usually modeled as constraints or objectives in multi-UAV cooperative task assignment. In fact, constraints or objectives are related to not only the limited resources and heterogeneity of UAVs6but also the diversity of task requirements7and complexity of the task environment8. For example, flight distance6,9, communication radius9,10,11and maximum task number6,8,12are three basic constraints considered from the perspective of UAV performance. Meanwhile, task requirements vary greatly from task to task, for example, some tasks are with mobile or unknown targets9,13, while some tasks have temporal relation6,12during completion. Another type of constraints comes mainly from the environment. There may be obstacles14,15and potential dangers8,16,17in the real environment. The constraints may not be all known and static12but may also be unknown9,dynamic10or even adversarial14. Regardless of the difficulty in obtaining solutions, more detailed restrictions will help reproduce more realistic scenes.In some way,a complete characterization of the task scene is the premise to study multi-UAV cooperative task assignment in real scenarios. In addition, a multi-UAV cooperative task assignment plan obtained with a completely characterized scene is practical enough to be carried out in actual multi-UAV autonomous control.

(3) Another crucial point of multi-UAV cooperative task assignment is obtaining high-quality solutions from models and algorithms

In recent years,much attention has been paid to proposing various models and algorithms in the field of cooperative task assignment.Cooperative task assignment has become an interdisciplinary subject that combines control, operations research, and computer science. At present, there are three main types of mathematical models for multi-UAV cooperative task assignment: integer programming, game theory, and Markov decision process. Different models reflect different considerations for the problem. In general, integer programming model is the most intuitive model that can be built,and often seeks to maximize the system benefit. However,game theory models start from maximizing the individual utility of each UAV, which can more effectively deal with the situation of limited communication.On the other hand,Markov decision process considers more about the uncertainty from environment or UAVs.In order to find solutions to these models, researchers are committed to exploring different types of algorithms and their variants, such as mathematical planning16,heuristic algorithms18,19,market-based approaches10,17,and reinforcement learning15,20. Related algorithms can also be classified into two types, centralized and decentralized,based on the communication structure between drones. In solving these problems, computational complexity is always a major concern to obtain better feasible solutions at a faster speed.

Research achievements in multi-UAV cooperative task assignment can be applied to multi-UAV autonomous control and even other control fields. However, there are still numerous challenges in the frontier fields of research and applications. To provide more insights on multi-UAV cooperative task assignment, this paper points out three future directions and related challenges.

(1) Cooperative task assignment in dynamic complex environments: In practical applications, surroundings in which UAVs operate are dynamic and complex, with incidents such as sudden threats, communication interruption, and bad weather. Environmental changes will invalidate an existing cooperative task assignment scheme and raise the need for adjustments. However, the real-time adjustment of the solution has strict requirements for information acquisition,model correction and computational performance, which is difficult to achieve for UAVs with limited resources. At this stage,much literature has been dedicated to achieving solutions that outperform the others in a specific environment.In the future,an adaptive general model and algorithm could be created to organize UAVs to accomplish tasks efficiently under friendly conditions while guaranteeing the completion of tasks under difficult conditions.

(2) Cooperative task assignment in unmanned-manned aircraft systems: Due to the limitations of current UAV capabilities, manned aircraft are still indispensable in performing missions. However, with the development of unmanned aircraft system technology, the relationship between drones and manned aircraft has gradually changed from obedience to collaboration.There are two main difficulties in assigning tasks in unmanned-manned aircraft systems.First,because drones and manned aircraft are different in level of intelligence and autonomy, it is difficult to communicate information effectively between drones and humans. Second, when working with unexpected situations,it is difficult for drones and manned aircraft to make adjustments independently while realizing collaboration. Designing distributed algorithms for unmannedmanned aircraft cooperative task assignment is an active area of research.

(3) Cooperative task assignment in UAV swarms: Among various development trends of UAV technology, the UAV swarm provides an important direction that can perform more complex tasks in a threatening environment. The inspiration for the concept of the UAV swarm is derived from the biomimetic study of insects. The ideal UAV swarm has a variety of attractive advantages such as low cost, large quantity, selforganization and self-healing, leading to a boom of related research. One of the most important problems in cooperative task assignment of a UAV swarm is that the difficulty of obtaining solutions increases rapidly as the number of UAVs increases. Researchers have been working on swarm intelligence algorithms to solve cooperative task assignment problems with a moderate quantity of UAVs6. However, there is still a long way to go before deploying an effective cooperative task assignment method on a real UAV swarm.

Owing to the capability of strong risk tolerance, low manufacturing cost and good maneuverability, UAVs have been widely applied in both military and civil fields. Among the related challenges, multi-UAV cooperative task assignment stands out as a key scientific problem of UAV autonomous control. This paper has elaborated on the importance of multi-UAV cooperative task assignment and pointed out future directions in this area. Autonomous control of UAVs can be fully accomplished only with sufficient attention and effort paid in the direction of multi-UAV cooperative task assignment.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Nos. 61671031, 61722102,91738301).