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

Danfeng Wu,Guangping Zeng,Lingguo Meng,Weijian Zhou,and Linmin Li

I.INTRODUCTION

T ASK 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 ensurethat the collaboration is effective in order to attain the highest levelof 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 II summarizes and analyzes the previous woks on MRTA problem.We define the problem of task allocation with resource constraints in Section III.The relationship between Gini coefficient and resource difference,two task allocation approaches,are presented in Section IV.In Section V,we provide experimental results to validate our proposed methods.Finally,we summarize our results and conclude with some open questions in Section VI.

II.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 II is divided into two parts.The market-based task allocation mechanisms are investigated in Section II-A,and works in the field of coalition-based approach to task allocation are briefly surveyed in Section II-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].Diaset al.introduced the TraderBots architecture in which robots are modeled as self-interested agents with the goal of maxim izing individual profits[12].Choiet 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].Huet 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].Zlotet 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].Dashet 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 realworld 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 subcoalitions 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.Wanget 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(Central LBSD),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.Lukicet 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.

III.NOTATIONS AND ASSUMPTIONS

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

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 tasktjcannot be assigned whentj−1is not finished.

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

5)Capability requirementtjkcan be executed by any robot having the capabilitykif 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

IV.GINICOEFFICIENT-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,AandB,the robot can performAwith relatively less resource than other robots,andBis a unique capability that exists only on this robot.According to the market-based approach,when the capability requirement vectors of some tasks haveA,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 requiresB.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 areaAdivided byA+B,as shown in Fig.1.When the Gini coefficient is applied to measure the resource difference degree of the robots,Ais the area surrounded by actual Lorenz curve and resource absolute no difference curve,andA+Bis the surrounded area by absolute no difference curve and absolute difference curve.Here,the Lorenz curve qualitatively reflects the resource difference degree roughly.

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 is1,and the sum ofAandBis 0.5,so,

Fig.1.The schematic diagram of Gini coefficient.

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

Because the Lorenz curve is an irregular curve,the areaBcannot 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 areaB,as shown in(4).Detailed derivation process can be seen in[25].

According to the calculation of(4),nrobots are per mutated from small to large according to the quantity of resource,andW idenotes the percentage of accumulated resources from the first robot to the robotiof 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)Combinations Formation

For a tasktj,there can form various robot combinations within the coalition according to each robot’s capability vectorand the capability requirement vector(Line 9−15).

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

Assuming,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;.So a set of combinationsthat can perform tasktjcan be expressed specifically as Table II.

TABLE II A SET OF COMBINATIONS THAT CAN PERFORM TASK tj

TABLE II A SET OF COMBINATIONS THAT CAN PERFORM TASK tj

r1 r2 r3 V t jV cj{1,2,0}cj1 {1,1,0} {0,1,0} {0,0,0}cj2 {0,1,0} {1,1,0} {0,0,0}cj3 {0,1,0} {0,1,0} {1,0,0}

2)Residual Resources Calculation

Residual resource calculation finds the residual resources of each robot after each combination executing the tasktj(Line 21).Assume that each robot’s initial resources number is 2000,all for 2000,and the weight of the task is 1,so the total resource consumptionrciand the residual resourcesreiof each robot are shown in Table III.

3)Gini Coefficient Calculation

After each combination performingtjsimulantly,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 minimumG-value to execute tasktj(Line 24−28).

TABLE III THE RESIDUAL RESOURCES OF EACH ROBOT AFTER EACH COMBINATION EXECUTES THE TASK tj

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

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

The setting ofG-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 V-A-2,V-B-2 and V-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 ofG,and 0≤G≤0.5.In fact,when the setGequals 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 ofG.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,Gcan 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 ofGas a set point to the actual task allocation.The selection algorithm for the optimal set value ofGis shown as Algorithm 3.

Algorithm 3.The selection algorithm for the optimal set value of G

1)SetGequals 0,0.1,0.2,...,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 theG-value of coalition is greater than or equal to the set value in execution process(Line 5−14).

