1 Introduction

With the rapid development of technology, robots are used in more and more fields. However, the environment that robots face today is always dynamic, real-time, complex and adversarial. What’s more, the current single-robot system has limitations in obtaining information and solving problems. When faced with such complicated tasks and stochastic working environment, a single-robot system is complicated to perform operations.

Compared to single-robot systems, multi-robot systems have more advantages when executing tasks. Robots in the system can complete tasks faster and better.

Therefore, the critical issue we need to study is how to assign tasks based on the work environment and situation accurately which is called multi-robot task assignment, MRTA. It aims to increase the efficiency of the entire robotic system and take full advantage of the collaborative functions in multi-robot systems. When the number and state of robots are precise, if the number and state of tasks are also precise, the MRTA problem can be considered as an assignment problem. We assume that there are N different robots and M different tasks in the multi-robot system. Then how to map N robots to M tasks correctly is an assignment problem.

Under normal circumstances, accomplishing tasks can provide some rewards for the system. The first object of task allocation is to maximize the utility the whole system can achieve. Moreover, it costs some to accomplish a task. So the second object is to minimize the cost of the whole system. The allocation of tasks directly affects the efficiency of the entire system. We aim to find the optimized task scheduling strategies.

However, in robot rescue tasks, completing tasks will not provide any positive return for the system, and tasks will continue to damage the system. For example, there is a firing building in a city. Extinguishing the fire cannot offer any positive income. However, if the fire brigade leaves the fire as it was, then the fire will cause continuous damage to the city until it stops.

This paper mainly studies task allocation in the rescue environment. Our goal is to minimize system damage caused by sudden disasters. Many task allocation methods are static at present. The task allocation method can be divided into two types: centralized and distributed. Based on the analysis of related work, a merging approach based on auction is proposed.

We made three contributions in this paper. First, a dynamic auction approach for differentiated tasks under cost rigidities (DAACR) is proposed. Secondly, we prove that DAACR is 𝜖-optimal. Finally, a detailed experiment is designed, we demonstrate the results to analyze our approach.

2 Related work

In recent years, scholars have made great progress in the research of multi-robot system and its cooperation mechanism. Some scholars proposed to use the dual programming representation process to solve decision problems [1], or use reinforcement learning and neural network in recent years to to control the robots [10, 11, 13]. The traditional dual programming algorithm is generally based on known and determined static environment, but in fact, the rescue environment is a dynamic environment. In order to improve the efficiency of search and rescue (SAR) in disaster relief, some researchers used auction-based task allocation scheme to develop a cooperative rescue plan [2, 5, 16].

Auction algorithm is a feasible task assignment method. It has proved to be effective in producing suboptimal solutions. Generally speaking, agents bid for tasks, and the highest bid wins the assignment [4, 7]. The traditional way of calculating the winner is to have a central agent as an auctioneer to receive and evaluate every bid in the bidder list [14]. Considering multiple resources of the robots and limited robot communication range, Lee [7] proposes a resource-oriented, decentralized auction algorithm (RODAA) for multi-robot task allocation. Lu [9] applied the idea of second-price auction to determine the final price in the double auction.

However, the results that auction generated cannot necessarily achieve the goals in the ideal time [5], at the same time, the response of robots when tasks are operated also has certain hysteresis [15].

The disadvantage of these methods is that the bidding of each agent must be transmitted to the auctioneers in some way [8]. A standard way to avoid communication constraints is to sacrifice auction performance by running auctions through adjacent auctioneers. To achieve an ideal task allocation plan, we must give full consideration to the tasks we have accomplished to obtain the corresponding costs and benefits [3, 6, 12].

3 Model description

We define Et to represent the robots’ work environment at time t. Mathematically speaking, Et can be formalized as below:

$$ E_{t} =< T_{1},T_{2},R> $$
(1)

