This paper is concerned with the problem of dynamic taskassignment among multiple mobile agents. We study and experimentally compare two approaches for achieving an agreement on how the tasks are to be assigned: negotiation through auctions and aggregation of preferences through voting. For the second approach, we formalize the task assignment problem as a voting problem and present the corresponding algorithm for mobile agents. Our experimentation is performed in a 2Denvironment applying both agreement methods and comparing them in terms of their social welfare values.
Multiple mobile-agent task and resource assignment is an important part of
decision-making processes in many areas, some of which are: industrial
procurement [
The alignment of individual and global utilities is a big issue in heterogeneous agents. Even when the agents are cooperative, the utilities of the individual may not necessarily be aligned with the utilities of the group. Since the assignment cost and utility function of a self-interested agent may or may not coincide with the global system's cost and utility, di erent notions of optimality may arise. Optimality can be seen from the global and individual point of view. Looking from the global standpoint, globally optimal solution searches for the minimum cost and maximum utility of the group as a whole and it does not consider the individual dynamics of assignment. However, in the globally optimal solution, individual assignments might be far from the optimal so that there might exist some agents who are unsatis ed with their individual assignment. The question is can we start from constructing a global solution from individual interactions looking only to minimize the damage of the worst-o agents and how it behaves in respect to the global solution.
Two allocations can be compared, in terms of individual utilities3 of
participating agents, by comparing their collective utility values. Assuming that any
given allocation yields some utility for each agent, a group utility function
assigns a single utility, i.e., social welfare, to the agent group. Group utility values,
are natively studied in the theory of public choice and welfare economics [13,
Chapter 23]. The use of public choice methods and theories has recently also
gained the interest of computer scientists [
Examples of group utility functions include utilitarian and egalitarian collective utility. The utilitarian group utility function is de ned as the sum of all the individual utilities. A high utilitarian social welfare is indicative of a "globally" good allocation, but it does not re ect on how good, or fair, an allocation is \locally". For example, if one agent's utility were increased while decreasing the utility of another agent for the same amount, the utilitarian social welfare would not be changed. In contrast, the egalitarian social welfare re ects the fairness aspect of an allocation. The egalitarian collective utility function is the lowest individual utility in the allocation. Thus a high egalitarian social welfare is indicative of a \locally" fair allocation. Another common social welfare is the elitist collective utility which coincides with the maximal individual utility in the allocation. A high elitist social welfare is indicative of a society that maximizes the \pro t" of an individual disrespecting fairness and group optimality.
In this paper we are interested in a decentralized multi-agent system in which
mobile agents move in an environment to reach their assigned tasks and
communicate within a connected communication graph while doing so. We explore
two cases of self-interested agents: collaborative and competitive one. For each of
these cases, we apply a di erent method for assigning tasks and compare the
resulting solutions in terms of their collective utility values. For cooperative agents
we use a Bertsekas [
This paper is organized as follows. In Section 2 we formulate the task assignment problem. Section 3 describes brie y the auction method used by the collaborative agents. The voting method for the competitive agents is described in Section 4. Section 5 contains simulation results comparing these negotiation approaches. We discuss our results, draw conclusions and outline the directions for future work in Section 6. 2
We consider a set A = f1; : : : ; ng of n collaborative mobile (vehicle) agents. The agents are represented as points in a plane positioned in an environment E R2. The position of an agent a 2 A at time t = 1; : : : ; T is given by pa(t) 2 E. We also consider a set = f1; : : : ; ng of n targets (tasks), with q 2 E being the static position of task 2 .
Each agent, a 2 A, is described by a tuple a = fpa(t); ; vm[a]ax; dista(t); g ; (1) where 2 R>0 is a xed transmitting (communication) range of agent a's wireless transceiver for limited range communication, vm[a]ax is its maximum velocity (maximum movement distance in each time period t), and dista(t) is the total distance passed until period t. At any time t, each agent a knows its pa(t) and the position q of each target 2 . Let ca (t) be the (Euclidean) distance between the position of agent a and target . We consider the problem of dynamic assignment of the set A of vehicle agents to the set of target locations, under the requirement that each agent is assigned to at most one target. The total traveled distance by all agents moving towards their targets, calculated as (2) (3) X ca (t) ; t = 1; : : : ; T ;
i should be minimized. T is the upper time bound in which all the agents reach their distinct assigned target locations.
In each period t, each agent a is able to communicate to a set of agents Ca(t) A (belonging to the same connected component) reachable in a multihop fashion within the communication graph; at any time t, agents i and j communicate if kpi(t) pj (t)k2 : In this way, agents which are not within the communication range of each other can, however, exchange information over other interconnected agents. We assume that no global assignment information is available a priori and that the agents only receive information through their local interaction with the environment and with the connected agents in the communication graph.
The auction algorithm of Bertsekas [
A modi cation of the Bertsekas algorithm for dynamic environments and
moving agents with incomplete local information is presented in [
Voting is a general group option-choosing method for societies of self-interested
agents [
Formally, a voting problem is speci ed by a non-empty set of social options O and a set A = fa1; : : : ; ang of at least two agents. Each agent ai 2 A reports his/her preferences over elements in O, which are represented by a complete, transitive preference relation4 %iO. A pro le P = f%iOj i 2 Ag is the set of the preference orders of the agents A.
Let R(O) denote the class of all preference orderings over O. The set of all preference pro les is then given by R(O)n. An n person voting rule is function F : R(O)n ! 2O n f;g, that assigns to each tuple of n preference orders from R(O) a non-empty sub-set of options from O.
Which voting rule is used for a particular problem depends on the nature of the problem. The goal of plurality (majority) rule is to ensure that the elected option has the support of a majority. Ranked pairs [17], on the other hand, aim at electing the candidate who would win each head-to-head option comparison (Condorcet winner), while the Borda count rule chooses a consensus option, looking at how strongly the agent dislike certain options as well. The Borda rule 4 A preference relation is transitive if and only if o1 %i o2 and o2 %i o3 implies o1 %i o3. The preference relation is complete if for every o1; o2 2 O either o1 i o2, o2 i o1 or o1 i o2. is one of the voting rules based on the principle of dissatisfaction minimization, namely the winner is chosen to be such that the dissatisfaction of the individual voters with the election solution is minimal.
One desirable feature of the Borda count rule is the low computational
complexity of the determining the winner. According to the Borda rule, each option
is assigned a score and the option with the highest score is elected a winner.
The computational complexity of determining the Borda score, and with that
the election winner, is very low compared to some other rules based on scores
such as, e.g., Dodgson and Kemeny [
According to Borda count rule, each element o 2 O is given a score based on its position in the individual preference orders in P . The scores for the elements o 2 O are de ned as s(o) = X #f(o0)jo0 2 O and o %iO o0g:
i2N The number #f(o0)jo0 2 O and o %iO o0g is e ectively the position of the option a in the agent i's preference order. For example, in the order o1 i o2 i o3, the top ranked option o1 is assigned a value 3 because it at least as good as 3 other options including itself. The Borda count rule returns the option with the highest score as a winner of the election.
It is directly observable that the Borda score for each option can be calculated in linear time of the size of the pro le of preferences and consequently the respective linear order over the options can be generated in time O(m2 n), where m is the number of options and n is the number of agents. Other low complexity methods like the plurality rule are not adequate for the voting problem in task assignment. Namely, in elections for task assignment, the number of options (tasks) equals the number of voters (agents). The plurality rule returns as winner the option that is most preferred by the largest number of agents. However, when the number of options is greater or equal to the number of agents, it can frequently happen that no option is supported by more than a few agents and in this case no winner can be found.
The task-assignment problem can be formulated as a voting problem in the following manner. Let A = fa1; : : : ; ang be a set of n agents and = f 1; : : : ng a set of n target locations. Each agent i 2 A submits his (cardinal) preference order %iO over a set of social options O = f(i; ) j 2 g. The preference order %iO is a complete strict order over O corresponding to the values ui(j; )jj 2 A, where the utility ui(j; ) expresses the utility that agent i has if task is assigned to agent j 2 A. The utility ui(j; ) in a task-assignment is connected with the minimization of the assignment cost ci . The individual preferences ui(i; ) are ordered in ascending way such that ui(i; ) = min ci is ordered rst; i.e., each agent prefers to be assigned to a task closer to him. For i 6= j there are di erent ways in which ui(j; ) can be ordered, the simplest being ui(j; ) = max(ci ) for all j expressing that an agent prefers his most distant targets to be assigned to other agents.
We present the detailed description of our task-assignment algorithm based on the Borda count voting rule. Let us assume that the set of unassigned agents is au 2 U , and a set of unassigned targets u 2 T . Then each unassigned agent au 2 U does the following steps: it keeps in its memory a set of unassigned agents au 2 U and a set of unassigned targets u 2 T . after constructing n preference orders as described above, it keeps its preference order ui(i; ) and sends ui(j; )jj 6= i to other agents aj 2 U; j 6= u. it receives preference orders from other communicating unassigned agents j 2 U; j 6= i and constructs a preference pro le also considering his own preferences. For aggregation, the Borda count voting rule is applied. In the cases when the Borda voting rule produces a tie, i.e., the voting points are the same for multiple remaining targets, the agent i selects the winning option to be the one with the lowest utility value ui(i; ) and informs the other communicating agents of the same.
Once a target 2 T is assigned to agent j 2 U , both are removed from unassigned agents U and targets respectively. An election is now held for the next agent in U . The agents who have already gotten a task do not vote. Example 1. Consider a set of ve agents A = fa; b; c; d; eg and a set of ve targets = f 1; 2; 3; 4; 5g distributed (at moment t) like in Figure 1.
The Euclidean distances at t5 are as follows: ca1 = 3:6 ca2 = 8:06 ca3 = 13:34 ca4 = 16:97 ca5 = 23:26 cb1 = 3:6 cb2 = 5 cb3 = 13:04 cb4 = 14:03 cb5 = 21:84 cc1 = 11:31 cc2 = 7:61 cc3 = 7:28 cc4 = 2:23 cc5 = 10 cd1 = 12:37 cd2 = 13:6 cd3 = 4:47 cd4 = 13:34 cd5 = 12:53 ce1 = 23:26 ce2 = 20:61 ce3 = 14:26 ce4 = 12 ce5 = 3:6 Let us consider the following election sequence N = (a; b; c; d; e).
Election 1 A = fa; b; c; d; eg, O = f(a; 1); (a; 2); (a; 3); (a; 4); (a; 5)g. The pro le of preferences regarding which target should be assigned to agent a is Pro le 1 on Figure 2. The Borda scores are: s(a; 1) = 18, s(a; 2) = 18, s(a; 3) = 12, s(a; 4) = 13 and s(a; 5) = 14. The winners are (a; 1) and (a; 2). Agent a is assigned to target a because ca1 < ca2.
Agent P ref erences a (a; 1) (a; 2) b (a; 5) (a; 4) c (a; 1) (a; 5) d (a; 2) (a; 4) e (a; 1) (a; 2) (a; 3) (a; 3) (a; 2) (a; 5) (a; 3) (a; 4) (a; 2) (a; 3) (a; 1) (a; 4) (a; 5) (a; 1) (a; 4) (a; 3) (a; 5)
Pro le 1 Agent P ref erences b (b; 2) (b; 3) c (b; 5) (b; 2) d (b; 2) (b; 4) e (b; 2) (b; 3) (b; 4) (b; 3) (b; 5) (b; 4) (b; 5) (b; 4) (b; 3) (b; 5)
Pro le 2
Election 2 A = fb; c; d; eg, O = f(b; 2); (b; 3); (b; 4); (b; 5)g. The pro le of preferences regarding which target should be assigned to agent b is Pro le 2 on Figure 2. The Borda scores are: s(b; 2) = 16, s(b; 3) = 9, s(b; 4) = 8 and s(b; 5) = 8. The winner is ( 2).
Election 3 A = fc; d; eg, O = f(c; 3); (c; 4); (c; 5 g ) . The pro le of preferences regarding which target should be assigned to agent c is Pro le 3 on Figure 3. The Borda scores are: s(c; 3) = 6, s(c; 4) = 8 and s(c; 5) = 4. The winner is (c; 3).
Election 4 A = fd; eg, O = f(d; 3); (d; 5 g ) . The pro le of preferences regarding which target should be assigned to agent d is Pro le 4 on Figure 3. 5 we do not write the parameter t below to ease the readability
Agent P ref erences c (c; 4) (c; 3) d (c; 4) (c; 5) e (c; 3) (c; 4) (c; 5) (c; 3) (c; 5) Pro le 3
Agent P ref erences d (d; 3) (d; 5) e (d; 3) (d; 5)
Pro le 4
As it can be observed directly in the example, the order in which the elections are held determines which target is assigned to which agent. If instead of the sequence N = (a; b; c; d; e) we used the sequence N = (b; a; c; d; e) the allocation reached would be 0 = f(b; 1); (a; 2); (c; 4); (d; 3); (e; 5)g which is a worse allocation than because u( 0) = 21:96 and e( 0) = 8:06.
Example 2. Consider a set of ve agents A = fa; b; c; d; eg and a set of ve targets = f 1; 2; 3; 4; 5g distributed (at moment t) like in Figure 2. Let us consider the following election sequence N = (a; b; c; d; e). We reach the following assignment = f(a; 1); (b; 4); (c; 3); (d; 5); (e; 2)g. The utilitarian welfare is u( ) = 58:91, the egalitarian welfare is e( ) = 21:38, while the elitist welfare is el( ) = 7:07. 5
We simulate a multi-agent system with mobile agents applying the Bertsekas modi ed iterative auction algorithm and the voting-based algorithm in MatLab. The dynamic modi ed auction algorithm as well as the presented voting algorithm were experimented with complete assignment information exchange, i.e., the communication graph among the agents is connected and every two agents in the group can communicate, if not directly, then at least in a multihop fashion through other connected agents.
Without loss of generality and for simplicity, we model the agents as points in a plane, which move on a straight line towards their assigned targets. The experiments were performed for up to 10 agents in environment [0; 50]2 R2 where the initial agent and target positions were generated uniformly randomly.
We considered 30 di erent instances for the problem with 10 agents and 10 targets. We measured the total distance traveled PT t=1 distai(t) by agents ai 2 A and calculated utilitarian, egalitarian, and elitist social welfare as a negative value of the passed distances of individual agents and the agent group as a whole. We chose this approach since every agent is better o if its assigned target is closer to it. Moreover, the cost of assignment is proportional to the traveled distance. Therefore, the elitist welfare is measured as the utility of the agent that is currently best o as negative distance cost mini PtT=1 distai(t). The utilitarian social welfare is the sum of individual utilities Pin=1 PtT=1 distai(t), while the egalitarian social welfare is given by the utility of the agent that is currently worst o maxi PtT=1 distai(t).
From Figures 5 and 6, it can be seen that the egalitarian and the utilitarian welfare in the case of the iterative auction algorithm are better o in all the experimented instances in respect to the voting algorithm while the elitist welfare (Figure 7) is better in 25, equal in 4 and worse in 1 out of 30 instances. Performance of the iterative auction in respect to the voting method is evaluated measuring the gap (in percentage) g = [(SWV M SWIA)=SWIA] 100, between (elitist, egalitarian and utilitarian) social welfare obtained by voting mechanism SWV M and iterative auction SWIA respectively. The gap provides an estimation of the relative extra-cost incurred in the competitive scenario (voting mechanism) in respect to the collaborative one (iterative auction) for not having at disposal all the system information to optimally assign the available targets.
From Figure 8 and Table 1, it can be seen that the gap between those two scenarios for the egalitarian and utilitarian welfare is signi cantly lower and more uniformly distributed than the elitist welfare gap which in average is almost 3 times higher than the other two.
(Auction-Voting)/Auction[%]
Utilitarian welfare Elitist welfare Egalitarian welfare
121,8 281,2 99,5
The reason for the lower performance of the voting mechanism lies in the fact that although the communication graph among agents is connected, the voting mechanism obscures the information necessary for a good global solution. This can be explained by the strong in uence of greedy policy in ordering preferences sent from one agent to others to direct them to less preferred targets, thus minimizing individual cost and, on average, worsening the global and other individual solutions. The individual assignment process of the voting mechanism doesn't take into consideration individual agent bias and is performed taking into consideration all the information at disposal with the same weight. Furthermore, since a random factor is introduced through lexicographic ordering of equivalently valued targets, the distribution of the quality of the solution on the best-case and worst-case agent cannot be achieved. 6
In this work we compared two approaches for solving the multiagent task allocation problem: negotiation through auctions and preference aggregation via a voting rule. The voting-based method is applicable both to competitive and to collaborative environments, though it is structured such that the assignment information exchanged is minimal and the communicated preferences are only ordinal. The auction-based method is a broadly used method for task assignment of collaborative agents that results in an optimal allocation solution. Our results show that cooperative agents that use the auction method to agree on how the tasks should be assigned on average reach solutions that are cost optimal for the system as a whole and su ciently good for the agents individually. Moreover, the worst-o and best-o agent in the system have a signi cantly better local assignment solution in this case than when the voting approach is used. When we evaluated the deviation of the voting mechanism in respect to Bertsekas auction algorithm, the elitist welfare resulted in the lower, while the egalitarian welfare in the higher di erence in respect to the (optimal) auction solution.
We formulated the problem as a dynamic task assignment problem to allow for the case when not all agents are connected in the communication graph and voting is done only among communicating agents. The voting algorithm presented in this paper assumes a connected communication graph which allows for a dynamic update of assignment information within all of the agents present in the system. We intend to consider the disconnected communication graph case in our future work.
In our experiments with the voting method, we modelled the suggested utility values of each agent for the assignment of other agents assuming a negative in uence of similar assignments one to another. However, we can foresee scenarios in which the relations between the agents in the grid are more complex, e.g., when the agents cooperate with some group of other agents but compete with others. It would be interesting to compare the results from auction-based methods and those from voting in such scenarios, as well.
A great disadvantage of our voting approach stems from its sequentially, namely the tasks are allocated to the agents following a sequence of one agent at a time. The solution directly depends on the sequence in which the agents are considered. In our experiments we use a lexicographic sequence, however there might exist a heuristic that helps us generate the sequences in such a manner that the desired social welfare of the assignment solution is increased. We intend to explore such heuristics in our future work. 7
The work of Marin Lujak was supported in part by the Spanish Ministry of Science and Innovation through the projects "AT" (Grant CONSOLIDER CSD20070022, INGENIO 2010) and "OVAMAH" (Grant TIN2009-13839-C03-02) cofunded by Plan E. The work of Marija Slavkovik was partially supported both by the Virtual Engineering Centre (funded by the NWDA and the ERDF) and EPSRC (funding via research project EP/F033567). [13] D. C. Mueller. Public choice III. Cambridge University Press, Cambridge [England] New York, 2003. [14] H. Nurmi. Voting theory. In D. Rios Insua and S. French, editors, eDemocracy, volume 5 of Advances in Group Decision and Negotiation, pages 101{123. Springer Netherlands, 2010. [15] B.Silvia Suarez, Christian Quintero M., and Josep de la Rosa. A real time approach for task allocation in a disaster scenario. In Yves Demazeau, Frank Dignum, Juan Corchado, and Javier Perez, editors, Advances in Practical Applications of Agents and Multiagent Systems, volume 70 of Advances in Intelligent and Soft Computing, pages 157{162. Springer Berlin / Heidelberg, 2010. [16] P. J. 't Hoen and J. A. La Poutre. A decommitment strategy in a competitive multi-agent transportation setting. In Proceedings of the second international joint conference on Autonomous agents and multiagent systems, AAMAS '03, pages 1010{1011, New York, NY, USA, 2003. ACM. [17] T. N. Tideman. Independence of clones as a criterion for voting rules. Social
Choice and Welfare, 4:185{206, 1987. [18] H. Van Dyke Parunak. Applications of distributed arti cial intelligence in industry. In G. M. P. O'Hare and N. R. Jennings, editors, Foundations of distributed arti cial intelligence, chapter Applications of distributed arti cial intelligence in industry, pages 139{164. John Wiley & Sons, Inc., New York, NY, USA, 1996.