Gini Coefficient-based Task Allocation for Multi-robot Systems With Limited Energy Resources

Ⅰ. INTRODUCTION

Task allocation has been a subject of multi-robot systems research for many years. Multi-robot systems, characterized as a coalition of robots working collaboratively to achieve system goals in an environment, have been widely employed in a variety of applications where tasks are complex [1], [2]. Complex tasks, referred to as multirobot (MR) tasks, are those that cannot be completed by a single robot but require multiple robots to cooperate tightly [3], [4]. It is important to ensure that the collaboration is effective in order to attain the highest level of productivity [5], [6]. So we believe that the problem of finding suitable combination of robots in a coalition of robots (for a collaborative task) is an important problem to study, and the process of task allocation can be regarded as the process of finding suitable combination in the coalition.

Much earlier work studied the multi-robot systems in abstract domains, where conditions in the real world could be eliminated or relaxed [7]. For example, in a search and rescue mission, a set of robots are required to form different coalitions (i.e., individual robot may not have all the capabilities for a complex task) for the different types of tasks (i.e., a coalition responsible for the search tasks, a coalition responsible for the rescue tasks) to search for and rescue more victims as soon as possible [8], [9]. In practice, the energy resources of each robot such as fuel or electricity are limited, because the resource supply cannot be guaranteed on these occasions, and they will be finally depleted as the robot executes tasks in the harsh environment. But in the majority of existing related works, researchers seldom pay much attention to the problem of energy resources constraints of multi-robot systems, and robots were often assumed to possess sufficient energy resources to accomplish the task inherently.

Therefore, we will focus on the task allocation elements of a multi-robot framework for dealing with search and rescue and other similarly dangerous environments. In these application contexts, the coalition must complete as many tasks as possible using their limited resources (in this paper, fuel or electricity is referred to as resource). In view of this, studying a task allocation mechanism for maximizing the number of tasks completed, while minimizing the resources consumption, has a realistic significance. In this paper, the MRTA (multi-robot task allocation) problem which we studied belongs to the ST-MR-TA (single-task robots, multi-robot tasks, time-extended assignment) task allocation type. ST means that each robot can execute at most one task at a time, MR means that some tasks require multiple robots, and TA means that more information is available, such as the set of all tasks that will need to be assigned [3]. From the angle of the resource consumption per task, the distributed approaches complemented with auction based method, which are often called market-based approaches [10]-[17], give somewhat better solution. Therefore, our research mainly focuses on finding a good approach to maximize the number of completed tasks of coalition, and makes a try to combine this approach with market-based approach to maximize the number of tasks each completed while minimizing resources consumption of task in view of the task situation. Our main contributions are presented as follows:

1) Our key contribution is to innovatively introduce the Gini coefficient of economics to measure the "resource difference degree'' of the residual resources of robots, and propose a Gini coefficient-based task allocation method for the task allocation problem of multi-robot systems with energy resource constraints. Specifically, the Gini coefficient-based method includes four steps, respectively, combinations formation, residual resources calculation, Gini coefficient calculation and optimal combination selection. This method positions a robot coalition appropriately in preparation for dynamic future tasks by balancing resources distribution among robots, and extends the combined operational lifetime of the coalition and maximizes the number of tasks completed.

2) We propose a hybrid algorithm that combines the proposed Gini coefficient-based method with market-based mechanism to pursue the two optimization objectives of "maximizing the number of tasks completed" and "minimizing resource consumed". Furthermore, we propose a selection algorithm for selecting the optimal value of set G (i.e., Gini coefficient), which can determine the method conversion inflection point for our hybrid algorithm in advance, and achieve the objectives of the system flexibly according to the application context.

3) Extensive simulations are conducted for evaluating the effectiveness of the proposed task allocation methods. The experimental results show that the Gini coefficient-based method can cause the residual resources converge to each other and make a simultaneous exhaustion of all robots, which effectively controls the resource difference degree and keeps the multi-robot system having a maximal synergism over time. Under the different experimental setting, Gini coefficient-based method can always make multi-robot system complete more tasks than using market-based method, and the hybrid method which combines the advantages of both methods can make a balance between the resource consumption and the number of tasks completed according to their relative importance degree.

The remainder of this paper is organized as follows. Section Ⅱ summarizes and analyzes the previous woks on MRTA problem. We define the problem of task allocation with resource constraints in Section Ⅲ. The relationship between Gini coefficient and resource difference, two task allocation approaches, are presented in Section Ⅳ. In Section Ⅴ, we provide experimental results to validate our proposed methods. Finally, we summarize our results and conclude with some open questions in Section Ⅵ.

Ⅱ. RELATED WORKS

We have mentioned in the introduction, this paper mainly studies the task allocation of multi-robot system with resources constraints in the search and rescue or other emergency and dangerous environments. In these cases, the working space of robots is relatively narrow, which limits the number of robots. But the complex tasks, such as scene detection and wounded rescue, often require multiple robots to cooperate. Therefore, this article studies the situation that the multi-robot system performs one task at a time. Less number of the robots and the global optimal targets of task allocation make us believe that the centralized mechanism is more appropriate. Therefore, we will set a special management agent to take the charge of task allocation of multi-robot system. The management agent located at a computer node, which is responsible for receiving the tasks (Tasks are produced by the rescuers after they analyze the field data), is analyzing the status of energy consumption of each robot, and making the task allocation decisions.

Section Ⅱ is divided into two parts. The market-based task allocation mechanisms are investigated in Section Ⅱ-A, and works in the field of coalition-based approach to task allocation are briefly surveyed in Section Ⅱ-B.

A Market-based Task Allocation Mechanism