2)Record the number of tasks completedf1(x)and the total resource consumption(Line 15−16),total resource consumption divided by the task completion number is the average resource consumption per taskf2(x).Now,we can acquire the maximum task completion numberand the minimum average resource consumed per task(Line 18).

3)Structuring the multi-objective evaluation functionU(x)((5)or(6)),calculatingU(x)under each set value ofG,(Line 19−22),and taking theG-value corresponding to the minimumU(x)as the set value ofGin 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):

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

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

V.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 robots 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 IV.

TABLE IV ROBOT PARAMETERS USED IN EXPERIMENTS

A.Same and Different Initial Resources of Robots

We use the same robot coalition including four robots(r1tor4in Table IV)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 V-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(Central LBSD)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 V-A-2 validates that the initial resources of robots have the influence on the optimalG-value setting in the hybrid method.

As we mentioned in Section II,the Central LBSD 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 Central LBSD 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 for30 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.

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 matterGtakes which set value,the number of tasks completed is not less than using the market-based method.About Central LBSD algorithm,we will make comparison with market-Gini coefficient based method combined with average resource consumed per task after show ing Fig.4.

Fig.2.Average number of tasks completed under three methods.(a1)and(a2),the same initial resources of robots(in the hybrid method,λ1= λ2);(b1)and(b2),different initial resources of robots(in the hybrid method,λ1= λ2).

Fig.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.

Fig.4. Average resource consumed per task under three methods.(a1)and(a2),the same initial resources of robots(in the hybrid method,λ1= λ2);(b1)and(b2),different initial resources of robots(in the hybrid method,λ1= λ2).

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 setG-values is not more than using Coefficient-based method in general.

