A resource-constrained distributed task allocation method based on a two-stage coalition formation methodology for multi-UAVs

Abstract

The task allocation problem is an important research field in unmanned aerial vehicles (UAVs). However, most existing task allocation algorithms can form coalitions to address the resources constraints, but cannot support starting tasks at the same time, nor can cope with the new emerging tasks flexibly. To this end, we propose a novel resource-constrained task allocation method based on the performance impact algorithm (RCPIA) to support simultaneously starting tasks and provide more flexibility to reallocate the new tasks. More specifically, based on the proposed task allocation model, we firstly modify the task inclusion phase and conflict resolution phase of the baseline PI algorithm to preferentially allocate the tasks to the UAVs that can complete tasks individually. After that, to make full use of resources and further allocate remaining unassigned tasks, a two-stage coalition formation method is creatively proposed to form a coalition for the tasks that cannot be performed by a single UAV to provide enough resources. Especially, an idle time slot mechanism (ITSM) is investigated to shift the start times of tasks that can be performed by a single UAV to create a longer feasible time slot to insert the task. Thirdly, the reassignment application of the two-stage coalition method is introduced to cope with new emerging tasks. Finally, numerical simulations are constructed to illustrate the procedure of RCPIA and verify the superiority of RCPIA compared with other task allocation algorithms in efficiency and success allocation rate.

1 Introduction

A multiple unmanned aerial vehicles (multi-UAV) system is a set of UAVs that are designed to cooperate with each other to complete some complex missions [22, 30, 32]. The advantages of multi-UAV system lie in increased flexibility, enhanced reliability and resilience, simultaneous broad area coverage or capability to operate outside the communication range of base stations [5, 24, 40]. Hence, multi-UAV systems have been applied to many real-world scenarios [21, 43].

Task allocation means assigning a set of tasks to UAVs without conflicts and constraints violation while optimizing some objective function [36, 45]. Hence, the solution that does not violate constraints is vital to improve the performance of completing complex missions [11]. Much research has studied dealing with complex constraints in problems, such as the constraints of limited resource, resource type, time windows and reassignment version in dynamic environment [20, 38].

However, there are many challenges that exist in addressing the complex constraints of multi-UAV systems task allocation [36, 45]. In real-world, the resources carried by heterogeneous UAVs are diverse and limited, while the tasks also may require different types of resources. In addition to the resource type constraints, we hope to make full use of the limited heterogeneous resources of UAVs to further allocate more tasks. Hence, it is allowed to select a group of UAVs to cooperatively provide enough resources for executing one task. Besides, due to the military requirement, some tasks must be started at the same time to guarantee the task completion performance. Since starting tasks at the same time will affect the start time of other tasks in the task list, which may cause the objection function of the solution to decrease. Therefore, it is necessary to develop approaches that form a group of UAVs to provide enough resources for tasks and cooperatively start a task at the same time without much objective function loss. Moreover, the new emerging tasks may have a greater impact on the coalition UAVs than single UAV. Once the task list of a coalition UAV is interrupted by the new task, other coalition member UAVs must wait for its arrival. This will cause the allocated tasks cannot be performed on time or not be executed. Hence, how to provide a feasible and flexible solution in a dynamic environment within a short time is much worth studying.

To this end, we focus on the distributed task allocation problem where heterogeneous UAVs are allocated to several tasks with resource-type constraints and the simultaneous starting tasks should also be supported. In this paper, it is preferred to avoid unnecessary cooperation of UAVs and alleviate the impact of new emerging tasks on preallocation solutions. Also, to provide greater flexibility, more redundant time should be fully utilized to create feasible time slots by shifting the start times of a single UAV executing tasks. Therefore, we propose a novel resource-constrained task allocation algorithm based on the performance impact algorithm (RCPIA). In detail, this paper makes the following contributions to the state of the art:

• The task assignment problem with resources type constraints and limited quantity constraints is modeled in the mathematical formulation. Besides, the requirement of starting coalition tasks concurrently is also taken into consideration.

• To avoid unnecessary cooperation, it is first preferred to allocate a single UAV with sufficient resources to the tasks, rather than form a coalition to complete tasks to obtain a higher reward. To this end, this paper first modifies the criteria of adding tasks and removing tasks to allocate the tasks to the UAVs with enough resources which can complete them individually as much as possible. Then, the conflict resolution rules are also modified to meet the resource constraints.

• To further make full use of UAV resources, a two-stage coalition formation method is introduced to further allocate the tasks that cannot be performed by a single UAV. First, in the first stage, the UAVs that can provide the required resources for the task and meet the deadline constraints are selected as preliminary coalition members. It’s worth noting that we propose an idle time slot mechanism (ITSM) to compute the feasible time slot for the UAV to insert the task. This mechanism can calculate the start time redundancy for the current coalition task without affecting the start times of other coalition tasks in the task list. After selecting preliminary coalition members, the second stage is used to further reduce the coalition size based on three different criteria and the final coalition members are obtained.

• In order to cope with the new emerging tasks in a dynamic environment, the reassignment application of the two-stage coalition formation method is investigated.

The rest of the paper is organized as follows. In Sect. 2, we overview the previous works related to the task allocation problem of multi-UAV systems. Section 3 introduces the resource-based multi-UAV task allocation problem and gives its mathematical formulation. The main structure of RCAPI is illustrated in Sect. 4. Several simulations and comparisons are conducted in Sect. 5 to demonstrate the performance of the RCAPI. Section 6 concludes this paper.

2 Related work

There have been numerous studies on the task allocation problem of multi-UAV systems and many methods are proposed for the past few years. Generally, they are categorized into two main categories: optimized-based and market-based [3].

Many optimized-based methods are proposed to find the optimal solution. For example, ant colony algorithm (ACO) [34, 46] and practical swarm optimization (PSO) [25, 28] were developed due to their fast convergence speed in solving large-scale task allocation problems. Besides, as a typical optimization-based approach, genetic algorithm (GA) is also one of the most useful methods to solve task assignment problem when the search space is not extremely rugged in the presence of many types of constraints [45]. Many algorithms are incorporated into GA to improve the efficiency or avoid the local optimum. In [35], the improved simulated annealing algorithm (SA) was used in the second selection operation to improve the population diversity of GA. [37] proposed a multi-objective shuffled frog-Leaping algorithm (MOSFLA) and GA-based task assignment and sequencing method which showed that the total operation time shrinks. However, since optimized-based algorithms are difficult to design appropriate local decision rules, they are usually used in centralized systems. This places a heavy communication burden on the server and also reduces the mission range. In addition, they are vulnerable to the single point of failure and are easy to fall into local optimum.

Hence, as a typical distributed approach, the market-based algorithm [29, 31, 41, 44] has been applied to achieve a suboptimal solution due to its low computation complexity, efficiency, robustness, and scalability. Recently, the consensus-based bundle algorithm (CBBA) has attracted considerable research interest since it combines the positive properties of the auction and conflict resolution to produce a conflict-free assignment [8]. It has been proven that this method can offer similar solutions to some centralized sequential greedy algorithms and 50% optimality is guaranteed. Several researches made modifications and extensions based on CBBA [27, 38], and several algorithms were also inspired from it [13, 33, 46] which also performed well in solving task allocation problems. Besides, many other algorithms were also applied to solve such problems, see [1, 2, 12, 18, 19, 26].

For dealing with resource constraints, [17] adopted cross-entropy (CE) to address the resource required by tasks and demonstrated its effectiveness. A greedy heuristic was introduced in [42], which considered inter-task resource constraints to approximate the influence between different assignments in task allocation. [23] proposed a distributed task allocation method based on resource welfare by balancing resource depletions. [10] designed a modified genetic algorithm with multi-type genes for the task assignment with limited resources and kinematic constraints. However, the aforementioned algorithms just considered assigning one task to one UAV, which can not make full use of the resources of heterogeneous UAVs.