The common feature in market-based allocation mechanism is an auction protocol to coordinate tasks between different robots or between different components of the same robot. When an auction is announced, robots compute bids based on their expected profit for the tasks and the robots with the lowest cost bid are awarded contracts [10]. Gerkey and Matari presented a dynamic task allocation mechanism using a publish/subscribe communication method for a heterogeneous robot coalition, and tasks are allocated dynamically via a sequence of first-price single-round auctions in a greedy fashion [11]. Dias et al. introduced the TraderBots architecture in which robots are modeled as self-interested agents with the goal of maximizing individual profits [12]. Choi et al. addressed task allocation to coordinate a fleet of autonomous vehicles by presenting two decentralized algorithms, these algorithms utilize a market-based decision strategy as the mechanism for decentralized task selection [13]. Viguria and Howard used a market-based approach for addressing the initial formation problem [14]. Hu et al. distributed the subtasks with a market-based dynamic task allocation method to cope with unexpected changes in the environment and the limited sensing range of the robotic fish [15]. Zlot et al. extended market-based approaches by generalizing task descriptions into task trees, which allow tasks to be traded in a market setting at variable levels of abstraction [16]. Dash et al. extended the standard Vickrey-Clarke-Groves mechanism to allow for multi-attribute bids and introduced a novel penalty scheme such that producers are incentivized to truthfully report their capacities and their costs [17].

But in these works, resource constraints between robots and tasks and how resource constraints will affect achieving the goal of system have not been extensively considered. When individuals pursue resources consumption minimization under the market-based task allocation mechanism, due to the capability heterogeneity of robots, the robots coalition may fail in the task execution when some robots are subject to insufficient resources.

Therefore, an efficient task allocation approach should not only focus on finding a set of robots that have the necessary capacities or assigning tasks to robots in a greedy way so that short-term goals are met. In this paper, we will study how the different combinations affect the resource equilibrium of the robots of multi-robot coalition before each combination performs task, which is good for us to choose a combination that can make the robot system meet the long-term goal of completing tasks as much as possible under the limited resource constraints, avoiding the fast resource consumption of a robot.

B Coalition-based Approach to Task Allocation

Due to the inherent difficulty and complexity of real world tasks, cooperation amongst robots is essential for successful task completion [18]. So, in past few years, forming coalitions to solve the MRTA problem has become increasingly important worldwide [19]. With the coalition-based MRTA architecture, a coalition of robots is divided into several sub-coalitions and each sub-coalition is assigned to a task. These sub-coalitions are called coalitions [20].

In recent years, the coalition-based approaches for task allocation of multiple robots or embedded systems with resource constraints begin to be studied [21]-[24]. Reference [21] analyzed the resource constraints when robots implement tasks, and proposed leader-follower coalition algorithms to resolve resource constrained task allocation problem. Xie and Qin [22] proposed a novel balanced energy-aware task allocation (BEATA) algorithm for heterogeneous networked embedded systems. BEATA algorithm aims at making the best trade-off between energy saving and schedule length. However, the residual energy of embedded systems are not taken into account for choosing processing nodes, which ultimately results in that some nodes are chosen frequently and hence they die early. Wang et al. [23] proposed the energy-balanced centralized and distributed algorithms to efficiently dispatch mobile sensors in a hybrid WSN, and they can be applied for any number of mobile sensors and event locations. In the centralized load balanced sensor dispatch algorithm (CentralLBSD), when there are more mobile sensors, it translates the sensor dispatch problem into a maximum matching problem in a weighted complete bipartite graph. In the process of the actual matching, the central LBSD algorithm does not consider the balance degree of surplus resources of different mobile sensors, and it only considers to balance the energy consumption of each node and minimize the total energy consumption. Lukic et al. [24] described the novel centralized and distributed algorithms for the task assignment problem in wireless sensor and robot networks, with arbitrary number of robots and events. They allow robots to handle multiple events, and events to be handled by desired number of robots. The goal is to minimize the average travel path by robots and maximize the number of iterations for handling events. They combine matching and sequence dispatch approaches, but the more challenging problem of simultaneous presence of several robots at the scene is not discussed. These show that again, we should propose a task allocation method to control the resources consumption process and position the multi-robot system appropriately in preparedness for dynamic future events.

Ⅲ. NOTATIONS AND ASSUMPTIONS

The notations used in this paper and their definitions are shown in Table Ⅰ.

Table  Ⅰ.  THE NOTATIONS USED IN THIS PAPER

Notation	Definition
$r_i$	Robot $i$
$R$	A coalition of robots, $R=\{r_1, r_2, \ldots, r_n\}$
$r_{ik}$	Robot $i$ in capability $k$ (a non-negative integer) and it is zero if the robot does not have that capability
$V_i^r$	A capability vector of each robot, $V_i^r=\{r_{i1},$ $r_{i2}, \ldots, r_{im}\}$ , where $m$ denotes the number of capacities of a coalition
$re_i$	The residual resources of robot $i$
$V^{re}$	A residual resources vector of the coalition, $V^{re}=$ $\{re_1, re_2, \ldots, re_n\}$
$rc_{ik}$	The resources consumed of robot $i$ in capability $k$ (a non-negative integer) and it is zero if the robot does not have that capability
$V_i^{rc}$	A resource consumption vector of each robot, $V_i^{rc}=$ $\{rc_{i1}, rc_{i2}, \ldots, rc_{im}\}$
$t_j$	Task $j$
$T$	A set of tasks, $T=\{t_1, t_2, \ldots\}$ , in this paper, we try to select the suitable robots combination in one coalition for the assigned task efficiently
$t_{jk}$	The required number of task $j$ in capability $k$ (a non-negative integer) and it is given zero if the task does not require that capability
$V_t^j$	A capability requirement vector of each task, $V_t^j=$ $\{t_{j1}, t_{j2}, \ldots, t_{jm}\}$
$V^R$	A capability vector of the coalition: $V^R=\sum\nolimits_{i=1}^n V_i^r=(\sum\nolimits_{i=1}^n r_{i1},$ $\sum\nolimits_{i=1}^n r_{i2},$ $\ldots,$ $\sum\nolimits_{i=1}^n r_{im})$ . In this paper, we assume that the capability vector $V^R$ of the coalition is not less than the capability requirement vector $V_j^t$ of the task, i.e., $\exists t_{jk}$ $\leq \sum\nolimits_{i=1}^n r_{ik}$ , $\forall 1\leq k\leq m$
$c_{jx}$	A robot combination $x$ that can execute the task $t_j$ , the number of robots of each combination is not more than the number of robots of the coalition
$V_j^c$	A set of combinations for each task, $V_j^c=$ $\{c_{j1},$ $c_{j2}, \ldots\}$

 | Show Table

