An Improved Market-Based Auction Algorithm for UAVs Task Assignment Problem

Abstract

This paper analyzes distributed task assignment for unmanned aerial vehicles (UAVs) using a market-based parallel auction algorithm. This approach includes five steps: choosing tasks into subset, auctioning the task subset, evaluating the bids, assigning tasks to unmanned aerial vehicles and arranging the velocity of each UAV and tasks execution times. Through auctioning several tasks, including coupling and individual tasks, in one time, this method greatly reduces the communication requirements between unmanned aerial vehicles in the process of distributed task assignment, and therefore results in lower risk of being detected and higher real time property. Simulation results show that market-based parallel auction algorithm can efficiently allocate tasks to UAVs.

1 Introduction

With the development of artificial intelligence (AI) and the application of AI on unmanned aerial vehicles (UAVs), the capability of UAVs’ autonomous determination is promoted gradually [1]. In the future, UAV teams may plan and execute missions without human feedback. Unmanned Systems Integrated Roadmap FY2011-1036 promulgated by the Department of Defense of the United States hopes to make UAV teams has the ability of autonomous collaborative combat before 2017.

Collaborative task assignment is the key technology of UAVs collaboration system [2, 3]. The purpose of collaborative task assignment is to assign a set of cooperative tasks to UAV team and arrange mission sequences and execution times for every UAV in the team. Distributed task assignment based on multi-agent technology can utilize every team member’s computation capability and make the system robust and flexible [4]. To achieve the goal of autonomous collaboration, we require the agents to be able to compute a coordinated task strategy and share the available data.

Market-based approach is suitable for distributed task assignment [5]. One of the representative market-based approaches is auction algorithm [6]. Auction algorithm assigns task to UAV which has the greatest superiority through processes of tender and biding. But the traditional one-by-one auction algorithm has one disadvantage that is only one task will be assigned in one auction process. So the communication demands among UAVs are very huge. For the existence of communication delays, frequent communication will affect the real time property of this approach. At the same time, frequent communication increases the risk of be detected by enemy.

This paper presents an improved market-based auction algorithm to solve the problem of allocating tasks including coupled ones to multiple UAVs. The outline of this paper is as follows. After the introduction, the scenario of collaborative task assignment for UAV team is showed (Sect. 69.2). Section 69.3 describes the improved market-based auction algorithm in detail. After the simulation results, presented in Sects. 69.4 and  69.5 reports the conclusions and future developments.

2 Scenarios

Given a list of $N_{T}$ tasks and a UAV team formed by $N_{U}$ UAVs, the goal of the task assignment is to find a conflict-free matching of tasks to UAVs that maximizes performance of the whole system. An assignment is said to be conflict-free if each task is assigned to no more than one UAV [7, 8]. Some tasks have close collaboration requirements that constraint tasks to be carried out simultaneously. Every task has an earliest execution time point $ET_{j}$ and a latest execution time point $LT_{j}$ which limit the task to be carried out in the time bounds $\left[ {ET_{j} ,LT_{j} } \right]$. There are $N_{D}$ dangerous areas defended by ground-to-air missile or antiaircraft artillery in the planning environment across which UAVs are forbidden to fly. The performance of the whole system is assumed to be a sum of local reward values, while each local reward is determined as a function of tasks assigned to each UAV.

The task assignment problem described above can be written as the following program with binary decision variables $x_{ij}$ that indicate whether or not task $j$ is assigned to UAV $i$:

$$ {\text{Min}}\quad \sum\limits_{i = 1}^{{N_{U} }} {\sum\limits_{j = 1}^{{N_{T} }} {cost_{ij} x_{ij} } } $$

(69.1)

$$ {\text{Subject to}}:\quad \sum\limits_{j = 1}^{{N_{T} }} {x_{ij} } \le M_{iT} $$

(69.2)

$$ \sum\limits_{i = 1}^{{N_{U} }} {x_{ij} } \le 1 $$

(69.3)