At the same time, most existing works studied forming coalition UAVs to cooperatively complete tasks, which aims to obtain a better solution compared to assigning one UAV to one task [9, 14, 39], and only a few studies considered both resource constraint and coalition formation. For example, [7] introduced a holistic coalition methods for global optimization and a sequential coalition method to select suitable robots to form coalitions for the dynamic events. Similarly, a leader-follower coalition methodology (LFCM) for solving resource constraints was discussed in [6]. Nevertheless, these two methods were both applied in a centralized way and did not consider the constraints of simultaneously starting tasks. In addition, they cannot allocate the new tasks in real-time. [4] proposed a coalition formation method based on game theory (CFGT) to provide enough resources for tasks. Similarly, this method also cannot start tasks at the same time. [13] proposed a resource dynamic assignment algorithm inspired by CBBA based on task sequence mechanism (RDAATSM) and the simulation verified that the algorithm can assign new tasks with limited resources online. The task sequence mechanism can insert the new tasks into its task list without affecting the allocated tasks. To perform tasks in the shortest time and occupy fewer UAVs resources, RDAATSM forms coalitions for each task and there is synchronous waiting time generated to ensure the task can be started at the same time. However, this may lead to three troubles. The first is that only inserting the new tasks into the idle period (synchronous waiting time) will reduce the flexibility and success rate to allocate new tasks since the preallocated start times are not allowed to change. The second is that if the assigned task encounters dynamic events (such as the task execution time extends, the last task is delayed, the task disappears, etc.), these dynamic events have a greater impact on the task execution of subsequent tasks for all coalition UAVs than on the UAV executing the task independently. As for the third weakness, it is known that the CBBA algorithm must meet the marginal diminishing characteristics of the task reward during the bundle construction phase. Therefore, RDAATSM is designed to assign the most resources to the tasks with the greatest reward, which means that this algorithm first selects tasks to insert according to the greatest reward then according to the provided resources. This will lead to more tasks being performed by a coalition rather than a single UAV. In brief, we provide a comparative analysis of five typical task allocation algorithms, which are PI ( [43]), cross-entropy (CE) [17], Leader-Follower Coalition Methodology (LFCM) ( [7]), coalition formation method based on game theory (CFGT)( [4]) and Resource Dynamic Assignment Algorithm Based on Task Sequence Mechanism (RDAATSM) ( [13]). Comparison are analyzed from: (i) resource constraints; (ii) dynamic assignment; (iii) implementation way; (iv) simultaneous start; and (v) objective. The comparative analysis is summarized in Table 1.

Hence, this paper investigates a distributed algorithm to solve the task allocation problem with constraints of resource and simultaneous start. In addition, this algorithm should be flexible to address the new emerging tasks in a dynamic environment by slightly changing the original task allocation scheme.

Table 1 Comparative characteristics of previous works

3 Problem description

Consider a scenario where $N_u$ heterogeneous UAVs ${\mathbf {V}}={{[{{v}_{1}},\ldots ,{{v}_{N_u}}]}^{T}}$ are allocated to execute $N_t$ heterogeneous tasks ${\mathbf {T}}={{[ {{t}_{1}},\ldots ,{{t}_{N_t}}]}^{T}}$, with $N_t>N_u$. Heterogeneous tasks are distinguished by the number of different resources required by the task. A task allocation solution ${\mathbf {A}}={{[ {{{\mathbf {a}}}_1},\ldots ,{{{\mathbf {a}}}_{N_u}} ]}^{T}}$ consists of the assignments for all UAVs, where ${{\mathbf {a}}_{i}=[t_{i1},\ldots ,t_{i|{\mathbf {a}}_i|}}], i=1,\ldots ,N_u$ is the task list assigned to UAV ${{v}_{i}}$ and is ordered by the actual start time of assigned tasks. The size of a task list ${{{\mathbf {a}}}_i}$ is decided by the number of tasks assigned to ${{v}_{i}}$. In addition, each task has a latest start time (deadline) ${\mathbf {S}}={{[{{s}_{1}},\ldots ,{{s}_{N_t}}]}^{T}}$. ${\mathbf {G}}{(t)}$ denotes a symmetric communication matrix, where $g_{i,j}(t)=1$ indicates that UAV $v_i$ can directly communicate with UAV $v_j$ at time t and we denotes the UAVs as neighbors. A list of key symbols used is provided in Table 2.

Table 2 Symbol Definitions

3.1 Resource modeling

• (1) The UAV is a physical entity with given resource capabilities that can be used to process tasks. A resource is a measurable physical or virtual entity used in the processing of tasks. Denote the resources vector $R_i^U$ on UAV $v_i$ as follows:

  $$\begin{aligned} R_i^U=[R_{i1}^U,\ldots ,R_{iM}^U] \end{aligned}$$

  (1)

  where $R_{ip}^U,p=1,\ldots ,M$ denotes the amount of the pth type resource carried by UAV $v_i$ and M is the number of supplied resource types. For example, $R_i^U=[2,0,1]$ means that UAV $v_i$ carries two Resource 1 and one Resource 3, and does not carry Resource 2 or Resource 2 has been used up. It is noted that the resources carried by UAVs will constantly be consumed as the tasks are processed.

• (2) The tasks are derived by decomposing a high-level task and are activities that require relevant resources that will be provided via UAVs. Denotes $R_i^T$ as the required resources for completing task $t_i$ as follows:

$$\begin{aligned} R_i^T=[R_{i1}^T,\ldots ,R_{iN}^T] \end{aligned}$$

(2)

where $R_{iq}^T,q=1,\ldots ,N$ denotes the number of the qth type of resources required by task $t_i$, and N represents the number of types required by the task. For simplicity, $M=N$ is adopted in this paper.

Fig. 1

The relationship between the resources, tasks and UAVs

In order to complete the task $t_i$, it is required that the assigned coalition (maybe a single UAV) must provide all types and enough amounts of resources required by the task. The relationship between the resources, tasks and UAVs is shown in Fig. 1.

3.2 Utility function

In order to achieve a feasible solution, the overall optimization objective is defined as follows:

$$\begin{aligned} max\{J=\sum _{i=1}^{N_u}\sum _{j=1}^{N_T}X_{i,j}\frac{s_j-\tau _{ij}}{s_j}SV_j\eta _{ij}\} \end{aligned}$$

(3)

subject to:

$$\begin{aligned} \begin{aligned}&\sum _{i=1}^{N_u}X_{i,j}R_{ik}^U\ge R_{jk}^T, \forall j\in T, \forall k\in N\\&X_{i,j}\tau _{ij}\le s_j, \forall j\in T \\&\tau _j=X_{i,j}\tau _{ij}, \forall j\in T\\&X_{i,j}\in \{0,1\}, \forall (i,j)\in V\times T \end{aligned} \end{aligned}$$

(4)

where$X_{i,j}$ denotes whether UAV $v_i$ is assigned to task $t_j$. The static reward $SV_j$ is defined as the contribution of completely completing the task to the overall goal, and we can also regard the static reward as the inherent importance of the task $t_j$. A linear time-discount strategies is used here to indicate the effect of start time on task reward. $\eta _{ij}$ is defined as the contribution proportion, i.e., the ration of the number of resources that UAV $v_i$ can provide to the number of resources required by the task $t_j$. The constraints described in Eq. (4) means as follows: the resources that UAVs provide must cover the task required resources, the actual start time of a task must not be later than its deadline, the coalition for a task must start the task at a same time.

The actual start time $\tau _{ij}$ is computed as Eq. (5) based on the order of task execution in task list ${\mathbf {a}}_i$,

$$\begin{aligned}&\tau _{ij}=\tau _j=\max _{i=1}^{|C_j|}{\tau _{ij}^*},v_i\in C_j \end{aligned}$$

(5a)