DownLoad: CSV

Then the problem is to maximize the number of tasks completed by the coalition while minimizing resources consumption in view of the task situation. Following are assumptions with which we characterize our problem:

1) There is no chance for robots to recharge their resources until they finish a mission.

2) The robot coalition has been formed before task allocation. In this paper, multi-robot coalition formation problem will not be discussed.

3) The tasks are online assigned to the coalition one by one, under normal circumstances, there are dependencies among some tasks, so we assume the task $t_j$ cannot be assigned when $t_{j-1}$ is not finished.

4) There is an agent being responsible for making a task allocation choice among several combinations for a specific task.

5) Capability requirement $t_{jk}$ can be executed by any robot having the capability $k$ if the resources of the robot are enough.

6) The resource consumption that a robot spends on using a capability for a particular task can be estimated by multiplying the weight of the task by corresponding capability element in robot's resource consumption vector $V_i^{rc}$ .

Ⅳ. GINI COEFFICIENT-BASED APPROACH AND ITS COMBINATION WITH MARKET-BASED APPROACH

In the market-based task allocation approach, the task is auctioned off to a robot bidding with the least cost. This approach minimizes the resource consumption of each task, but it may lead to rapid resource consumption of some robots. In this case, the completion of follow-up tasks will be affected. For example, there is a robot that has two capabilities, $A$ and $B$ , the robot can perform $A$ with relatively less resource than other robots, and $B$ is a unique capability that exists only on this robot. According to the market-based approach, when the capability requirement vectors of some tasks have $A$ , the robot will be excessively used, causing its resources to consume quickly, shortly afterwards, the task could not be assigned to the coalition when it requires $B$ . Therefore, we should use a method to balance the resources of robots, i.e., retain as many robots as possible to execute more tasks. In this paper, we turn to the Gini coefficient of economics.

A Gini Coefficient and Resource Difference Degree

Gini coefficient was proposed by famous Italian economist C. Gini on the basis of the Lorenz curve in 1912, now it has been an important international analysis indicator used to make a comprehensive investigation on residents internal income distribution difference. The most prominent feature of the Gini coefficient is integrity, which can clearly show the income inequality of the residents of a region as a whole. Also because of its integrity, when a region has a less number of the individual residents, the effectiveness of the Gini coefficient is higher. That is, even the Gini coefficient of a region with large individual number is small, the income inequality difference among some individuals may be quite large, which makes Gini coefficient invalid in a certain sense.

We define a new metric "resource difference degree" to indicate how unevenly resources are distributed among the robots of a coalition, and introduce the Gini coefficient as the measurement index for resource difference degree.

Gini coefficient refers to the proportion of the area $A$ divided by $A$ $+$ $B$ , as shown in Fig. 1. When the Gini coefficient is applied to measure the resource difference degree of the robots, $A$ is the area surrounded by actual Lorenz curve and resource absolute no difference curve, and $A + B$ is the surrounded area by absolute no difference curve and absolute difference curve. Here, the Lorenz curve qualitatively reflects the resource difference degree roughly.

Figure  1.  The schematic diagram of Gini coefficient

DownLoad: Full-Size Img PowerPoint

Gini coefficient is expressed as

We can see by (1), the value of Gini coefficient is between 0 and 1, very close to 0 indicates the resources of robots more equal, very close to 1 indicates the resources of robots more unevenly distributed. When Gini coefficient takes the minimum value 0, it means all the robots of this coalition have the same resources, resource difference degree is 0.

In the schematic diagram of Gini coefficient (Fig. 1), abscissa axis denotes the percentage of robot number accumulation to per coalition, ordinate axis denotes the percentage of resources accumulation to per coalition, the total area is 1, and the sum of $A$ and $B$ is 0.5, so,

If the Lorenz curve equation is $r = L (x),$ the integral expression of Gini coefficient is

Because the Lorenz curve is an irregular curve, the area $B$ cannot be calculated directly, many scholars made explorations on the concrete calculation method of Gini coefficient, and proposed several different calculation formulas. Zhang put forward a simple and easy formula using approximate trapezoidal area instead of area $B$ , as shown in (4). Detailed derivation process can be seen in [25].

According to the calculation of (4), $n$ robots are permutated from small to large according to the quantity of resource, and $W_i$ denotes the percentage of accumulated resources from the first robot to the robot $i$ of all the total resources of the robots.

B Gini Coefficient-based Task Allocation Approach

As mentioned above, in rescue, robots need to use their limited resources to quickly execute as many tasks as possible. In this paper, we will utilize Gini coefficient which has been used to measure the resource difference degree as the decision basis of task allocation, and strive to keep the residual resource difference of robots minimum after each task completed. This can improve the reserve capability of the coalition for the subsequent tasks, and make coalition complete more tasks. We call this task allocation method as the Gini coefficient-based method, and the method expressed in pseudo code is shown as Algorithm 1.

Algorithm 1 is described concretely as follows:

Algorithm 1. Gini coefficient-based task allocation method
1: procedure
2: set $V_i^r$ of each robot $i$
3: set $V_j^t$ of each robot $j$
4: set the initial resources of each robot
5: for all $t_j$ in $T$ do
6: for all $t_{jk}$ in $V_j^t$ do
7: add all $r_{ik}$ to $array_k$
8: end for
9: for all $r_{i1}$ in $array_1$ do
10: for all $r_{i2}$ in $array_2$ do
11: $\vdots$
12: for all $r_{ik}$ in $array_k$ do
13: traversing the $V_j^c$
14: if $c_{jx}\in V_j^c$ can execute the task
15: save $c_{jx}$ to the buffer array
16: end if
17: end for
18: $\vdots$
19: end for
20: end for
21: residual resources calculation
22: sorting in ascending order the residual resources of robots of $c_{jx}$
23: calculating the Gini coefficient of $c_{jx}$
24: If the number of elements in buffer array is not equal to 0
25: choose the combination corresponding to the minimum Gini coefficient to execute task $t_j$
26: output: Task has been executed
27: else
28: output: Task has interrupted
29: end if
30: end for
31: end procedure

 | Show Table

DownLoad: CSV

1) Combinations Formation

For a task $t_j$ , there can form various robot combinations within the coalition according to each robot's capability vector $V_i^r$ and the capability requirement vector $V_j^t$ (Line 9-15).

In order to be easily understood, we will make an illustration in the following parts.

Assuming $V_j^t=\{1, 2, 0\}$ , where 1 denotes needing one unit of capability 1, 2 denotes needing two units of capability 2, 0 denotes there is no need for capability 3; $R=\{r_1, r_2, r_3\}$ , $V_1^r$ $=$ $\{1, 1, 0\}$ , $V_2^r=\{1, 1, 0\}$ , $V_3^r=\{1, 0, 1\}$ . So a set of combinations $V_j^c$ that can perform task $t_j$ can be expressed specifically as Table Ⅱ.

Table  Ⅱ.  A SET OF COMBINATIONS $V_j^c$ THAT CAN PERFORM TASK $t_j$

$V_j^t$	$V_j^c$	$r_1$	$r_2$	$r_3$
$\{1, 2, 0\}$ }	$c_{j1}$	$\{1, 1, 0\}$	$\{0, 1, 0\}$	$\{0, 0, 0\}$
	$c_{j2}$	$\{0, 1, 0\}$	$\{1, 1, 0\}$	$\{0, 0, 0\}$
	$c_{j3}$	$\{0, 1, 0\}$	$\{0, 1, 0\}$	$\{1, 0, 0\}$

 | Show Table

DownLoad: CSV

2) Residual Resources Calculation

Residual resource calculation finds the residual resources of each robot after each combination executing the task $t_j$ (Line 21). Assume that each robot's initial resources number is 2000, all for 2000, $V_1^{rc}=\{90, 80, 0\}$ , $V_2^{rc}=\{50, 70, 0\}$ , $V_3^{rc}$ $=$ $\{80, 0, 90\}$ , and the weight of the task is 1, so the total resource consumption $rc_i$ and the residual resources $re_i$ of each robot are shown in Table Ⅲ.

Table  Ⅲ.  THE RESIDUAL RESOURCES OF EACH ROBOT AFTER EACH COMBINATION EXECUTES THE TASK $t_j$

Initial resources	$V_j^c$	$rc_1$	$re_1$	$rc_2$	$re_2$	$rc_3$	$re_3$
2000	$c_{j1}=\{\{1, 1, 0\}\ \{0, 1, 0\}\ \{0, 0, 0\}\}$	170	1830	70	1930	0	2000
	$c_{j2}=\{\{0, 1, 0\}\ \{1, 1, 0\}\ \{0, 0, 0\}\}$	80	1920	120	1880	0	2000
	$c_{j3}=\{\{0, 1, 0\}\ \{0, 1, 0\}\ \{1, 0, 0\}\}$	80	1920	70	1930	80	1920

 | Show Table

DownLoad: CSV

3) Gini Coefficient Calculation

After each combination performing $t_j$ simulantly, Gini coefficient calculation sorts the residual resources of all robots in coalition from less to more (Line 22), and then calculates the Gini coefficient ( $G$-value) of the coalition according to the (4) (Line 23). The specific calculation process is as follows:

4) Optimal Combination Selection

It refers to select the robot combination corresponding to the minimum $G$-value to execute task $t_j$ (Line 24-28).

C Market-Gini Coefficient-based Task Allocation Approach

For a given set of tasks, market -based method can make the robot coalition consume the least resources when executing each task, but in general, the number of task completion is fewer; Gini coefficient-based method can make the coalition consider the executive capability for the future tasks by keeping the resource difference degree minimum, so it can complete more tasks within the limited resources, but the average resource consumed per task may increase. Two methods have own advantages and disadvantages, therefore, we will combine the advantages of Gini coefficient-based method and marked-based method put forward a hybrid method, namely, market-Gini coefficient-based method. The algorithm of hybrid method is shown as Algorithm 2.

Algorithm 2. Market-Gini coefficient-based task allocation method
1: procedure
2: set $V_i^r$ of each robot $i$
3: set $V_j^t$ of each robot $j$
4: set a $G$-value
5: set the initial resources of each robot
6: for ${\rm all} t_j {\rm in} T$ do
7: Algorithm 1 is described concretely as follows: calculate the Gini coefficient of the coalition
8: if the Gini coefficient is equal or greater than the value of set $G$ then
9: implement Gini coefficient-based method
10: else
11: implement market-based method
12: end if
13: end for
14: end procedure

 | Show Table

DownLoad: CSV

The idea of the hybrid method: setting a value of $G$, using the market-based method to allocate tasks at the beginning stage (Line 10-11), then using the Gini coefficient-based method when the $G$-value of the coalition is greater than or equal to the set $G$-value in execution process (Line 8-9).