$$ t_{j} \in \left[ {ET_{j} ,LT_{j} } \right] $$

(69.4)

$$ x_{ij} \in \left\{ {0,1} \right\} $$

(69.5)

where $x_{ij} = 1$ if task $j$ is assigned to UAV $i$ and $c_{ij}$ is a nonnegative function of assignment $x_{ij}$. $cost_{ij}$ is the cost of UAV $i$ to carry out task $j$ includes the length of route UAV $i$ flying to task $j$ location and the risk of being shot down if it cross enemy antiaircraft weapon defense areas. If UAVs are enforced to avoid the threat areas then $cost_{ij}$ is just the length cost. $t_{j}$ is the estimate time when task $j$ is carried out, which should be in the time window $\left[ {ET_{j} ,LT_{j} } \right]$.

It is assumed in this paper that UAVs in the team are isomorphic, that is when not think about the consumption of fuel each UAV has the same probability of finishing the same task successfully [9].

3 Algorithms

Market-based auction algorithm is suitable for distributed multi-agent task assignment scene for it does not require each agent in the team know about the global information. But the auction algorithm is inefficient when the size of task assignment is large because of abundant deals and communication between agents [10]. Another disadvantage of auction algorithm is that coupling constraints between tasks are not taken into account when tasks are allocated.

To satisfy the need of efficient cooperative task assignment, a parallel auction (PA) algorithm is presented. PA algorithm auctions a subset of tasks includes coupling and separated tasks in one time. The decrease of auction times reduces the communication requirements between agents. And it is easy to deal with collaborative demands when coupling tasks are auctioned together. The details of PA algorithm are as follows.

3.1 Subset of Tasks

Tasks are picked up and compose a subset of tasks waiting for auction before executing the PA algorithm. Every task which has not be allocated is endued with a priority defined as

$$ pri\_T_{j} = 1 - \frac{{LT_{j} }}{{\mathop {\hbox{max} }\limits_{i = 1}^{{N_{T} }} LT_{j} }} $$

(69.6)

Equation (69.6) reflects the urgency of tasks. The earlier of the latest start time point, the higher of the priority.

The agent who is in charge of the auction picks up the task with highest priority $T_{k}$ into subset. Then the close coupling tasks of the highest priority task $T_{k}$ are sent to subset. The number of tasks in the subset $N_{ST}$ should not larger than $N_{CU}$. $N_{CU}$ is the number of usable UAVs in the team. If $N_{ST} < N_{CU}$, no more than $N_{CU} - N_{ST}$ tasks which have lower priority will be chosen into the subset.

All the tasks in the subset will be auctioned together. Each agent can get no more than one task in one auction process.

3.2 Auction

After the subset of tasks is collected, the principal agent sends task information of the subset to all the agents in the team. Team members respectively work out practical scheme for every task in the subset. A scheme $bid_{ij}$ consists of three parts: $cap_{ij}$ showing the capability of agent $i$ to execute task $j$, $length_{ij}$ computing the length of route through which agent $i$ flies to the position of task $j$ and $\left[ {\hbox{min} \_rt_{ij} ,\hbox{max} \_rt_{ij} } \right]$ estimating time bound of agent $i$ to execute task $j$.

$$ bid_{ij} = \left\{ {cap_{ij} ,length_{ij} ,\left[ {\hbox{min} \_rt_{ij} ,\hbox{max} \_rt_{ij} } \right]} \right\} $$

(69.7)

$bid_{i} = \left\{ {bid_{ij} \;|\;j = 1,2, \ldots ,N_{ST} } \right\}$ is the aggregate of agent $i$’s scheme.

To calculate $bid_{ij}$, the route planning system of the agent $i$ plans a feasible route $route_{ij}$ from the position of the latest task in its task schedule to task $j$’s position and route $route_{jo}$ from the position of task $j$ to the reclaiming airport. We can get $length_{ij}$ and $\left[ {\hbox{min} \_rt_{ij} ,\hbox{max} \_rt_{ij} } \right]$ via $route_{ij}$ and the velocity range of agent $i$ and get $length_{jo}$ via $route_{jo}$. The capability of agent $i$ fulfilling task $j$ can be defined as