In the formula (1), T1 is the set of tasks that have been allocated while T2 is the set of the tasks waiting to be assigned. Apparently the set T consisting of all the tasks in the system is T = T1 ∪ T2. A task can be formalized as below:

$$ task_{j} = <taskID_{j},location_{j},state_{j},C_{j}({A_{j}^{t}}),t> $$
(2)

taskIDj is uesd to identify a task uniquely and taskIDj = j. locationj represents the robots current location. statei indicates the status of task j, and it can be described as below:

$$ state_{j}= \left\{\begin{array}{lllllllll} 0,& \text{if task} j \text{is not assigned;}\\ taskID_{j},& \text{if robot} i \text{takes care of it.} \end{array}\right. $$
(3)

We need to point out that \({A^{t}_{j}}\) is the accomplishment rate of taskj at time t. Clearly, \({A^{t}_{j}} \in [0, 1]\). We also define a new parameter called damaging rate function, labeled with \(C_{j} (A{R^{t}_{j}})\). It represents how much damages taskj will cause to the system in per unit of time when the accomplishment rate equals to \({A^{t}_{j}}\).

R is the set of all the robots in this system, it can be formalized as below:

$$ R = < r_{1},r_{2},...,r_{n} > $$
(4)

ri is the i th robot in the system. n = |R| represents the total number of robots. One of robots ri can be described as below:

$$ r_{i} = < robotID_{i},location_{i},state_{i},t > $$
(5)

In this formula, robotIDi uniquely identifies a robot. locationi represents the robot’s location. statei indicates the operational status of robot ri, whose value rules are demonstrated below:

$$ state_{i}= \left\{\begin{array}{lllllllll} 0,& \text{if robot} r_{i} \text{is free;}\\ taskID_{j},& \text{if} task_{j} \text{is assigned to} r_{i}. \end{array}\right. $$
(6)

We use auction as a basic approach to assign tasks, an auction can be formalised as below:

$$ A = < T_{2},B > $$
(7)

T2 is the set of tasks waiting to be assigned in this auction. B is the set of robots waiting to be assigned to tasks, in other words, bidders.

So far, if tj is assigned to bi at time t0, then under such allocation result, the damage that taskj will cause to the system can be formalized as below:

$$ cos{t^{j}_{i}} = {\int}^{{t_{0}}+{t_{1}^{ij}}}_{t_{0}} C_{j}(0)dt +{\int}_{{t_{0}}+{t^{1}_{ij}}}^{{t_{0}}+{t^{1}_{ij}}+t^{2}_{ij}} C_{j}({A^{t}_{j}})dt $$
(8)

For a certain task tj, bidder bi will calculate two time parameters: \(t^{1}_{ij}\) and \(t^{2}_{ij}\). \(t^{1}_{ij}\) represents the time it takes for bi to go to task tj . \(t^{2}_{ij}\) represents the time it takes from starting working on tj to accomplishing it.

4 Auction algorithm description

4.1 N tasks for N bidders

In this section, we consider one to one auction model of task allocation with N robots matching N rescue tasks. We use taskID and robotID to represent a task and a robot, respectively. The allocation problem to be discussed here is to minimise the damage to the whole system by matching the N robots with the N tasks, and the constraints can be expressed as the following mathematical formula:

$$ \begin{array}{lllllllll} \min\quad & \sum\limits_{i\in B} \sum\limits_{j\in T_{2}} q_{ij}cos{t_{i}^{j}} \\ \text{s.t.}\quad &\sum\limits_{j|(i,j)\in D} q_{ij} = 1,\forall i = 1,2,...,n\\ &\sum\limits_{i|(i,j)\in D} q_{ij} = 1,\forall j = 1,2,...,n\\ &q_{ij} = 0,1, \forall(i,j)\in D \end{array} $$
(9)

In this format group above, we use set D to represent the tuples of all possible distributions. It can be formalized as below:

$$ D=\lbrace (i,j)|j\in T_{2},\forall i = 1,2,...,N \rbrace $$
(10)

We use D(i) to represent the set of all tasks that can be assigned to the robot i. To reduce the complexity of the algorithm, we set the time limit using the \(\overline {t}\). If the total time of robot i solving task j is more than t, task j cannot be assigned to robot i.

$$ D(i)=\lbrace j|t_{ij}\le \overline{t}\rbrace $$
(11)

The set A is used to represent the two-tuples (i, j) consisting of robots and tasks. Each robot can have one two-tuples (i, j) ∈ A at most. Each robot can have one two-tuples (i, j) ∈ A at most either. For the set A, if there is a two-tuples(i, j) ∈ A, it means that task j is assigned to robot i.

In the algorithm, we set a positive value called 𝜖 and a price set p = {p1, ... , pn}. For robot i, if the difference between its absolute value of the relative gains obtained from task j and the optimal relative gains obtained from all the allocation schemes is not greater than 𝜖, we call robot i and task j satisfy complementary slackness condition. This two-tuples (i, j) is the optimal result, which can be described as below:

$$ |p_{j}-cos{t_{i}^{j}}-\max\limits_{k\in D(i)} \lbrace p_{k}-cos{t_{i}^{k}} \rbrace|\le \epsilon $$
(12)

The specific process of auction algorithm is described as follows:

Step 1: prepare phase

Select a 𝜖 > 0, set pk = 0, ∀k = 1, 2, ... , n, and the set of robots which are tender to the task j in the bidding phase is denoted as B(j);

Step 2: decision phase

For each robot i, if statei = 0, get the maximum relative gains ui and the assigned task ji when the maximum relative gains is obtained:

$$ u_{i}=\max\limits_{k\in D(i)}\lbrace p_{k}-cos{t_{i}^{k}} \rbrace $$
(13)

And its second relative gains vi:

$$ v_{i}=\max\limits_{k \in D(i),k\ne j}\lbrace p_{k}-cos{t_{i}^{k}} \rbrace $$
(14)

If D(i) has only one task j, we define vi as −∞.

Step 3: bidding phase

All robots bid for ji which is the most gainful task, the bidding price of the robot is determined as:

$$ a_{ij_{i}}= p_{j_{i}}-u_{i}+v_{i}-\epsilon=cost_{i}^{j_{i}}+v_{i}-\epsilon $$
(15)

Step 4: allocation phase

For each task j, if the B(j) is not empty, we update the price of the task j to the highest bid price:

$$ p_{j}=\max\limits_{i\in B(j)}a_{ij} $$
(16)

The task is assigned to the highest bidding robot ij, and at the same time, the two-tuples related to the robot ij and the task j are removed from the A which is an infeasible allocation, and the new two-tuples (ij, j) are added to the set A.

Optimization proof

In this iterative process of the algorithm, we use pj and \(p^{\prime }_{j}\) respectively to represent the price corresponding to the task before and after the iteration. In the iterative process, if robot i bids to the task ji and is successfully assigned to the task ji, its price will be updated, which can be described as follow:

$$ p^{\prime}_{j_{i}}=cost_{i}^{j_{i}}+v_{i} - \epsilon $$
(17)

Therefore, we can get the format below:

$$ p^{\prime}_{j_{i}}-cost_{i}^{j_{i}}=v_{i} - \epsilon =\max\limits_{k\in D(i),k\ne j}\lbrace p_{k}-cos{t_{i}^{k}}\rbrace-\epsilon $$
(18)

For each task j, there are \(p_{j} \ge p^{\prime }_{j_{i}}\), so:

$$ |p^{\prime}_{j_{i}}-cost_{i}^{j_{i}}-\max\limits_{k\in D(i),k\ne j} \lbrace p_{k}-cos{t_{i}^{k}}\rbrace |\le \epsilon $$
(19)

It can be seen that every two tuple (i, j) always satisfies complementary slackness condition in each iteration.

4.2 M tasks for N bidders

In the actual disaster environment, the number of rescue tasks and the number of robots cannot be guaranteed to be equal. In order to ensure the feasibility of the algorithm in different environments, it is necessary to discuss the reasonable allocation of N rescue robots and M rescue tasks. According to the number of rescue tasks, there are two kinds of situations, namely, N > M and N < M.

4.2.1 N > M

The number of rescue robots is larger than the number of rescue missions. Set the N − M virtual tasks and join the auction, we set the price of the virtual task as pj = + ∞. After all of the tasks have been assigned to the robots, robots which are assigned to operate virtual tasks can join the auction again to get real tasks until all robots have been assigned real tasks so far.

4.2.2 M > N

The number of rescue tasks is greater than the number of rescue robots, unable to deal with all tasks in a timely manner, in order to ensure the minimum loss of the system, we should select rescue tasks which can have the greater loss for priority allocation. We set M − N virtual robots to add to the allocation, and the tasks allocated to the virtual robot or the less loss task should be discarded in the allocation.

4.3 Dynamic adjustment of task assignment

Because the rescue environment of the robot is changing at all time, the results of the auction are not necessarily feasible. Also, there may be other emergencies in the process of responding to tasks. In this case, we need to adjust the task executors. In this way, we quantify the emergency results using Ej. The definition of urgency is:

$$ E_{j}=\frac{w}{\beta v} $$
(20)

In the above formula, w is the quantitative result of the severity of the disaster in the task, and the v is the speed of the task execution. β is the ratio coefficient. In the process of task execution, if Ej is greater than the set threshold h, it is considered that the execution robot cannot finish the task under the existing circumstances. Station will reassess the task and add the task to the auction list, then launch a new round of auction.

5 Experiment analysis and future work

In this paper, we proposed a new auction model and use the auction algorithm to study the multi-robot task allocation problem. Experiments show that the algorithm can effectively allocate tasks.

We chose the classical Hungarian algorithm for comparative experiments. For all cost matrices, the same optimal allocation result can be obtained by iteration. Through experiments, it is found that the results of the two task assignment algorithms are the same. For all matrices, the same optimal assignment results or the near optimal results can be obtained by iteration.

For example, when the number of tasks and robots is 5, we give the cost matrix shown in Table 1.

Table 1 Cost matrix
Full size table

The final allocation results of the two algorithms are the same:

  • Task allocation results:

    Robot r1 gets task3

    Robot r2 gets task1

    Robot r3 gets task2

    Robot r4 gets task4

    Robot r5 gets task5

  • The total cost of tasks is 13. This is a global optimal result.

For all cost matrices in the experiment, the distribution results may be different, but the total cost will be the same and the least. The two algorithms can show the same precision.

However, the proposed auction algorithm has excellent computational complexity obviously. We can improve the time complexity to a fairly low level by changing the value of 𝜖. When the size of task matrix that needs to be assigned is 250 × 250, the running time of Hungarian algorithm is 15 times that of Auction algorithm. When processing the assigned task of 500 × 500, this multiple reduced to 5. The number of tasks has a greater impact on the running time of the Hungarian algorithm than the algorithm we proposed. The time spent on auction algorithm and Hungarian algorithm is as follows (see Fig. 1).

Fig. 1
figure 1

Time cost comparison between Auction algorithm and Hungarian algorithm

Full size image

Due to the limited ability of the author, there are many deficiencies in this paper. On the one hand, there may be new tasks in the execution of tasks. For more urgent tasks, it should have priority and can be done by more agents, and the robot may need to stop the current work and perform new tasks.

On the other hand, the auction algorithm can only be terminated in the feasible distribution, so a mechanism must be added to the auction algorithm to discover the infeasibility of the problem when the problem is unsolvable. Also, the experiment we carried out in this paper are only theoretical simulation experiments. A real world experiment should be carried out later to verify the method.