The setting of $G$-value is influenced by many factors, such as the relative importance between task completion number and average consumption of each task, the size of the robot coalition, the degree of heterogeneity, the resource levels of robots, the number of tasks, and so on (the verification of influence can be seen in Sections Ⅴ-A-2, Ⅴ-B-2 and Ⅴ-C-2. According to the provisions of the relevant organization of United Nations, the Gini coefficient below 0.2 denotes the income absolute average; 0.2 to 0.3 denotes relative average; 0.3 to 0.4 denotes relatively reasonable; 0.4 to 0.5 denotes the income inequality relatively large; more than 0.5 denotes a huge income gap. Therefore, we make 0.5 as the upper limit of the set value of $G$, and $0\leq G\leq 0.5$ . In fact, when the set $G$ equals to 0, Gini coefficient-based method is used to allocate tasks only. There will be a kind of situation: the same task completion number and the same average resources consumed per task under different relatively big set value of $G$. This is because before reaching the set value, resources of some robots have been fast consumed during the execution process with market-based method, and the task allocation has been interrupted before using the Gini coefficient-based method.

As we mentioned above, $G$ can take any value between 0 and 0.5. We will downsize the value range to make it possible for using the ideal point method of the multi-objective evaluation function to select the optimal value of $G$ as a set point to the actual task allocation. The selection algorithm for the optimal set value of $G$ is shown as Algorithm 3.

Algorithm 3. The selection algorithm for the optimal set value of $G$
1: procedure
2: set $V_i^r$ of each robot $i$
3: set $V_j^t$ of each robot $j$
4: set $G=\{0, 0.1, 0.2, 0.3, 0.4, 0.5\}$
5: set the initial resources of each robot
6: for all $g_i$ in $G$ do
7: for all $t_j$ in $T$ do
8: calculate the Gini coefficient of the coalition
9: if the Gini coefficient is equal or greater than $g_i$
10: implement Gini coefficient-based method
11: else
12: implement market-based method
13: end if
14: end for
15: input the number of tasks completed to $infor$
16: input average resource consumed per task to $infor$
17: end for
18: select the maximum task completion number as $f_1^0$ and the minimum average resource consumed per task as $f_2^0$
19: input $\lambda_1$, $\lambda_2$
20: for each pair in $infor$ do
21: calculate $U(x)$
22: end for
23: select the corresponding $G$-value of minimum $U(x)$
24: output the optimal set value of $G$
25: end procedure

 | Show Table

DownLoad: CSV

1) Set $G$ equals $0, 0.1, 0.2, \ldots, 0.5$ , respectively (Line 4), for a given set of tasks, making the simulation allocation according to the market-based method at the beginning stage, then use the Gini coefficient-based method when the $G$-value of coalition is greater than or equal to the set value in execution process (Line 5-14).

2) Record the number of tasks completed $f_1(x)$ and the total resource consumption (Line 15-16), total resource consumption divided by the task completion number is the average resource consumption per task $f_2(x)$ . Now, we can acquire the maximum task completion number $f_1^0$ and the minimum average resource consumed per task $f_2^0$ (Line 18).

3) Structuring the multi-objective evaluation function $U(x)$ ((5) or (6)), calculating $U(x)$ under each set value of $G$, (Line 19-22), and taking the $G$-value corresponding to the minimum $U(x)$ as the set value of $G$ in the actual process of task allocation (Line 23-24).

We construct multi-objective evaluation function based on the weighted ideal point method, as shown in (5):

$\lambda_1$ and $\lambda_2$ are the nonnegative weights, which are used to measure the relative importance of the task completion number and the average resource consumed per task, $\lambda_1+\lambda_2=1$ . $\lambda_1$ and $\lambda_2$ can be omitted when the importance of the number of tasks completed and the average resource consumed per task are fair, now (5) becomes:

$\lambda_1$ and $\lambda_2$ are the nonnegative weights, which are used to measure the relative importance of the task completion number and the average resource consumed per task, $\lambda_1+\lambda_2=1$ . $\lambda_1$ and $\lambda_2$ can be omitted when the importance of task completed number and average resource consumed per task is fairly, now (5) becomes:

Ⅴ. EXPERIMENTS

In this part, we have performed three simulation experiments. In the simulation experiments, the coalition executes a task every time. The different type of unit capability requirements of a task must not exist on the same robot or on different robots but the same type of unit capability requirements must exist on different robots. Tasks are generated randomly and injected into the coalition one by one. The capability requirement of a task involves three types of capability, each task can be executed when the resources of corresponding robots are enough. The estimated resources consumption that a robot spends on using a capability for a particular task is obtained by multiplying the weight of the task by corresponding capability element in the robot's resource consumption vector. It is assumed that a task is immediately finished when all members of selected combination arrive at the task. Robot parameters used in experiments are as shown in Table Ⅳ.

Table  Ⅳ.  ROBOT PARAMETERS USED IN EXPERIMENTS

$R$	Capability vector ( $V_i^r$ )	Resource consumption vector ( $V_i^{rc}$ )	Initial resources
			Balanced	Unbalanced
$r_1$	$\{1, 1, 0\}$	$\{90, 80, 0\}$	2000	1850
$r_2$	$\{1, 1, 0\}$	$\{50, 70, 0\}$	2000	2460
$r_3$	$\{1, 0, 1\}$	$\{80, 0, 90\}$	2000	2900
$r_4$	$\{0, 1, 1\}$	$\{0, 90, 70\}$	2000	2750
$r_5$	$\{1, 1, 1\}$	$\{50, 60, 80\}$	2000	2600

 | Show Table

DownLoad: CSV

A Same and Different Initial Resources of Robots

We use the same robot coalition including four robots ( $r_1$ to $r_4$ in Table Ⅳ) and the same task set including forty tasks to carry out experiments in the conditions of the same and different initial resources of robots.