$$ cap_{ij} = \left\{ {\begin{array}{*{20}c} {\quad \quad \quad 0,\quad \quad \quad length_{ij} + length_{jo} > rest\_length_{i} } \\ {\quad \quad \quad \quad 0,\quad \quad \quad weapon_{j} > rest\_weapon_{i} } \\ {v\_length_{ij} \times (1 - \beta ) + v\_weapon_{ij} \times \beta ,\quad others} \\ \end{array} } \right. $$

(69.8)

$$ v\_length_{ij} = 1 - \frac{{length_{ij} + length_{jo} }}{{length_{i} }} $$

(69.9)

$$ v\_weapon_{ij} = 1 - \frac{{weapon_{j} }}{{rest\_weapon_{i} }} $$

(69.10)

where $rest\_length_{i}$ is the length that agent $i$ can fly by its rest fuel and $rest\_weapon_{i}$ is the qualities of rest weapons after agent $i$ finishes its task schedule. The more fuel and weapons remain means agents have the higher possibility to execute one task again if the first execution activity is failed.

3.3 Evaluate

Every member of the team sends back its bid to the principal agent. The principal agent evaluates all the bids together. The results constitute a $N_{CU} \times N_{ST}$ superiority matrix $Sup$ where $Sup_{ij}$ reflects the superiority of agent $i$ competing with other agents for task $j$. The measurement equation of $Sup_{ij}$ is

$$ Sup_{ij} = \left\{ {\begin{array}{*{20}c} {0,\quad \quad cap_{ij} = 0} \\ {\left[ {cap_{ij} \times (1 - \rho ) + pro\_len_{ij} \times \rho } \right] \times ctime_{ij} ,cap_{ij} > 0} \\ \end{array} } \right. $$

(69.11)

where

$$ pro\_len_{ij} = 1 - \, \frac{{length_{ij} }}{{\mathop {\hbox{max} }\limits_{i = 1}^{{N_{U} }} \left( {length_{ij} } \right)}} $$

(69.12)

and

$$ ctime_{ij} = \left\{ {\begin{array}{*{20}c} \begin{gathered} 0,\quad \quad \hbox{min} \_rt_{ij} > LT_{j} \hfill \\ 0.5,\quad \quad \hbox{max} \_rt_{ij} < ET_{j} \hfill \\ \end{gathered} \\ {1, \, \left[ {\hbox{min} \_rt_{ij} ,\hbox{max} \_rt_{ij} } \right] \cap \left[ {ET_{j} ,LT_{j} } \right] \, \notin \emptyset } \\ \end{array} } \right. $$

(69.13)

$pro\_len_{ij}$ is the route length factor that makes the agent $i$ near the position of task $j$ has a high probability of being chosen to execute task $j$. But it does not mean that the nearest agent has the highest probability to execute the task. For every task has special executing time window $\left[ {ET_{j} ,LT_{j} } \right]$, $\hbox{min} \_rt_{ij} > LT_{j}$ means even the agent $i$ flies to task position with the highest velocity it cannot arrive the task location before the deadline of the task $j$ and $\hbox{max} \_rt_{ij} < ET_{j}$ is the case that even the agent $i$ flies to task position with the lowest velocity it will get to the task location before $ET_{j}$. $ctime_{ij}$ is a time punishment factor. In the first case above, agent $i$ can not finish task $j$ within the prescriptive time bounds, so $ctime_{ij}$ is set as 0. In the second case agent $i$ has to plan a waiting route and cruise until fit the time requirement. To punish the waste of fuel the time punishment factor is set as 0.5. When $\left[ {\hbox{min} \_rt_{ij} ,\hbox{max} \_rt_{ij} } \right]$ and $\left[ {ET_{j} ,LT_{j} } \right]$ have intersection, which means agent $i$ will get to task position between $\left[ {ET_{j} ,LT_{j} } \right]$ by adjusting its flying velocity, $ctime_{ij}$ will be set as 1.

The length of route, time fitness and the capability of agent $i$ performing task $j$ have been taken into account in the computation of $Sup_{ij}$. $Sup_{ij}$ is a composite result of three factors mentioned above. $\beta$ is an accommodation coefficient with a range from 0 to 1 which reflects decision-maker’s favor. For all the factors in the function have a bound of $[0,1]$, the magnitude of $Sup_{ij}$ is between 0 and 1.

3.4 Assignment

As mentioned in Sect. 69.3.1, each agent only can get no more than one task in one auction and each task can be distributed to one agent. The problem of assigning UAVs to tasks in the subset is defined as

$$ {\text{Max}}\quad \sum\limits_{i = 1}^{{N_{CU} }} {\sum\limits_{j = 1}^{{N_{ST} }} {Sup_{ij} x_{ij} } } $$

(69.14)

$$ {\text{Subject to}}:\quad \sum\limits_{j = 1}^{{N_{ST} }} {x_{ij} } \le 1 $$

(69.15)

$$ \sum\limits_{i = 1}^{{N_{CU} }} {x_{ij} } \le 1 $$

(69.16)

$$ x_{ij} \in \left\{ {0,1} \right\} $$

(69.17)

Hungary algorithm has been designed to solve such problem [11]. But the normal Hungary algorithm can deal with the case that $N_{ST}$ equals to $N_{CU}$. If $N_{CU} > N_{ST}$, we can set $N_{CU} - N_{ST}$ fictitious tasks and consider superiority of every UAV biding those fictitious tasks as 0.

$$ Sup_{ij} = 0,\quad \quad \quad i = 1,2, \ldots ,N_{CU} ;\;j = N_{ST} + 1, \ldots ,N_{CU} $$

(69.18)

After those fictitious tasks join the subset, the dimension of superiority matrix is $N_{CU} \times N_{CU}$. Then we can get a $N_{CU} \times N_{CU}$ 0-1 matrix R shows the allocation result computed by normal Hungary algorithm. Delete the last $m - n$ lists of R and we will get the final assigning result.

3.5 Velocity and Execution Time Arrangement

The above steps insure that tasks can be carried out in special time windows. Then we need to fix the practical execution time point of each task and the flying velocity of each UAV. In this part, the data got from Sect. 3.3 will be useful.

Assume that agent $i$ is assigned to individual task $j$, we will have two segments of time $\left[ {\hbox{min} \_rt_{ij} ,\hbox{max} \_rt_{ij} } \right]$ and $\left[ {ET_{j} ,LT_{j} } \right]$. Through evaluation in part C and assignment in part D the situation of $\hbox{min} \_rt_{ij} > LT_{j}$ is avoided. If $\hbox{max} \_rt_{ij} < ET_{j}$, $ET_{j}$ is the time point for agent $i$ to execute task $j$, and agent $i$ should fly to task position with its lowest velocity $V_{\hbox{min} }$. In this case a path of waiting route is needed and the length of waiting route is calculated by Eq. (69.19).

$$ wlength_{ij} = V_{\hbox{min} } \times \left( {ET_{j} - \hbox{min} \_rt_{ij} } \right) $$

(69.19)

If $\left[ {\hbox{min} \_rt_{ij} ,\hbox{max} \_rt_{ij} } \right] \cap \left[ {ET_{j} ,LT_{j} } \right] \notin \emptyset$ and the intersection is $\left[ {at_{j}^{\hbox{min} } ,at_{j}^{\hbox{max} } } \right]$, $at_{j}^{\hbox{min} }$ will be the execution time of task $j$ and flying velocity of agent $i$ in this section is defined as

$$ v_{ij} = \frac{{length_{ij} }}{{at_{j}^{\hbox{min} } - pretime_{i} }} $$

(69.20)

where $pretime_{i}$ is the estimate time that agent $i$ finish its task sequence.

It is analogous to get the execution times of simultaneous tasks. Generally, simultaneous tasks have the same time windows. Assume that agent $k$ and agent $l$ are assigned to carrying out simultaneous tasks with time window $\left[ {ET_{m} ,LT_{m} } \right]$, $\left[ {\hbox{min} \_rt_{k} ,\hbox{max} \_rt_{k} } \right]$ and $\left[ {\hbox{min} \_rt_{l} ,\hbox{max} \_rt_{l} } \right]$ are the estimating time bounds of agent $k$ and agent $l$ to carry out those simultaneous tasks mentioned above. For the usage of waiting route and waiting time, the latest time that agent $k$ and agent $l$ carry out collaborative tasks can be set to $LT_{m}$. $ct$ is defined as $ct = \hbox{max} \left\{ {\hbox{min} \_rt_{k} ,\hbox{min} \_rt_{l} } \right\}$. If $ct \in \left[ {ET_{m} ,LT_{m} } \right]$, the execution time equals to $ct$, else it equals to $ET_{m}$. The computation of waiting length and flying velocity is the same as Eqs. (69.19) and (69.20).

4 Simulation Examples

To clarify the scenarios and illustrate the assignment algorithm presented in Sect. 69.3, a simulation example with a problem of size $N_{U} = 3$ and $N_{T} = 8$ is presented here. UAVs and task positions are placed in an area 100 km wide and 100 km long. Four detected and some undetected antiaircraft threats with different threaten ranges exist in the planning environment. The parameters of UAVs, tasks and threats are showed in Tables 69.1, 69.2 and 69.3 respectively. Time windows are set to the bounds from the start time point of the assignment process.

Table 69.1 The parameters of UAVs

Table 69.2 The parameters of tasks

Table 69.3 The parameters of threats

We assume that communications between UAVs are perfect, without delay and information losses. One of the team members is chosen as the tasks owner and host auctions. Each UAV has a route planner planning the best flying routes between two positions with sparse A* (SAS) algorithm [12] and task time availability windows are computed based on computing the length of the best flying routes. The progression of the simulation is shown in Fig. 69.1.

Fig. 69.1

Simulation example. a Initial positions. b First round auction results. c Second round auction results. d Third round auction results

Figure 69.1a shows the UAV and task positions at the beginning of the simulation. UAV team is cruising in the battle field. Figure 69.1b shows the first round auction result. Task1, 2 and 3 are chosen into the subset of tasks. After the processes of auction, evaluation and assignment presented in Sect. 69.3, Task1, 2 and 3 are assigned to UAV3, 1 and 2 respectively. The colorized lines are the best flying routes planned by SAS algorithm. Figure 69.1c, d show the second and third round auction result.

The velocity of each UAV in different phases and estimating execution time of each task is computed by method presented in Sect. 69.3.5. The arrangement results are shown in Table 69.4.

Table 69.4 The arrangement of execution times and velocity

From the simulation results we can find eight tasks are assigned to three UAVs by three times of auction activities, less than eight times of auction activities of the traditional one-by-one auction algorithm. So the efficiency is promoted nearly 167 %. To calculate the efficiency promoted by parallel auction algorithm, a series of tests was carried out in the same battle scene with 1–20 tasks. 3 UAVs with sufficient fuel and weapons join the tests. Respectively run the traditional auction algorithm and the improved parallel auction algorithm and record the auction times. The results are showed in Fig. 69.2. We can see that the efficiency is promoted 150–200 %.

Fig. 69.2

Parallel auction algorithm compared with traditional auction algorithm in auction times

5 Summaries

The problem of assigning collaborative and individual mixed tasks to multiple UAVs has been presented. The problem was solved using an improved market-based PA algorithm. This methodology allows the host agent to auction a series of tasks in one time therefore greatly decreasing the number of deals compared to traditional market-based auction algorithm. The reduction in number of auctions results in decrease in communication cost. The simulation results show that PA algorithm presented is realizable and has higher efficiency than traditional auction algorithm.