$$\begin{aligned}&\tau _{ij}^*= {\left\{ \begin{array}{ll} d_{i,o,j}^T,& \quad {} j=1\\ \tau _{i(j-1)}+d_{j-1}^E+d_{i,j-1,j}^T,& \quad {} 1<j\le |{\mathbf {a}}_i| \end{array}\right. } \end{aligned}$$

(5b)

$$\begin{aligned}&\tau _{ij}=\tau _{ij}^*+d_{i,j}^W \end{aligned}$$

(5c)

where $d_{i,o,j}^T$ denotes the travel time from the initial location to the first task in ${\mathbf {a}}_i$ for $v_i$ and $d_{i,j}^W$ denotes the waiting time of UAV $v_i$ to task $t_j$. $d_j^E$ represents the execution time for performing $t_j$. $\tau _j$ represents the actual start time for task $t_j$ and $\tau _{i,j}^*$ denotes the actual arrival time for $v_i$ to $t_j$.

If task $t_j$ is assigned to a coalition $C_j$, in order to guarantee the performance of task completion, the UAV needs to wait for all other members of the coalition to arrive before they can start to execute the task. Hence, Eq. (5a) shows that the time cost of $v_i$ starting $t_j$ is equal to the maximum arrival times for all UAVs in coalition $C_j$ and this maximum arrival time is also regarded as the real start time for the task $t_j$. Eq. (5b) means that the arrival time for UAV $v_i$ to reach task $t_j$ is computed as the sum of the travel times and execution times of all previous tasks. It is noted that time costs are cumulative so that the cost of servicing task ${{t}_{j}}$ includes the time cost of servicing all the tasks previous to it in the task list. Eq. (5c) demonstrates the relationship between the actual start time and arrival time for $v_i$ to $t_j$. It is noted that, if task $t_j$ is assigned to a single UAV $v_i$, the UAV starts $t_j$ as soon as it arrives at $t_j$, i.e., $\tau _{j}= \tau _{ij}=\tau _{ij}^{*}$. The schematic representation of time cost is expressed in Fig. 2, where $v_k$ is the last UAV to reach $t_j$.

Fig. 2

The relationship between the execution time, travel time and waiting time

The contribution proportion $\eta _{ij}$ is defined as the ration of the number of resources that UAV $v_i$ can provide to the number of resources required by the task $t_j$ as follows:

$$\begin{aligned} \eta _{ij}=\frac{\sum _{k=1}^{M}min({R_{ik}^U},{R_{ik}^T})}{\sum _{k=1}^{M}R_{ik}^T} \end{aligned}$$

(6)

For example, when task $t_j$ requires the resources $R_j^T=[0,3,1]$ and UAV $v_i$ carries the resources $R_i^U=[1,3,2]$, $t_j$ can be completed by $v_i$ individually, i.e., $\eta _{ij}=1$. If $R_i^U=[0,2,0]$, then $v_i$ can only contribute two resources of four resources required by $t_j$ and $\eta _{ij}$=0.5.

4 Proposed method

In order to address the resource constraints on heterogeneous UAVs in a distributed way, we propose a resource-constrained task allocation method based on the performance impact algorithm (RCPIA) by modifying the criteria to include and remove tasks in [43] and introducing a two-stage coalition formation method. The main program of RCPIA is described as Algorithm 1.

In more detail, after initializing the mission environment, all UAVs first communicate with neighbors to achieve consensus regarding the winning UAVs and winning RPIs for all tasks (line 4). Then, for each UAV, the conflict resolution phase is first carried to remove the conflict tasks (line 6) and the task inclusion phase is followed to further include more tasks into the task list until no more tasks can be included (line 7). After all, UAVs have completed a cycle of these two phases, if no more tasks can be swapped among all UAVs to maximize the total score, the algorithm ends. Otherwise, a new communication is triggered again. So far, a conflict-free and feasible solution has been obtained. Some tasks are assigned to the UAVs that can complete them individually. In addition, the leaders which can provide the most resources for the tasks that cannot be performed by a single UAV are also obtained. Then, the two-stage coalition formation method is followed to form a coalition for the tasks that cannot be completed by a single UAV (line 12).

4.1 Main structure

4.1.1 Task inclusion phase

During the task inclusion phase, every UAV tries to include tasks into its task list until no more tasks can be included or no more resources are left based on the knowledge of the resource requirements for all tasks. At the beginning of RCPIA, the task list ${\mathbf {a}}_i$, local RPI list $W_i^{\ominus }$, global winning UAV list $\pmb {\beta }_i$ and global winning contribution proportion list $\mho _{i}^{\diamond }$ for all UAVs are initialized as empty and set as the initial inputs of RCPIA. Once the conflict resolution has been carried, the inputs change to the conflict-free outputs of the resolution phase. It is noted that, since this phase is locally carried by each UAV, the output solution is maybe conflicting. The pseudo-code of this phase is shown in Algorithm 2.

• Step 1(lines 2–7) At the beginning, the contribution proportion $\eta _{ij}$ for each task is also computed by Eq. (6).

  Then, the inclusion performance impact (IPI) is defined to measure the newly added task’s local performance impact generated by the UAV. It is defined as the greatest difference in the score (with and without the added task) of the added task and subsequent tasks for all possible insert positions. Every UAV computes the IPIs for all tasks as shown in Eqs. (7) and (8) (line 5):

  $$\begin{aligned} w_{i,k,l}^{\triangle }= \,& {} {{u}_{i,k}}\left( {{{\mathbf {a}}}_i}{{\oplus }_{l}}{{t}_{k}} \right) +\sum \limits _{r=l}^{\left| {{{\mathbf {a}}}_i} \right| }{\left( {{u}_{i,r+1}}\left( {{{\mathbf {a}}}_i}{{\oplus }_{l}}{{t}_{k}} \right) -{{u}_{i,r}}\left( {{{\mathbf {a}}}_i} \right) \right) } \end{aligned}$$

  (7)
  $$\begin{aligned} w_{i,k}^{\oplus }= \,& {} \underset{l=1}{\overset{\left| {{{\mathbf {a}}}_i} \right| +1}{\mathop {\max }}}\,\left\{ w_{i,k,l}^{\triangle } \right\} \end{aligned}$$

  (8)

  where ${\mathbf {a}}_i\oplus _lt_k$ denotes adding the task $t_k$ into the task list ${\mathbf {a}}_i$ of UAV $v_i$ at l position. When the task has been included in ${\mathbf {a}}_i$ or the UAV cannot provide enough resources required by the task, the IPI is set to 0. A local IPI list $W_i^{\oplus }=[w_{i,1}^{\oplus },\ldots ,w_{i,N_t}^{\oplus }],i=1,\ldots ,N_u$ is designed to store the IPIs of UAV $v_i$ including all tasks.

  It is known that completing a new task which inserted in the UAV’s task list can increase the local score of the UAV. However, the time costs of subsequent tasks in the task list may be delayed since subsequent tasks need to be shifted to create enough time to execute the new task. From Eq. (2), the delay time costs of subsequent tasks may lead to the decrease of the local scores of the UAV performing subsequent tasks. Hence, as shown in Eq. (7), the local performance impact $w_{i,k,l}^{\Delta }$ of inserting $t_k$ into position l of ${\mathbf {a}}_i$ is defined as the local score of $v_i$ executing $t_k$ plus the sum of decrease in local scores of other tasks in ${\mathbf {a}}_i$ that have been assigned previously. Eq. (8) selects the maximum local performance impact for all possible positions as the IPI ${{w}_{i,k}^{\oplus }}$ of task $t_k$ in ${\mathbf {a}}_i$.

• Step 2 (lines 8–9) The contribution proportions for all tasks are stored in a local contribution proportion list $\mho _{i}=[\eta _{i1},\ldots ,\eta _{iN_t}]$. In order to avoid unnecessary coordination and communication, it is preferred to allocate the task to a single UAV rather than a coalition. Hence, the tasks with the highest contribution proportion and positive IPI are selected as the candidate tasks set to add, i.e., $T_i^A$, as Eq. (9):

  $$\begin{aligned} T_i^{A}=\{t_k|\arg \max _{k=1}^{N_t}\eta _{ik}\} \end{aligned}$$

  (9)

• Step 3 (lines 10–16) If $|T_i^A|=1$, the task $t_g$ with the highest contribution degree is selected to be inserted into the task list ${\mathbf {a}}_i$ (line 11) and goes to Step 4.

However, if there are more than one tasks in $T_i^A$, i.e., $|T_i^A|>1$, the task with the highest improvement for the global objective is selected to add to the task list. However, if the task has been previously assigned to a UAV, the performance impact of adding it should not only consider the IPI but also consider the local impact of removing the task from the previously assigned task list.

The RPI is introduced to measure the performance impact of removing a task and is defined as the greatest difference in the score (with and without the added task) of the deleted task and subsequent tasks as Eq. (10):

$$\begin{aligned} w_{i,k}^{\ominus }={{u}_{i,b}}\left( {{{\mathbf {a}}}_i} \right) +\sum \limits _{r=b+1}^{\left| {{{\mathbf {a}}}_i} \right| }{\left( {{u}_{i,r}}\left( {{{\mathbf {a}}}_i} \right) -{{u}_{i,r}}\left( {{{\mathbf {a}}}_i} \ominus {t_k}\right) \right) } \end{aligned}$$

(10)

where ${\mathbf {a}}_i \ominus {t_k}$ denotes the removal of task $t_k$ from the task list ${\mathbf {a}}_i$ of UAV $v_i$, and b symbolizes the position of task $t_k$ in the task list, i.e., $a_{i,b}=t_k$.

Although removing a task from the task list will cause the loss of the local score of UAV performing the removed task, the start times of subsequent tasks will be advanced due to removing the task. The local scores of subsequent tasks will be increased from Eq. (3). Hence, as shown in Eq. (10), the RPI of removing task $t_k$ from ${\mathbf {a}}_i$ is computed as the loss of executing the removed task $t_k$ plus the increased local scores of subsequent tasks in task list ${\mathbf {a}}_i$. It represents the contribution of a task to the local score generated by a UAV.

The RPIs of all unassigned tasks are initialized as 0. Hence, the RPI must be greater than 0 once be assigned. The RPIs of all tasks for UAV $v_i$ are stored in a local RPI list $W_i^{\ominus }=[w_{i,1}^{\ominus },\ldots ,w_{i,N_t}^{\ominus }],i=1,\ldots ,N_u$. To facilitate consensus, defines a local winning UAV list $\pmb {\beta }_i=[\beta _{i,1},\ldots ,\beta _{i,N_u}]^T$ to represent which UAV is assigned to which task for UAV $v_i$’s the local view, and $\beta _{i,k}$ is set as the ID of the UAV assigned to task $t_k$.

Based on the definitions of RPI and IPI, it can be inferred that the global score can be improved by reallocating $t_k$ to UAV $v_i$ if the IPI of task $t_k$ in ${\mathbf {a}}_i$ is higher than $t_q$’s RPI in another UAV’s task list ${\mathbf {a}}_j$. Therefore, decide which task can be inserted into the current the current task list ${\mathbf {a}}_i$ of $v_i$ according to Eq. (11).

$$\begin{aligned} g=\mathrm{max}_{k=1}^{T_i^A}\left\{ w_{i,k}^{\oplus } -w_{i,k}^{\ominus } \right\} \end{aligned}$$

(11)

If $g>0$, the task $t_g=\arg \max _{k=1}^{T_i^A}\left\{ w_{i,k}^{\oplus } -w_{i,k}^{\ominus } \right\}$ with the greatest difference of IPI and RPI in current candidate tasks set, i.e., the task can provide the greatest objective improvement, should be selected to insert into ${\mathbf {a}}_i$ at the position $l_{t_g}^{i}=$arg$w_{i,k}^{\oplus }$. If $g\le 0$, IPIs of all tasks are equal or lower to the current RPIs, which means that the current assignment cannot be improved or the constraints cannot be met. In this case the task inclusion phase ends.

Step 4 (lines 17–18) The final RPI is set equal to the IPI. In addition, the local RPI list $W_i^\oplus$, the global winning RPI list $W_i^\oplus \diamond$, winning UAV list ${\varvec{\beta }}_i$, remaining resources of UAV $R_i^U$ and global winning contribution proportion list $\mho _{i}^\diamond$ are updated. Repeat this inclusion process until no more tasks can be included.

4.1.2 Communication

Because every UAV locally builds its own task list, two or more UAVs may have a conflict with the winning UAV for each task. To this end, all UAVs must communicate with other UAVs to achieve the consensus on the global winning UAVs, global winning RPIs, and global winning contribution proportions for all tasks.

First, all UAVs communicate with each other where a communication link exists between them based on a network topology to transmit some fundamental information, i.e., the local RPI list $W_i^{\ominus }$, winning UAV list $\pmb {\beta }_i$, the local contribution proportion list $\mho _{i}$ and time stamps $TS_i$ that stores the iteration numbers of the last information update from each of the other UAVs.

Then, after receiving the information from other UAVs, the receiver UAV uses the consensus procedure to achieve global consensus in terms of the aforementioned four lists. In detail, the receiver can determine three types of operation shown in Eq. (12) (update, leave and reset) by evaluating four lists with a decision rule table referred to the Appendix Table 11. For example, when $v_i$ receives information about task $t_k$ from sender $v_j$, three possible actions are displayed as follows:

$$\begin{aligned} \begin{aligned}&\mathrm{Update}: \beta _{i,u}=\beta _{j,u}, w_{i,u}^{\ominus \diamond }=w_{j,u}^{\ominus \diamond },\eta _{i,u}^{\diamond }=\eta _{j,u}^{\diamond }\\&\mathrm{Reset}: \beta _{i,u}=0, w_{i,u}^{\ominus \diamond }=\phi ,\eta _{i,u}^{\diamond }=0 \\&\mathrm{Leave}: \beta _{i,u}=\beta _{i,u}, w_{i,u}^{\ominus \diamond }=w_{i,u}^{\ominus \diamond },\eta _{i,u}^{\diamond }=\eta _{i,u}^{\diamond } \end{aligned} \end{aligned}$$

(12)

Since the tasks are preferred to allocate to the UAV with a higher contribution proportion, the contribution proportion is firstly compared and the UAV with the higher contribution proportion is selected as the winner UAV. When multiple UAVs can provide the same contribution proportion, the RPI value is utilized to further select the winning UAV, which means that the UAV with a higher RPI becomes the winner UAV.

After updating the winner UAV, the global winning contribution proportion and RPI for the task are also updated. It is noted that the consensus of the global winning RPI list and global winning contribution proportion list are additionally stored in $W_i^{\ominus \diamond }$ and $\mho _{i}^{\diamond }$ respectively, while $\pmb {\beta }_i$ held by $v_i$ is directly updated. The local winning RPI list $W_i^\ominus$ and local winning contribution proportion list $\mho _i$ remain unchanged in each communication process.

4.1.3 Conflict resolution phase

Since every UAV locally builds its own task list, two or more UAVs may include the same task. Hence, a conflict resolution phase is demonstrated in Algorithm 3 to resolve the conflict. Take the outputs of task inclusion phase as the inputs and a conflict-free solution is obtained as output in this phase.

• Step 1 (line 1) After communication procedure, the consensus of the global winning UAV list $\pmb {\beta }_i$, global winning RPI list $W_i^{\ominus \diamond }$ and global winning contribution proportion list $\mho _{i}^{\diamond }$ have been achieved and are now ready to determine if any tasks in the task list should be removed. The candidate tasks set $T_{i}^R$ to remove from the task list ${\mathbf {a}}_i$ is determined by Eq. (13):

  $$\begin{aligned} T_{i}^R=\{ {\mathbf {a}}_i|\mathbf {\pmb {\beta }}_i({\mathbf {a}}_i)\ne v_i \} \end{aligned}$$

  (13)

  In detail, each UAV $v_i$ checks the winning UAVs of all assigned tasks, and the tasks whose winning UAV is not $v_i$ itself, i.e., $\pmb {\beta }_i({\mathbf {a}}_i)\ne v_i$, are regarded as the conflict tasks.

• Step 2 (lines 3–7) Since a higher contribution proportion implies a better assignment, the UAV with a lower contribution proportion for the conflict task should remove the task from its task list. The globally identical winning contribution proportion list $\mho _{i}^{\diamond }=[\eta _{i1}^{\diamond },\ldots ,\eta _{iN_t}^{\diamond }]$ are iteratively compared with the local contribution proportion list $\mho _{i}=[\eta _{i1},\ldots ,\eta _{iN_t}]$. For all tasks in $T_i^R$, the criterion Eq. (14) is computed:

  $$\begin{aligned} h=\max _{k=1}^{|T_i^R|}\{ \eta _{ik}^{\diamond }-\eta _{ik} \} \end{aligned}$$

  (14)

  here $h>0$ means that reallocating $t_k$ from $v_i$ to the corresponding UAV winner $\beta _{i,k}$ can improve the contribution proportion of task $t_k$, i.e., the winner $\beta _{i,k}$ can provider more required resources by $t_k$ than UAV $v_i$. Hence, if $h<0$ there are no tasks can be released to provide more resources to the tasks in $T_i^R$ and the conflict resolution phase ends.

• Step 3 (lines 8–13) If there is only one task with h, then the task is selected to be removed from the task list ${\mathbf {a}}_i$ and $T_i^{R}$ (line 9), and goes to Step 4. Otherwise, when there are two or more tasks with same h, a temporary conflict tasks set $T_i^{R'}$ is defined to stores the tasks with same h, and goes to Step 3 to further select task to delete.

  $$\begin{aligned} T_i^{R'}=[t_k|\arg h,t_k\in T_i^{R}] \end{aligned}$$

  (15)

  In order to select a specific task with the greatest objective improvement when the contribution proportions are same for multiple tasks, the global winning RPI list $W_i^{\ominus \diamond }=[w_{i,1}^{\ominus \diamond },\ldots ,w_{i,N_t}^{\ominus \diamond }]$ are iteratively compared with the local RPI list $W_i^{\ominus }=[w_{i,1}^{\ominus },\ldots ,w_{i,N_t}^{\ominus }]$. Since a higher RPI means executing the task can achieve higher scores for overall multi-UAV systems, the UAV with the lower RPI for the conflict task should remove it. Similarly, Eq. (16) is computed for all tasks in $T_i^{R'}$.

  $$\begin{aligned} z=\max _{k=1}^{|T_i^{R'}|}\{ w_{i,k}^{\ominus \diamond }-w_{i,k}^{\ominus } \} \end{aligned}$$

  (16)

  The task with z is selected to remove from the task list ${\mathbf {a}}_i$ and $T_i^{R}$.

• Step 4 (lines 14–16) After removing the selected task, the resources of UAV and time costs for all followed tasks in the task list are updated, and local RPI list $W_i^{\ominus }$, global winning RPI list $W_i^{\ominus \diamond }$ local contribution proportion list $\mho _{i}$, global winning contribution proportion list $\mho _{i}^\diamond$ and global winning UAV list ${\varvec{\beta }}_i$ are also updated. Repeating the Step 2 - Step 3 until Eq. (16) is not satisfied or $T_i^R$ is empty. The remaining tasks in $T_i^R$ (if they do exist) are put back into the task list ${\mathbf {a}}_i$ again. In brief, after repeating the task inclusion phase and conflict resolution phase, the winning UAVs for all tasks have been found. For the task whose winning contribution proportion is equal to 1, its winner UAV can accomplish it individually. It is noted that, the winner for the tasks that cannot be completed by a single UAV denotes the UAV that can provide the most resources for the task or the UAV with maximum global score improvement (z) as Eq. (16) based on maximum contribution proportion.

4.2 Two-stage coalition formation method

For the tasks that cannot be accomplished by a single UAV, i.e., $T_C=\{t_k|0<\mho _{i,k}^{\diamond }<1\}$, the UAV which can provide the most resources has been found as the winning UAV by repeating the task inclusion phase and conflict resolution phase. However, it is still necessary to try to form a coalition to provide enough resources for executing the tasks in $T_C$.

Fig. 3

Flow chart of the proposed two-stage coalition formation method

To this end, a two-stage coalition formation method is designed to form a feasible coalition for the tasks that cannot be completed by a single UAV. In the first stage, the UAVs that can provide the required resources and do not violate the deadline constraints become preliminary coalition members. The coalition size is further reduced in the second stage to obtain the final coalition. The conflict-free solution of iterating the previous two phases is set as the inputs of this two-stage coalition formation method, while the final assignment for all UAVs, coalition and actual start times for all tasks are obtained as the outputs. The details are described as Algorithm 4 and Fig. 3.

4.2.1 Stage 1: select preliminary coalition members

The final winning UAV for the task that cannot be completed by a single UAV is regarded as the leader of the coalition for the task, and the leader further selects members for this coalition.

• (1) Idle time slot mechanism (ITSM)

For the tasks which need to be completed by a coalition, the changed time costs for these tasks may have a great impact on the time costs of the following tasks. Hence, it is only allowed to affect the tasks which can be accomplished by a single UAV but do not disturb the tasks which must be completed by a coalition in this paper. To this end, we propose an idle time slot mechanism (ITSM) to compute the feasible time slot $\Delta _{i,n}=[ES_{in}, LS_{in}]$ for $v_i$ to start task $t_n$ as Eq. (17),where $t_n$ needs to be accomplished by a coalition and inserted into the $k+1$ position of ${\mathbf {a}}_i$ (line 3). $ES_{in}$ and $LS_{in}$ denote the earliest start time and latest start time for $v_i$ to start $t_n$, respectively.

Fig. 4

Illustration of computing the feasible time slot by ITSM

The earliest start time $ES_{in}$ is computed as the arrival time for the UAV to arrive task, which means that the UAV starts the task as soon as the UAV arrives. For the latest start time $LS_{in}$, we consider two cases according to the insertion position of task $t_n$ and whether there is a subsequent coalition task. When all subsequent tasks can be completed by a single UAV, $LS_{in}$ calculates as the $ES_{in}$ plus the redundancy time which is the difference between the deadline for starting the last task and the actual start time of the last task. If there is a subsequent task that needs to be completed by a coalition, the computation of feasible time slot is shown as Fig. 4. The start times of tasks which can be performed by a single UAV and between $t_k$ and $t_c$ are delayed. $t_c$ is the first coalition task after insertion position $k+1$. In addition, the waiting time $d_{i,c}^W$ of $t_c$ are also be utilized to create a long feasible time slot. Therefore, $t_n$ can be inserted into $k+1$ position of ${\mathbf {a}}_i$ without affecting the start times of coalition tasks. It is noted that, the tasks between $t_k$ and $t_c$ all can be performed by a single UAV. $LS_{in}$ should not be later than $t_n$’s deadline $s_n$.

In conclusion, the feasible time slot $\Delta _{i,n}=[ES_{in},LS_{in}]$ for $v_i$ start $t_n$ is computed as Eq. (17):

$$\begin{aligned} \begin{aligned}&ES_{in}=\tau _{k}+d_{i,k}^E+d_{i,k,n}^T=\tau _{in}\\&LS_{in}= {\left\{ \begin{array}{ll} \min {ES}_{in}+d_{i,c}^W+d_{i,k,k+1}^T-d_{i,k,n}^T-d_{i,n}^E-d_{i,n,k+1}^T, s_n \}, \ 0<\mho _{i,c}^{\diamond }<1\\ \min {ES}_{in}+(s_{|{\mathbf {a}}_i|}-\tau _{L|{\mathbf {a}}_i|}),s_n\}, t_c=\emptyset \\ \end{array}\right. } \end{aligned} \end{aligned}$$

(17)

where $s_{|{\mathbf {a}}_i|}$ and $\tau _{i|{\mathbf {a}}_i|}$ represent the deadline and actual start time for the last task in task list ${\mathbf {a}}_i$ respectively. If the new task is inserted into the last position of the task list, the latest start time is equal to the earliest start time, i.e., $ES_{in}=LS_{in}=\tau _{in}$.

• (2) Procedure of stage 1

The leader UAV $v_L$ first computes the feasible start time slot for task $t_n$ by Eq. (17), where $v_L$ cannot perform $t_n$ individually. It is noted that the execution order of $t_n$ in the task list ${\mathbf {a}}_L$ has been obtained by repeating the task inclusion phase and conflict resolution phase. Then, the leader $v_L$ communicates the information, including the location $P_n$, the remaining resources required $R_{n}^{T\triangle }=R_n^T-R_L^U$ and the feasible start time slots $\Delta _{L,n}$ for task $t_n$, with neighboring UAVs where a communication link exists (line 4). The receiver $v_j$ evaluates whether it can provide a part or all resources required based on the current task list. Here, we define a resource contribution degree $\zeta _{jn}$ as Eqs. (18) and (19) to represent the proportion of the resources that UAV $v_j$ can provide the resources currently required to process $t_n$.

$$\begin{aligned} \zeta _{jn}= \,& {} \frac{\sum _{m=1}^M D_j^m}{\sum _{m=1}^M R_{nm}^{T\triangle }} \end{aligned}$$

(18)

$$\begin{aligned} D_j^m= \,& {} {\left\{ \begin{array}{ll} R_{jm}^{U},&{} R_{jm}^{U}\le R_{nm}^{T\triangle }\\ R_{nm}^{T\triangle },&{} others \end{array}\right. } \end{aligned}$$

(19)

where $R_{nm}^{T\triangle }$ denotes the number of type m resources that $t_n$ still required based on existing coalition members rather than the original required resources $R_{nm}^T$ of $t_n$ before the allocation process. It is noted that, $R_{j}^{T}$ always updates as Eq. (20) in the process of task allocation rather than remaining same, to reflect the current resources status of $t_j$.

$$\begin{aligned} R_{nm}^{T\triangle }=R_{nm}^{T}-\sum _{i=1}^{|C_n|}D_j^m \end{aligned}$$

(20)

If $\zeta _{jn}>0$, then try to temporarily insert $t_n$ into all positions of ${\mathbf {a}}_j$ by task inclusion phase. If there is a position available to insert $t_n$, then compute the feasible start time slot $\Delta _{j,n}=[ES_{jn},LS_{jn}]$ by Eq. (17) (line 7). If the $\Delta _{j,n}$ and $\Delta _{L,n}$ overlap, i.e., $\varvec{\Delta _{j,L,n}^{'}}$ $=\Delta _{j,n}\bigcap \Delta _{L,n}\ne 0$, then receiver $v_j$ becomes one of the members of the preliminary coalition $C_n^P$, and sends the information of feasible start time slot $\Delta _{j,n}$ and the resources it still carried $R_{j}^{U}$ to the leader $v_L$ (lines 9-10). It means that when the receiver has a position that can insert $t_n$ and the feasible start time slot of this position overlaps the feasible start time slot of the leader, it becomes a preliminary coalition member. Otherwise, when all positions cannot provide an overlapped feasible start time with the leader, the UAV is not selected. It is noted that the leader has the ability to calculate the overlapped feasible start time slot $\Delta _{j,L,n}^{'}$ and contribution degree $\zeta _{jn}$ based on the received information.

4.2.2 Stage 2: reduce coalition size

The leader $v_L$ receives the information from preliminary coalition members in $C_k^p$ and needs to further reduce the coalition size to obtain the final coalition members. We detail the next three different criteria for the leader to rank UAVs in a preliminary coalition (line 15). Each approach prioritizes the UAVs by a different characteristic and aims towards optimizing according to a different metric.

• Max $\varvec{\zeta _{jk}}$: Order preliminary coalition members according to the contribution degree $\zeta _{jk}$. The UAVs that can provide more resources come first. This strategy can reduce the coalition size and fewer UAVs would add to the coalition. In addition, fewer coalition members will result in fewer UAVs may be affected by the task’s delay.

• Max $\varvec{\Delta _{j,L,k}^{'}}$: UAVs are ordered by overlapped feasible start time slot $\Delta _{j,L,k}^{'}$. Since the feasible start time slot of the UAV must overlap with the leader’s, a longer overlapped feasible start time slot means the coalition can start the task within a more flexible time slot.

• Min $\varvec{ES_{jk}}$: Prioritizes UAVs according to their earliest start time ($ES_{jk}$). Since the delay in the start time of the task that requires a coalition to complete will result in the subsequent tasks of all coalition members being delayed. Hence, the later the task start, the lower reward received for the overall multi-UAV system which can be inferred from Eq. (3). To this end, the UAV with the earliest start time has the highest priority, which can receive a higher total reward.

First, after the leader $v_L$ joins $C_k$, the final feasible start time slot for $t_k$ is equal to the feasible start time slot of leader UAV, i.e., $\Delta _k=\Delta _{L,k}$ (lines 16-17). Then, iteratively add the UAVs in rearranged preliminary coalition $C_k^p$ in order (lines 18-19). If $v_p$ still has common feasible start time slot with the exist coalition feasible start time slot, i.e., $\Delta _k\bigcap \Delta _{p,k}\ne \emptyset$, the feasible start time for final coalition is updated as the intersection of the two, i.e., $\Delta _k=\Delta _k\bigcap \Delta _{p,k}$, and $v_p$ is included into the final coalition $C_k$. When $v_p$ cannot provide the resources that $t_k$ still required or $\Delta _k\bigcap \Delta _{p,k}=\emptyset$, the adding process skips $v_p$ and continues to include other UAVs to final coalition. The stage 2 ends when there is a UAV $v_p$ which can provide all remaining required resources of $t_k$, i.e., $\zeta _{pk}=1$ or the all UAVs in preliminary coalition cannot provide adequate resources for $t_k$. The final coalition for completing task $t_k$ is denoted as $C_k$ and the feasible start time for task $t_k$ is defined as the intersection of feasible start time slots for all coalition members as Eq. (21):

$$\begin{aligned} \Delta _k=\bigcap _{i=1}^{|C_k|}\Delta _{i,k}\ne \emptyset ,\forall v_i\in C_k \end{aligned}$$

(21)

The task is regarded as failed when there are not enough resources provided by all UAVs in the preliminary coalition, and all UAVs in $C_k$ is set free (lines 30–31). When the final coalition can provide all required resources, all final coalition members include the task $t_k$ and set the start time of $t_k$ as the earliest start time in the final feasible time slot. After that, all final coalition members update the start times of all subsequent tasks (lines 33–36).

4.3 Reassignment application in dynamic environment

When all UAVs execute tasks as the preallocation results which are computed based on known information of UAVs and tasks, there may be unexpected new tasks introduced to the problem, which may lead to low efficiency or failure of the original plan. With the purpose of reallocating the new tasks within a short time and avoiding unnecessary computation resources, it is preferred to allocate the new task to the UAV which can perform it individually rather than a coalition. To this end, this section describes the ability of the two-stage coalition formation method to address the dynamic task reallocation problem.

When a UAV $v_d$ detects a new task $t_n$ in the process of executing the tasks in its task list, it first determines whether it can provide all required resources for performing $t_n$. Furthermore, determine whether exists a position to insert $t_k$ without affecting the time costs of the assigned tasks which need to be completed by a coalition (line 5). If $v_d$ can, then it includes $t_k$ into its task list and the reassignment ends (line 6). However, if $v_d$ cannot perform $t_k$ individually, it transmits the information of $t_n$ to all its neighbors $U_N$, and each neighboring UAV $v_j$ computes the resource contribution degree $\zeta _{jn}$ by Eq. (18) (line 10). If $v_j$ can provide resources $t_n$ required, i.e., $\zeta _{jn}>0$, the feasible start time slots for all positions are computed by Eq. (17) and the widest one is selected as the final feasible start time slot $\Delta _{j,n}$ (lines 12–13). If there is no position to insert $t_n$, we set the resource contribution degree as 0 (lines 14–15). After all, neighbors have computed the resource contribution degrees and feasible start time slots, a simple communication is triggered to elect the UAV which can provide the most resources for $r_n$ as the leader (line 19). When the leader can provide all resources $t_n$ required individually, $t_n$ is allocated to it (lines 20–22). Otherwise, carry the two-stage coalition formation method to further form a coalition for the new task $t_n$ (line 24).

Remark 1

If the UAV can provide required resources for multiple tasks as the leader or receiver, there may exist resource conflicts or deadlock. In this paper, we consider two types of resource deadlock, a UAV can provide resources for multiple tasks and a leader can provide resources for multiple tasks, and both of these deadlocks can be solved by comparing the static value $SV_j$ of the task. In detail, since a higher static value means that the task is more important and with higher priority, the UAV evaluates the available resources in the order in which the static value decreases. It means that only when the coalition formation process of the task with the higher static value is completed, the coalition formation stage of the task with the lower static value can be carried out.

4.4 Computational complexity

To asses the computational complexity of running RCPIA on one UAV, the method used in [43] is followed. According to the structure of RCPIA, the analysis of computational complexity is divided into three parts: (1) task inclusion phase and conflict resolution phase part, (2) two-stage coalition formation part, and (3) reassignment part.

• (1) For the first part, the major computational complexity arises from the calculation of RPI and IPI values and the updated scores for the remaining tasks in the task list. In task inclusion phase, a maximum computational complexity of $(|{\mathbf {a}}_i|+1)(|{\mathbf {a}}_i|+2)M_1\sigma /2+|{\mathbf {a}}_i|\sigma$ is requested to compute the IPI and update the scores for remaining tasks when inserting a new task into ${\mathbf {a}}_i$. $|{\mathbf {a}}_i|$ denotes the cardinality of the task list ${\mathbf {a}}_i$. $M_1$ denotes the number of tasks that are not yet in ${\mathbf {a}}_i$ and meet the constraints in Eq. (4). $\sigma$ implies the complexity of computing the local score of a task. For the conflict resolution phase, as most operations are simple rule-based logical judgments, few computations are required for consensus. It is assumed that a total of $M_2$ tasks are intended to be removed from ${\mathbf {a}}_i$. This will requires $|{\mathbf {a}}_i|M_2\sigma -M_2(M_2+1)\sigma /2+(|{\mathbf {a}}_i|-1)\sigma$ computational complexity maximumly. It can be inferred that the major computational complexity is dominated by the task inclusion phase and defined as $O((m_i-|{\mathbf {a}}_i|)|{\mathbf {a}}_i|^2M_1\sigma N_u)$ at each iteration to compute IPI and RPI. $m_i-|{\mathbf {a}}_i|$ is the maximum number of tasks that can be added into a UAV’s task list during each iteration of the algorithm. It is noted that, the difference between baseline PI and RCPIA lies on the computation and comparison of contribution proportion. In addition, the changes in the contribution ratio of one task will not affect the contribution ratio of other tasks in the task list as shown in Eq. (6). Define $\xi$ as the computation time of contribution degree for a position in the task list. Hence, the maximum computational complexity of contribution degree in this two phases is $O(M_1N_u(m_i-|{\mathbf {a}}_i|)\xi )$. To sum up, the computational complexity of these two phases are $O((m_1-|{\mathbf {a}}_i|)(\xi +|{\mathbf {a}}_i|^2\sigma )N_uM_1)$.

• (2) For the second part, it is assumed that up to $N_u$ UAVs participate in the coalition construction for performing the task $t_j$ which needs N-type of resources. Define $\kappa$ as the computation time of idle time slot of a position in the task list. In the first stage, by calculating the idle time slot for all UAVs by ITSM, the preliminary coalition members are selected and the computational complexity is $O((|{\mathbf {a}}_i+1|)N_uN\kappa )$. In the second stage, the preliminary members are first sorted by one of the three criteria (discussed in Section 4.2.2) which result in $O(N_ulgN_u)$ computational complexity maximally. After that, every UAV must be iteratively checked until the resource constraints of tasks are met. Hence, the maximum computational complexity of the second stage is $O(N_uN+N_ulgN_u)$. In conclusion, the computational complexity of the two-stage coalition formation method is $O(N_u(lgN_u+N+(|{\mathbf {a}}_i|+1)\kappa N))$.

• (3) For the third part, the detection UAV first computes the contribution degree and idle time slots for all positions in ${\mathbf {a}}_i$ which requires $O(\xi +(|{\mathbf {a}}_i|+1)\kappa )$. Then, every UAV needs to compute the feasible time slot for all positions in its task list and contribution degree, which needs $O(N_u(\xi +(|{\mathbf {a}}_i|+1)\kappa ))$ computational complexity maximally. In summary, the reassignment part requires $O((N_u+1)((|{\mathbf {a}}_i|+1)\kappa +\xi )$.

It can be concluded that the main computational complexity is still dominated by the calculation of IPI and RPI. The computational complexity of the two-stage coalition formation method and its reassignment application are all related to the number of available positions $|{\mathbf {a}}_i|+1$ and the number of UAVs $N_u$, which means that these two parts are all polynomial-time algorithms that scale well with the number of the UAVs and tasks in its task list. Hence, there is not too much computing time consumed in these two parts.

5 Numerical results

This section presents the simulation results of RCPIA to demonstrate its effectiveness and performance. The test scenario is first introduced and used to illustrate the solving process of RCPIA, including the reassignment application for dealing with the new emerging task. In addition, RDAATSM is conducted to compare with RCPIA to demonstrate its efficiency.

5.1 Test scenario

To test the performance of RCPIA, the combat scenarios mentioned in [15] and [16] are taken as references to design a combat scenario shown in Fig. 5. There are six heterogeneous UAVs, 16 tasks and six types of resources in this considered scenario. The resources capabilities of UAVs and the resource requirements for attack tasks are displayed in Tables 3 and 4 respectively, where the unit of time is an hour and the positions of all UAVs are initialized as (20,30,4). The commander can set the deadlines for attack tasks according to the battlefield situation to avoid further deterioration of the situation. Also, the deadlines can be used for the commander to control the different stages of the combat. In addition to EMI, other resources will be continuously consumed when performing tasks.

It is assumed that all UAVs perform tasks at an altitude of 4 km. Note that the scenario settings described in this paper are not necessary for the algorithm to work. All methods are conducted on MATLAB R2016a with AMD Ryzen 7 PRO CPU @ 1.70 GHz.

Fig. 5

Simulation example of combat situation

Table 3 Resources capabilities of UAVs

Table 4 Resource requirements for attack tasks

5.2 The feasibility of RCPIA

5.2.1 Task assignment for known tasks

The allocation results of known tasks derived from RCPIA are shown in Table 5. The task sequence for each UAV and the actual start times are displayed where the coalition tasks are in bold. Remaining resources for all UAVs are also displayed. It can be seen that all tasks are allocated by RCPIA. Furthermore, it is noted that 2 tasks ($t_7$ and $t_{11}$) need to be cooperatively performed by a coalition at the same time displayed in Table 6. The leader for each coalition tasks are in bold. To clarity, the schedules for all UAVs are also demonstrated in Fig. 6 and the coalition task is all in red where tasks that can be performed by a single UAV are in gray.

Since RCPIA prefers to allocate the tasks to the UAV which can individually complete them, only two tasks ($t_7$ and $t_{11}$) whose leaders ($v_3$ and $v_2$) cannot provide enough resources after iterating task inclusion phase and conflict resolution phase. Hence, the leaders form coalition for tasks by the two-stage coalition formation method. It can be seen from Table 6 that $v_3$ as the leader of $t_7$ first selects $v_1$ and $v_5$ as the preliminary members and the two UAVs provide same number of resources for $t_7$. Since the longer feasible time slot of $v_5$ is overlapped with $v_3$’s, the $v_5$ is selected as the final coalition members to cooperatively perform $t_7$ and it needs to wait 0.2066h until $v_3$ arrives. The two UAVs start $t_7$ at 0.7703h. Similarly, as the leader of $t_{11}$, $v_2$ first chooses $v_4$ and $v_5$ as the preliminary coalition members by the phase 1. The two preliminary members both provide 0.0095 contribution degree for $t_{11}$. Finally, the leader $v_2$ chooses $v_4$ as the final coalition members to start $t_{11}$ at 1.4613h.

Therefore, this section demonstrates the fact that most of the tasks are allocated to a single UAV by RCPIA rather than a coalition. In addition, RCPIA can further make full use of resources to cooperatively form coalitions for the tasks that cannot be completed by a single UAV.

Table 5 Assignment results for known tasks

Fig. 6

Schedule of all UAVs for allocating known tasks

Table 6 Coalition formation process of some known tasks

5.2.2 Reassignment for the new emerging task

In a dynamic environment, some new tasks may be introduced into the problem, which leads to low efficiency or failure of the original solution. Hence, to illustrate the feasibility of RCPIA to cope with the new emerging task, set the new emerging task as the new task $t_{17}$ appears at [50,50,0] at 0.3h. The information of new task is displayed in Table 7 and the reassignment of $t_{17}$ is shown in Table 8. The coalition tasks are still in bold while the tasks whose start times are affected are in italics. It can be seen that the start times of $t_{15}$ and $t_5$ are delayed compared to the original schedules of $v_4$ and $v_6$. To clarity, the schedules for all UAVs after reallocation are shown in Fig. 7, and the allocation of the new task $t_{17}$ is in green and the coalition process for $t_{17}$ is also presented in Table 9.

Table 7 The resource requirements for attacking the new emerging task $t_{17}$

Table 8 Reassignment results of all UAVs after a new task appearing

Fig. 7

Scheduler of all UAVs after reallocating the new task

Table 9 Coalition formation process of the new emerging task

The reallocation process of $t_{17}$ (Table 9) is described as follows in detail. Since the detection UAV $v_2$ cannot provide enough resources for the new task $t_{17}$, it transmits the information of $t_{17}$ to its neighbors through the communication network. After each neighbor computes the contribution degree and feasible time slot, $v_6$ is selected as the new leader of $t_{17}$. However, $v_6$ only can contributes [0,0,0,0,200,0] resources for $t_{17}$ and there are still [2,0,0,0,0,1] resources required. Hence, it selects preliminary coalition members by the first stage of the two-stage coalition formation method. $v_1$ and $v_4$ can contribute 0.0049 and 0.0147 contribution degree for $t_{17}$. Finally, the leader $v_6$ chooses $v_4$ as the other final coalition member to cooperatively start $t_{17}$ at 0.5008h. It is worth mentioning that, to insert the new task into $v_4$’s task list, RCPIA creates a longer feasible idle time slot and not affects the coalition task $t_{11}$ by delaying the start time of $t_{15}$. Since $t_{15}$ is only performed by $v_4$, this delay will not affect the schedules of other UAVs’. In addition, since $v_6$ can individually complete tasks $t_{16}$ and $t_5$, the start times of these two tasks can all be delayed to create a much long idle time slot. Hence, the feasible time slot for $v_6$ to start $t_{17}$ is [0.5008,3.2], where 3.2h is the deadline for starting $t_{17}$.

This section shows that RCPIA is able to create a longer feasible idle time slot for the new task by shifting the start times of the tasks that can be performed by a single UAV. At the same time, the start times of all coalition tasks will not be affected. This will not only ensure the preallocation will not be greatly affected, but also provides greater flexibility to insert the new task.

5.3 The influence of UAVs number and tasks number

To further analyze the influence of the number of UAVs and tasks on RCPIA more comprehensively and generally, we consider two series of simulations. It is noted that, each setup with the same number of tasks and UAVs but different resources distribution runs 50 times to avoid contingency. Since RDAATSM [13] can also support the simultaneously starting tasks and resource constraint, it is used to be compared with RCPIA in terms of the average percentage of allocating known tasks, the average percentage of tasks to be completed by a UAV coalition to all allocated tasks, the average runtime and the average total score of allocating known tasks.

Fig. 8

The simulations are tested for allocating 40 known tasks to an increasing number of UAVs which are 4, 8, 12, 16. Run RCPIA and RDAATSM 50 times and comparison of a Average allocation percentage of known tasks, b Average percentage of allocated tasks that need to be completed by a coalition, c Average runtime, and d Average total score are shown

Fig. 9

The simulations are tested for an increasing number of known tasks which are 20, 40, 60, and 80 need to be allocated to 8 UAVs. Run RCPIA and RDAATSM 50 times and comparison of a Average allocation percentage of known tasks, b Average percentage of allocated tasks that need to be completed by a coalition, c Average runtime, and d Average total score are shown

First, we consider 40 known tasks need to be allocated to UAVs whose number increases from 4 to 16. The comparison results are shown in Fig. 8. As the number of UAVs increases, more tasks can be allocated due to more resources can be provided as shown in Fig. 8a. In addition, RCPIA always allocates more tasks than RDAATSM. Since RDAATSM is developed based on CBBA, it must meet the marginal diminishing characteristics which lead to the tasks with the greatest score being first selected rather than the one with the greatest contribution degree. This may lead to forming more coalitions to provide enough resources for the task. However, more coalitions may indicate higher failure rates since the task is only allowed to insert into the appropriate task idle period without affecting the established plan. Hence, the more coalitions are required to allocate the tasks, the low allocation percentage in RDAATSM caused. For the coalition percentage of allocated tasks shown in Fig. 8b, fewer tasks are allocated to coalitions for RCPIA compared to RDAATSM, which results from RCPIA prefers to allocate the tasks to the UAV that can complete it individually. For the runtime, as the number of UAVs increases, more conflicts will be resolved in the conflict resolution phase as all UAVs build their task lists locally and more time is consumed in the task inclusion phase to re-add tasks after the conflict resolution phase. Hence, as seen in Fig. 8c, the average runtime of both two algorithms increases as more UAVs are introduced into the problem. Besides, RCPIA consumes a little less runtime to obtain the results compared to RDAATSM. The reason is that even though the two-stage coalition formation method consumes more time to form coalitions for the tasks that cannot be performed by a single UAV, the marginal diminishing characteristics of RDAATSM causes releasing all subsequent tasks of added/deleted tasks. This operation may consume more runtime. As more tasks are allocated by RCPIA, its total scores are higher than that of RDAATSM as shown in Fig. 8d.

Then, we consider the scenario that 20, 40, 60, and 80 known tasks need to be allocated to 8 UAVs. The comparison results are shown in Fig. 9. As the number of tasks increases, fewer tasks are allocated successfully as shown in Fig. 9a since the resources of 8 UAVs are certain and fewer tasks can be provided enough resources. In addition, fewer tasks are assigned to the coalition by RCPIA compared to RDAATSM in Fig. 9b. The reason is that when more tasks need to be assigned, RCPIA prefers to select tasks whose required resources better match those UAVs carry. Furthermore, RDAATSM selects the tasks that can achieve a higher score, which means that more coalitions are needed. As seen in Fig. 9c, as the increasing number of tasks need to be assigned, there is increasing runtime consumed due to calculating the IPI/RPI and bids in RCPIA and RDAATSM respectively. Similarly, fewer coalition tasks result in less time taken in forming a coalition by the proposed two-stage coalition formation method in RCPIA, while more runtime is required in RDAATSM to form a UAV squad to provide enough resources for more coalition tasks. Fewer allocated tasks of RDAATSM imply lower total scores as shown in Fig. 9d.

In conclusion, the characteristic of preferring to allocate the tasks to the UAV which can complete them individually in RCPIA avoids some unnecessary cooperation to form a coalition. This not only leads to more tasks are allocated and fewer tasks are allocated to a coalition, but also higher total scores are obtained. In addition, although the two-stage coalition formation method consumes much time to form a coalition, fewer tasks need to form coalitions, so less average runtime is spent.

5.4 The performance of RCPIA in reallocating the new task

To further demonstrate the performance of RCPIA in dealing with the new emerging task, this section considers three different appearance times of the new task, i.e., early, middle and late time which defined as the 10 percent, 40 percent and 80 percentage of the latest task completion time of the preallocation schedules. For a given 6 UAVs and 20 known tasks, each setup runs 50 times and the average results in terms of the success rate of reallocation, the percentage of a coalition, the consumed runtime and reallocation score of reallocating the new task successfully are displayed in Table 10.

Table 10 Performance comparison when assigning the new task with different appearance time

It can be seen that, with the delay of the emergence of the new task, fewer simulations can reallocate the new task successfully as shown in Table 10, which results from that fewer positions left to insert the new task. In addition, RCPIA always can allocate the new task in more simulations compared with RDAATSM. This is because that most of the preallocated tasks can be completed by a single UAV in RCPIA and the start times of these tasks can be flexibly shifted to create a long feasible time slot to insert the new task. Meanwhile, since RDAATSM only allows to insert the new task into the synchronization wait time and the start times of preallocated tasks cannot be affected, fewer simulations can allocate the new task successfully, i.e., the average success rate of reallocation for RCPIA is higher than RDAATSM. In addition, the average coalition percentage of RCPIA is lower than RDAATSM since RCPIA prefers to allocate the tasks to the UAV that can complete tasks individually. It must be noted that, since the appearance time and the start times of coalition tasks are random and not influenced by the appearance time but related to the preallocated schedules, the coalition percentage of the two algorithms does not show a obvious change trend. As for the runtime, since RCPIA prefers to allocate the tasks to the UAV that can perform the tasks individually, less computation time is spent in forming a coalition for the new task, i.e., the runtime of RCPIA reallocating the new task is less than RDAATSM. Besides, since the number of feasible insertion positions decreases as the appearance time increases, less computation time is required to calculate the IPI/RPI or bids for the two algorithms respectively, i.e., the average runtime for allocating the new task decreases. For the average reallocation score of the simulations which reallocate the new task successfully, RDAATSM performs better than RCPIA since it allocates the new task to the UAV with the highest bid.

In conclusion, most allocated known tasks are performed by a single UAV in RCPIA, which results that the preallocation is more flexible to cope with the new task. Hence, RCPIA can allocate the new emerging task in more simulations and less runtime is consumed compared to RDAATSM, which demonstrates the performance of RCPIA in reallocating the new task in dynamic environment.

6 Conclusion and future works

The task assignment problem of a multi-UAV system with limited resources is one of the most extensive research domains and many efforts have been made. Although the existing algorithm considers forming a coalition to accomplish tasks, which require a different number of resources, they cannot guarantee that the coalition UAVs reach the task position at the same time. In addition, the algorithm should be more flexible and robust when encountering new emerging tasks. To this end, this paper proposes a distributed heuristic algorithm called RCPIA to address the task allocation problem for heterogeneous UAVs with limited resources. First, the task allocation problem with the constraints of resources and simultaneously starting tasks is modeled in the mathematical formulation. Second, we develop the task inclusion phase and conflict resolution phase to adapt to the resource constraint. The criteria of adding and removing tasks are modified, and the consensus rules are also revised. Third, a two-stage coalition formation method is proposed to form coalition for the tasks that cannot be performed by a single UAV, which makes full use of the remaining resources of UAVs. The coalition formation method first selects the UAVs which can provide the required resources and do not violate the deadline constraints as preliminary coalition members in the first stage. Then, the coalition size is further reduced by three criteria and the final coalition is obtained. Finally, a reassignment application of two-stage coalition formation method is also introduced to cope with the new task appearing in the dynamic environment. Simulation results illustrate the allocation process of RCPIA in detail when assigning known tasks and new tasks in the design scenario. In addition, to demonstrate the efficiency, RDAATSM is conducted to compare with RCPIA. The results indicate that RCPIA performs well in resource-constrained task allocation problem and increases the robustness of assignment results.

The limitation of RCPIA is that it cannot balance the solution quality and computation time. In our future work, we plan to: 1) further improve the time efficiency of RCPIA; 2) study the coalition formation method with the precedence constraints; 3) study the impact of network topology on task assignment results.

Appendix

See Table 11.

Table 11 Action Rule For UAV i Based On Communication With UAV k Regarding Task k