Section Ⅴ-A-1 compares the average number of tasks completed and average resource consumed per task of robot coalition under the market-based method, the centralized load-balanced sensor dispatch (CentralLBSD) algorithm [23], the Gini coefficient-based method and the market-Gini coefficient-based method, and shows the resource consumption process of the market-based method and Gini coefficient-based method, which can illustrate each method's influence on resources reserve capability of robot coalition for the future tasks, and intuitively explain the reason of using the Gini coefficient-based method which can complete more tasks than using market-based method. Section Ⅴ-A-2 validates that the initial resources of robots have the influence on the optimal $G$-value setting in the hybrid method.

As we mentioned in Section Ⅱ, the CentralLBSD algorithm is used to solve the dispatch problem of mobile sensor nodes. The idea is to minimize their moving energy while keeping their energy consumption balanced after each round. In this paper, we use CentralLBSD to allocate tasks among different robots. We make every unit capacity requirement as an event, and make every robot as a sensor node. Each unit capacity requirement needs a robot having the corresponding capacity.

1)Comparison of the Average Number of Tasks Completed and the Average Resource Consumed Per Task

We have run the experiment for 30 times. Each time we have produced a task set including forty tasks randomly as the test case.

Figs. 2-4 intuitively show the average number of tasks completed, the changing process of resources of each robot in a test case and the average resource consumed per task.

Figure  2.  Average number of tasks completed under three methods. (a1) and (a2), the same initial resources of robots (in the hybrid method, $\lambda_1$ $=$ $\lambda_2$ ); (b1) and (b2), different initial resources of robots (in the hybrid method, $\lambda_1=\lambda_2$ )

DownLoad: Full-Size Img PowerPoint

Figure  3.  Residual resources of robots over time. (a) market-based in balanced condition; (b) Gini coefficient-based in balanced condition; (c) market-based in unbalanced condition; (d) Gini coefficient-based in unbalanced condition

DownLoad: Full-Size Img PowerPoint

Figure  4.  Average resource consumed per task under three methods. (a1) and (a2), the same initial resources of robots (in the hybrid method, $\lambda_1$ $=$ $\lambda_2$ ); (b1) and (b2), different initial resources of robots (in the hybrid method, $\lambda_1=\lambda_2$ )

DownLoad: Full-Size Img PowerPoint

As illustrated in Fig. 2, when we use the same robot coalition with the same task set in the conditions of the robots having the same and different initial resources, the number of tasks completed by Gini coefficient-based method is higher than the one obtained by the market-based method. Using the market-Gini coefficient-based method, no matter $G$ takes which set value, the number of tasks completed is not less than using the market-based method. About CentralLBSD algorithm, we will make comparison with market-Gini coefficient-based method combined with average resource consumed per task after showing Fig. 4.

Fig. 3 intuitively explains why the number of tasks completed using the Gini coefficient-based method is more than using the market-based method. Regardless of the robots have the same (Fig. 3 (a) and (b)) or different initial resources (Fig. 3 (c) and (d)), the residual resources of four robots under the market-based method gradually diverge over time, eventually resulting in early exhaustion of two robots. In contrast, the Gini coefficient-based method causes the residual resources converge to each other even in the unbalanced setup, and makes the resources of all robots exhaust simultaneously. The method effectively controls the resources difference degree of the coalition and gives full consideration to the resource reserves for the subsequent tasks, thereby, the robot coalition can keep maximal synergism over time.

The total resource consumption of coalition divided by the number of tasks completed is the average resource consumed per task, as illustrated in Fig. 4. It is obvious that, when we use market-based method, in general, the average resource consumed per task is lower than the Gini coefficient-based method; when we use market-Gini coefficient-based method, the average resource consumed per task under different set $G$-values is not more than using Coefficient-based method in general.

When using the CentralLBSD algorithm to allocate tasks, Fig. 2 (a1), (b1) and Fig. 4 (a1), (b1) show that the average number of tasks completed is more than using the marked-based method, and the average resource consumed per task is less than Gini coefficient-based method. However, CentralLBSD algorithm's flexibility is obviously inadequate compared with market-Gini coefficient-based method. Market-Gini coefficient-based method can set the different optimal values of $G$ according to the different application environments. In addition, when the number of completed tasks of CentralLBSD is close to market-Gini coefficient-based method, the average resource consumed per task is more than market-Gini coefficient-based method, such as in the condition of the same initial resources of robots, the task completion number of CentralLBSD is 25.2 ((Fig. 2 (a1)), which is close to 25.7 and 24.2 when the setting value of $G$ is 0.2 and 0.3 respectively (Fig. 2 (a2)), and the average resource consumed per task of CentralLBSD is 295.5 (Fig. 4 (a1)), which is more than the 293.2 and 288.8 when the setting value $G$ is 0.2 and 0.3 respectively (Fig. 4 (a2)). The case under different initial resources of robots is also like this. In a word, the results prove the advantage of market-Gini coefficient-based method in realizing the dual optimization objectives.

In conclusion, the experiment results prove that no matter what initial resources the robots possess, the Gini coefficient-based method in task allocation can effectively improve the number of tasks completed by robot coalition, and the market-Gini coefficient-based method can make a balance between the number of tasks completed and the resource consumption according to their importance degree.

2) Whether the Initial Resources of Robots Have an Influence on Optimal $G$-value Setting?

The purpose of this experiment is to validate whether the initial resources of robots have an influence on $G$-value setting under the same task set and the same robot coalition conditions.

We choose five pairs of ( $\lambda_1$ , $\lambda_2$ ) to represent the relative importance of the number of tasks completed and the average resource consumed per task, then utilize the selection algorithm for the $G$-value setting to calculate the optimal $G$-values under the same and different initial resources setups, as shown in Table Ⅴ.

Table  Ⅴ.  THE OPTIMAL $G$-VALUE UNDER THE SAME AND DIFFERENT INITIAL RESOURCES SETUPS