When using the Central LBSD 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,Central LBSD algorithm’s flexibility is obviously inadequate compared with market-Gini coefficient-based method.Market-Gini coefficient-based method can set the different optimal values ofGaccording to the different application environments.In addition,when the number of completed tasks of Central LBSD 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 Central LBSD is 25.2((Fig.2(a1)),which is close to 25.7 and 24.2 when the setting value ofGis 0.2 and 0.3 respectively(Fig.2(a2)),and the average resource consumed per task of Central LBSD is 295.5(Fig.4(a1)),which is more than the 293.2 and 288.8 when the setting valueGis 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 onG-value setting under the same task set and the same robot coalition conditions.

Fig.5.Average number of tasks completed under three methods.(a1)and(a2),three robots(in the hybrid method,λ1= λ2);(b1)and(b2),five robots(in the hybrid method,λ1= λ2).

We choose five pairs of(λ1,λ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 theG-value setting to calculate the optimalG-values under the same and different initial resources setups,as shown in Table V.

TABLE V THE OPTIMAL G-VALUE UNDER THE SAME AND DIFFERENT INITIAL RESOURCES SETUPS

From Table V,we can conclude that theG-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(Central LBSD)algorithm[23],Gini coefficient-based method and market-Gini coefficient-based method.Part2)validates the influence of the number of robots on the optimalG-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 random ly as the test case,and we respectively allocate tasks to two robot coalitions.The first coalition contains three robots(r1tor3in Table IV),and the second contains five robots(r1tor5in Table IV),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.

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 marketbased method.In the market-Gini coefficient-based method,no matterGadopts which set point,it can complete more tasks than the market-based method.Furthermore,with some setpoints,the average number of tasks completed is more than Gini coefficient-based method,which reflects the advantage of hybrid method clearly.About Central LBSD algorithm,we will make comparison with market-Gini coefficient-based method combined with average resource consumed per task after show ing Fig.6.

Fig.6.Average resource consumed per task under three methods.(a1)and(a2),three robots(in the hybrid method,λ1= λ2);(b1)and(b2),five robots(in the hybrid method,λ1= λ2).

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 differentG-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 marketbased method,which reflects the advantage of hybrid method clearly.

When using the Central LBSD 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 markedbased 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,Central LBSD algorithm’s flexibility is obviously inadequate compared with market-Gini coefficient-based method.In addition,when the task completion number of Central LBSD 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 Central LBSD is 22.7((Fig.5(a1)),which is close to 23.0 and 22.5 when the value ofGis 0.3 and 0.4 respectively(Fig.5(a2)),and the average resource consumed per task of Central LBSD is 228.1(Fig.6(a1)),which is more than the 224.0 and 222.0 when the setting valueGis 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 onG-value setting with the same task set and the same initial resources of robots.

We choose five pairs of(λ1,λ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 theG-value setting to calculate the optimalG-values under different numbers of robot,as shown in Table VI.From Table VI,we can conclude that theG-value setting in market-Gini coefficient-based method is influenced by the size of the robot coalition.

C.Different Task Sets

Fig.7.Average number of tasks completed under three methods.(a1)and(a2),30 tasks(in the hybrid method,λ1= λ2);(b1)and(b2),50 tasks(in the hybrid method,λ1= λ2).

TABLE VI THE OPTIMAL G-VALUE UNDER DIFFERENT NUMBERS OF ROBOT

This experiment respectively uses the market-based method,the centralized load-balanced sensor dispatch(Central LBSD)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 theG-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 set1 includes thirty tasks and task set 2 includes fifty tasks,and we used a coalition including four robots(r1tor4in Table IV),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.

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 matterGtakes 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 Central LBSD 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 differentG-values is not more than the Gini coefficient-based method in general.

Fig.8. Average resource consumed per task under three methods.(a1)and(a2),30 tasks(in the hybrid methodλ1= λ2);(b1)and(b2),50 tasks(in the hybrid method,λ1= λ2).

When using the Central LBSD 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 marketbased 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 Central LBSD 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 Central LBSD is 24.3((Fig.7(a1)),which is same when the setting valueGis 0.2(Fig.7(a2)),and the average resource consumed per task of Central LBSD is 302.6(Fig.8(a1)),which is more than 301.0 when the setting valueGis 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 theG-value setting under the same robot coalition and the same initial resources of robots conditions.

We choose five pairs of(λ1,λ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 theG-value setting to calculate the optimalG-values under different task set,as shown in Table VII.

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

TABLE VII THE OPTIMAL G-VALUE UNDER DIFFERENT TASK NUMBERS

V I.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 multirobot systems,and propose the market-Gini coefficient-based method.Our market-Gini coefficient-based method allows a robot coalition to select the optimal value ofGaccording 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.

[1]J.W.Kwon,“Cooperative environment scans based on a multi-robot system,”Sensors,vol.15,no.3,pp.6483−6496,Mar.2015.

[2]M.H.Kim,S.P.Kim,and S.Lee,“Social-welfare based task allocation for multi-robot systems with resource constraints,”Comp.Indust.Eng.,vol.63,no.4,pp.994−1002,Dec.2012.

[3]B.P.Gerkey and M.J.Matarić,“A formal analysis and taxonomy of task allocation in multi-robot systems,”Int.J.Robot.Res.,vol.23,no.9,pp.939−954,Sep.2004.

[4]W.Y.Wang and Y.C.Jiang,“Multiagent-based allocation of complex tasks in social networks,”IEEE Trans.Emerg.Top.Comput.,vol.3,no.4,pp.571−584,Dec.2015.

[5]A.Majumder,S.Datta,and K.V.M.Naidu,“Capacitated team formation problem on social networks,”Proc.18th ACM SIGKDD International Conf.Know ledge Discovery and Data M ining,New York,2012,pp.1005−1013.

[6]X.Y.Wang,Z.Zhao,and W.Ng,“A comparative study of team formation in social networks,”Lecture Notes in Computer Science,Hanoi,Vietnam,2015,pp.389−404.

[7]T.Gunn and J.Anderson,“Effective task allocation for evolving multi-Robot teams in dangerous environments,”Proc.2013 IEEE/WIC/ACM International Joint Conf.Web Intelligence(WI)and Intelligent Agent Technologies(IAT),Atlanta,GA,2013,pp.231−238.

[8]T.Gunn and J.Anderson,“Dynamic heterogeneous team formation for robotic urban search and rescue,”J.Comput.Syst.Sci.,vol.81,no.3,pp.553−567,May 2015.

[9]P.Lanillos,E.Besada-Portas,J.A.Lopez-Orozco,and J.M.de la Cruz,“Minimum time search in uncertain dynamic domains with complex sensorial platforms,”Sensors,vol.14,no.8,pp.14131−14179,Aug.2014.

[10]L.Vig and J.A.Adams,“Market-based multi-robot coalition formation,”inDistributed Autonomous Robotic Systems,M.Gini and R.Voyles,Eds.Japan:Springer,2006,pp.227−236.

[11]B.P.Gerkey and M.J.Matari,“Sold!:Auction methods for multirobot coordination,”IEEE Trans.Rob.Autom.,vol.18,no.5,pp.758−768,Oct.2002.

[12]M.B.Dias and A.Stentz,“A comparative study between centralized,market-based,and behavioral multirobot coordination approaches,”Proc.2003 IEEE/RSJ International Conf.Intelligent Robots and Systems,Las Vegas,NV,United States,2003,pp.2279−2284.

[13]H.L.Choi,L.Brunet,and J.P.How,“Consensus-based decentralized auctions for robust task allocation,”IEEE Trans.Robot.,vol.25,no.4,pp.912−926,Aug.2009.

[14]A.Viguria and A.M.Howard,“An integrated approach for achieving multirobot task formations,”IEEE/ASME Trans.Mech.,vol.14,no.2,pp.176−186,Apr.2009.

[15]Y.Hu,L.Wang,J.Liang,and T.Wang,“Cooperative box-pushing withmultiple autonomous robotic fish in underwater environment,”IET Control Theory Appl.,vol.5,no.17,pp.2015−2022,Nov.2011.

[16]R.Zlot and A.Stentz,“Market-based multirobot coordination for complex tasks,”Int.J.Rob.Res.,vol.25,no.1,pp.73−101,Jan.2006.

[17]R.K.Dash,P.Vytelingum,A.Rogers,E.David,and N.R.Jennings,“Market-based task allocation mechanisms for limited-capacity suppliers,”IEEE Trans.Syst.Man Cybern.A,vol.37,no.3,pp.391−405,May 2007.

[18]A.Canedo-Rodriguez,R.Iglesias,C.V.Regueiro,V.Alvarez-Santos,and X.M.Pardo,“Self-organized multi-camera network for a fast and easy deployment of ubiquitous robots in unknown environments,”Sensors,vol.13,no.1,pp.426−454,Dec.2012.

[19]Z.Butlerand J.Hays,“Task allocation for reconfigurable teams,”Robot.Autonom.Syst.,vol.68,pp.59−71,Jun.2015.

[20]L.Vig and J.A.Adams,“Multi-robot coalition formation,”IEEE Trans.Robot.,vol.22,no.4,pp.637−649,Aug.2006.

[21]J.Chen and D.Sun,“Resource constrained multirobot task allocation based on leader-follower coalition methodology,”Int.J.Rob.Res.,vol.30,no.12,pp.1423−1434,Oct.2011.

[22]T.Xie and X.Qin,“An energy-delay tunable task allocation strategy for collaborative applications in networked embedded systems,”IEEE Trans.Comput.,vol.57,no.3,pp.329−343,Mar.2008.

[23]Y.C.Wang,W.C.Peng,and Y.C.Tseng,“Energy-balanced dispatch of mobile sensors in a hybrid wireless sensor network,”IEEE Trans.Parallel Distrib.Syst.,vol.21,no.12,pp.1836−1850,Dec.2010.

[24]M.Lukic,A.Barnaw i,and I.Stojmenovic,“Robot coordination for energy-balanced matching and sequence dispatch of robots to events,”IEEE Trans.Comput.,vol.64,no.5,pp.1416−1428,May2015.

[25]J.H.Zhang, “An convenient method to calculate Gini coefficient,”J.Shanxi Agric.Univ.(Soc.Sci.Ed.),vol.6,no.3,pp.275−278,283,Mar.2007.