Initial resource	$\lambda_1$ , $\lambda_2$
	$(1, 1)$	$(0.1, 0.9)$	$(0.1, 0.9)$	$(0.1, 0.9)$	$(0.1, 0.9)$
Same	0.2	0.3	0.3	0.2	0.1
Different	0.0	0.2	0.0	0.0	0.0

 | Show Table

DownLoad: CSV

From Table Ⅴ, we can conclude that the $G$-value setting in the market-Gini coefficient-based method is influenced by the initial resources setup of the robots.

B Different Numbers of Robots

This experiment uses different numbers of robots with the same task set under the condition that the robots have the same initial resources. Part 1) compares the average number of tasks completed and the average resource consumed per task by using market-based method, the centralized load-balanced sensor dispatch (CentralLBSD) algorithm [23], Gini coefficient-based method and market-Gini coefficient-based method. Part 2) validates the influence of the number of robots on the optimal $G$-value setting in the hybrid method.

1) Comparison of the Average Number of Tasks Completed and the Average Resource Consumed Per Tasks

We have run the test for thirty times. Each time we have produced a task set including sixty tasks randomly as the test case, and we respectively allocate tasks to two robot coalitions. The first coalition contains three robots ( $r_1$ to $r_3$ in Table Ⅳ), and the second contains five robots ( $r_1$ to $r_5$ in Table Ⅳ), the robots are initially endowed with the same amount of resources. Figs. 5 and 6 intuitively compare the average number of tasks completed and the average resource consumed per task in thirty tests.

Figure  5.  Average number of tasks completed under three methods. (a1) and (a2), three robots (in the hybrid method, $\lambda_1=\lambda_2$ ); (b1) and (b2), five robots (in the hybrid method, $\lambda_1=\lambda_2$ )

DownLoad: Full-Size Img PowerPoint

Figure  6.  Average resource consumed per task under three methods. (a1) and (a2), three robots (in the hybrid method, $\lambda_1=\lambda_2$ ); (b1) and (b2), five robots (in the hybrid method, $\lambda_1=\lambda_2$ )

DownLoad: Full-Size Img PowerPoint

Fig. 5 shows the average number of tasks completed by three different methods respectively when we use different numbers of robot with the same task set under the condition that the robots have the same initial resources. We observe that the average number of tasks completed by Gini coefficient-based method is higher than the one obtained by market-based method. In the market-Gini coefficient-based method, no matter $G$ adopts which set point, it can complete more tasks than the market-based method. Furthermore, with some set points, the average number of tasks completed is more than Gini coefficient-based method, which reflects the advantage of hybrid method clearly. About CentralLBSD algorithm, we will make comparison with market-Gini coefficient-based method combined with average resource consumed per task after showing Fig. 6.

The total resource consumption of coalition divided by the number of tasks completed is the average resource consumed per task, as illustrated in Fig. 6. It is obvious that, when we use the market-based method, in general, the average resource consumed per task is lower than the Gini coefficient-based method; when we use the market-Gini coefficient-based method, the average resource consumed per task under different $G$-values is no more than using Gini coefficient-based method. Furthermore, with some set points (Fig. 6 (a2)), the average resource consumed per task is less than the market-based method, which reflects the advantage of hybrid method clearly.

When using the CentralLBSD algorithm to allocate tasks, Fig. 5 (a1), (b1) and Fig. 6 (a1), (b1) show that the average number of tasks completed is more than using the marked-based method, and the average resource consumed per task is less than using the Gini coefficient-based method under the condition of different numbers of robots. However, CentralLBSD algorithm's flexibility is obviously inadequate compared with market-Gini coefficient-based method. In addition, when the task completion number of CentralLBSD is close to market-Gini coefficient-based method, the average resource consumed per task is more than market-Gini coefficient-based method, such as the task completion number of CentralLBSD is 22.7 ((Fig. 5 (a1)), which is close to 23.0 and 22.5 when the value of $G$ is 0.3 and 0.4 respectively (Fig. 5 (a2)), and the average resource consumed per task of CentralLBSD is 228.1 (Fig. 6 (a1)), which is more than the 224.0 and 222.0 when the setting value $G$ is 0.3 and 0.4 respectively (Fig. 6 (a2)). The results prove the advantage of market-Gini coefficient-based method in realizing the dual optimization objectives.

In conclusion, the experiment results prove that no matter what number of robots, the Gini coefficient-based method in task allocation can effectively improve the number of tasks completed by the coalition, and the market-Gini coefficient-based can make a balance between the number of tasks completed and the resource consumption according to their importance degree.

2) Whether the Size of the Robot Coalition Has an Influence on Optimal $G$-value Setting?

The purpose of this experiment is to validate whether the size of the robot coalition has an influence on $G$-value setting with the same task set and the same initial resources of robots.

We choose five pairs of ( $\lambda_1$ , $\lambda_2$ ) to represent the relative importance of the number of tasks completed and the average resource consumed per task, then utilize the selection algorithm for the $G$-value setting to calculate the optimal $G$-values under different numbers of robot, as shown in Table Ⅵ. From Table Ⅵ, we can conclude that the $G$-value setting in market-Gini coefficient-based method is influenced by the size of the robot coalition.

Table  Ⅵ.  THE OPTIMAL $G$-VALUE UNDER DIFFERENT NUMBERS OF ROBOT

Robot number	$\lambda_1$ , $\lambda_2$
	(1, 1)	(0.1, 0.9)	(0.1, 0.9)	(0.1, 0.9)	(0.1, 0.9)
3	0.4	0.4	0.4	0.4	0.1
5	0.4	0.5	0.5	0.4	0.4

 | Show Table

DownLoad: CSV

C Different Task Sets

This experiment respectively uses the market-based method, the centralized load-balanced sensor dispatch (CentralLBSD) algorithm [23], the Gini coefficient-based method and the market-Gini coefficient-based method to allocate tasks. Part 1) compares the number of tasks completed and the average resource consumed per task under the conditions of the same number of robots, the same initial resources setup and the different task sets. Part 2) validates that the task set has an influence on the $G$-value setting in the hybrid method.

1) Comparison of the Average Number of Tasks Completed and the Average Resource Consumed Per Task

We have run the tests for 30 times. Each time we used two different task sets, task set 1 includes thirty tasks and task set 2 includes fifty tasks, and we used a coalition including four robots ( $r_1$ to $r_4$ in Table Ⅳ), the robots are initially endowed with the same amount of resources. Figs. 7 and 8 intuitively show the average number of tasks completed per test and the average resource consumed per task.

Figure  7.  Average number of tasks completed under three methods. (a1) and (a2), 30 tasks (in the hybrid method, $\lambda_1=\lambda_2$ ); (b1) and (b2), 50 tasks (in the hybrid method, $\lambda_1=\lambda_2$ )

DownLoad: Full-Size Img PowerPoint

Figure  8.  Average resource consumed per task under three methods. (a1) and (a2), 30 tasks (in the hybrid method $\lambda_1=\lambda_2$ ); (b1) and (b2), 50 tasks (in the hybrid method, $\lambda_1=\lambda_2$ )

DownLoad: Full-Size Img PowerPoint

Fig. 7 shows the average number of tasks completed by three different methods respectively when we use different task sets with the same robot coalition under the condition that the robots have the same initial resources. We observe that the average number of tasks completed by Gini coefficient-based method is higher than the one obtained by the market-based method. And in the market-Gini coefficient-based method, no matter $G$ takes which set value, the average number of tasks completed is not less than the market-based method. Furthermore, as shown in Fig. 7, in some set points, the average number of tasks completed is more than Gini coefficient-based method, which reflects the advantage of the hybrid method ulteriorly. About CentralLBSD algorithm, we will make comparison with market-Gini coefficient-based method combined with average resource consumed per task as shown in Fig. 8.

The total resource consumption of the coalition divided by the number of tasks completed is the average resource consumed per task, as shown in Fig. 8. It is obvious that, when we use the market-based method, in general, the average resource consumed per task is lower than the Gini coefficient-based method; and when we use the market-Gini coefficient-based method, the average resource consumed per task under different $G$-values is not more than the Gini coefficient-based method in general.

When using the CentralLBSD algorithm to allocate tasks, Fig. 7 (a1), (b1) and Fig. 8 (a1), (b1) show that the average number of tasks completed is more than using the market-based method, and the average resource consumed per task is less than using the Gini coefficient-based method under the condition of different task sets. However, CentralLBSD algorithm's flexibility is obviously inadequate compared with market-Gini coefficient-based method. In addition, when the task completion number of CentralLBSD is close to market-Gini coefficient-based method, the average resource consumed per task is more than market-Gini coefficient-based method, such as the task completion number of CentralLBSD is 24.3 ((Fig. 7 (a1)), which is same when the setting value $G$ is 0.2 (Fig. 7 (a2)), and the average resource consumed per task of CentralLBSD is 302.6 (Fig. 8 (a1)), which is more than 301.0 when the setting value $G$ is 0.2 (Fig. 8 (a2)). The results prove the advantage of market-Gini coefficient-based method in realizing the dual optimization objectives.

In conclusion, the experiment results prove that under any task set, the Gini coefficient-based method in task allocation can effectively improve the number of tasks completed by robot coalition, and the market-Gini coefficient-based method can make a balance between the number of tasks completed and the resource consumption according to their importance degree.

2) Whether the Task Set Has an Influence on the Optimal $G$-value Setting?

The purpose of this experiment is to validate whether the task set has an influence on the $G$-value setting under the same robot coalition and the same initial resources of robots conditions.

We choose five pairs of ( $\lambda_1$ , $\lambda_2$ ) to represent the relative importance of the number of tasks completed and the average resource consumed per task, then utilize the selection algorithm for the $G$-value setting to calculate the optimal $G$-values under different task set, as shown in Table Ⅶ.

Table  Ⅶ.  THE OPTIMAL G-VALUE UNDER DIFFERENT TASK NUMBERS

Task number	$\lambda_1$ , $\lambda_2$
	(1, 1)	(0.1, 0.9)	(0.2, 0.8)	(0.3, 0.7)	(0.7, 0.3)
30	0.1	0.2-0.5	0.1	0.1	0.1
50	0.2	0.4-0.5	0.4-0.5	0.4-0.5	0.2

 | Show Table

DownLoad: CSV

From Table Ⅶ, we can conclude that the $G$-value setting in the market-Gini coefficient-based method is influenced by the task set.

Ⅵ. CONCLUSIONS

Although task allocation problem of multi-robot has been studied extensively, few literatures have been provided on the basis of energy resource constraint of robot. And in practical multi-robot systems, the number of tasks completed is crucial to system performance in some applications such as search and rescue, exploration, and site clearing. Inspired by the idea of "reducing internal resources distribution difference among robots", we investigate the task allocation problem with resource constraint in the multi-robot systems using Gini coefficient. We find that task allocation based on Gini coefficient can effectively improve the number of tasks completed by robots system. On the other hand, we also find that it is better to make a compromise between the number of tasks completed and resource consumed when resource cost has to be considered. Therefore, we focus on "minimizing resource consumed" and "maximizing the number of tasks completed" as two optimization objectives in the task allocation of multi-robot systems, and propose the market-Gini coefficient-based method. Our market-Gini coefficient-based method allows a robot coalition to select the optimal value of $G$ according to the importance of the two optimization objectives, so the method can be flexibly adapted and easily implemented in various application contexts. In the paper, we demonstrated the superiority of our proposed methods over the market-based approach using simulation experiments.