=Paper=
{{Paper
|id=Vol-1382/paper20
|storemode=property
|title=A Market Mechanism for QoS-aware Multi-Robot Task Allocation
|pdfUrl=https://ceur-ws.org/Vol-1382/paper20.pdf
|volume=Vol-1382
|dblpUrl=https://dblp.org/rec/conf/woa/BarileRSNR15
}}
==A Market Mechanism for QoS-aware Multi-Robot Task Allocation==
https://ceur-ws.org/Vol-1382/paper20.pdf
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
A Market Mechanism for QoS–aware
Multi–Robot Task Allocation
Francesco Barile∗ , Alessandra Rossi† , Maricarla Staffa‡ , Claudia Di Napoli§ and Silvia Rossi‡
∗ Dipartimento di Matematica e Applicazioni, Università degli Studi di Napoli “Federico II”
francesco.barile@unina.it
† Dipartimento di Fisica, Università degli Studi di Napoli “Federico II”
alessandra.rossi@unina.it
‡ Dipartimento di Ingegneria Elettrica e delle Tecnologie dell’Informazione, Università degli Studi di Napoli “Federico II”
{ mariacarla.staffa, silvia.rossi}@unina.it
§ Istituto di Calcolo e Reti ad Alte Prestazioni, CNR
claudia.dinapoli@cnr.it
Abstract—Market mechanisms, such as auctions and negoti- In this work, our assumption is that, in a more broad
ations, are often used for efficient task allocation in multi–robot context, ubiquitous robots can be represented as heterogeneous
domains where tasks are characterized by quality parameters self–interested agents that can provide different services (e.g.,
that are related to the way the task is executed depending on the to execute a specific task) depending on their own capabilities,
specific robot capabilities. In these cases, usually robots negotiate which are a priori defined. According to their capabilities,
their respective assignments in order to optimize task distribution
robots may provide services with different performance levels,
according to their own utility function. In this work, a market–
based negotiation mechanism is proposed to allocate tasks to a set which can be evaluated depending on dynamic information
of robots by taking into account end–to–end requirements that the and that can be traded, so allowing robots to dynamically
complete allocation should meet in terms of the considered quality adjust the performance they execute a task with, in order to
parameters. Negotiation takes place on these parameters that are be assigned the task. Of course, it is not possible to obtain
considered goods to be traded by the individual robots, depending an optimal allocation, but any allocation of tasks that meets
on their strategies, so that they can successfully negotiate to obtain global constraints on the complete allocation is considered an
the task allocation. acceptable solution.
I. I NTRODUCTION II. M ULTI -ROBOT TASK ALLOCATION
Networked robotic devices, such as mobile robots, drones, Mobile robot teams can fulfill a goal more efficiently than a
unmanned vehicles and position sensors, are starting to be single robot by sharing the workload and by optimizing the use
concretely employed in many real contexts, especially in of available resources. In fact, a given system–level (or global)
emergency and rescue activities, where navigation and search task can be divided into m sub–components {T1 , . . . , Tm }
operations take place both in indoor and outdoor environments which can be assigned to individual n robots {R1 , . . . , Rn }
with the human supervision. In this context, the use and the that can execute them. How a global task is decomposed is a
arrangement of multiple robots has been proven to help in crucial problem addressed by the planning methods, while the
achieving the task, both in terms of execution speed, increase distribution of subtasks to robots is known as task allocation.
of robustness, reliability, quality and performance of solutions
A task decomposition algorithm has to consider both the
in general. However the displacement of multiple robots comes
tasks nature, and restrictions in order to accommodate them
with the cost of coordination to allocate resources and tasks
among the agents for the execution. Tasks can be long-term
among them in a way that enables them to accomplish their
(e.g. monitoring an environment) or transient (e.g. looking for
mission efficiently and reliably.
objects), they can have different complexity and specificity, and
Researchers have recently applied the principles of market they can be performed by a single robot or multiple robots.
economies to multi–robot coordination [1]. Market mecha- Tasks have a well–defined set of constraints depending on the
nisms, such as auctions and negotiations, are often used for problem domain, the use of limited technologies, the scarcity
efficient task allocation in multi–robot domains [2]. More of resources, and environment conditions. The most common
specifically, they are used to determine the optimal alloca- ones are:
tion (distribution) of tasks to robots by considering it as an
optimization problem with some cost functions, such as, for • Partial ordering, i.e. a task has to be completed before
example, distance to travel, battery consumption or battery or after one or more others;
autonomy. These functions depend on the specific application, • Coupling, i.e. two or more tasks have be executed
and they are usually expressed as a minimization of the robots concurrently;
individual costs, or the total cost of the mission, although
others are possible. In any case, the optimal task allocation • Incompatibility, i.e. two or more tasks can not be
problem is known to be NP–hard. concurrently executed;
129
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
• Time windows, i.e. a task has a duration condition (i.e. utility theory). Utility represents a trade–off between accuracy
a deadline) to be met; and costs able to obtain an approximated result [10].
• Mobility interferences, i.e. robot’s ability to perform a
task is limited (e.g., it can not move in a narrow space III. Q O S M ARKET– BASED N EGOTIATION FOR TASK
due to its dimensions). A LLOCATION
The problem of allocating subtasks composing a complex
Such constraints model the functional relationships among task with specific non–functional constraints to a team of
tasks that can be expressed using a particular data structure. robots is similar to select services for delivering a compo-
There are several planning approaches to generate such con- sition of services with Quality of Service (QoS) constraints.
strained decompositions that can be expressed by task trees. In So, service–based computing technologies can be effectively
[3], Doherty et al. presented a task specification language and integrated and utilized into robotic applications [12], [13].
an abstract distributed data structure, called Task Specification
Tree (TST). Each node of a TST represents a task. A TST has In this work, we propose the use of automated negotiation
a constraint network formed by a constraint model for each as a mechanism to allocate subtasks to a set of robots, by
node and tree constraints, expressing the relations between allowing the individual robots to negotiate on the values of
the nodes. Hierarchical Task Networks (HTN) are used to the non–functional parameters characterizing the complex task.
represent various levels of task semantics, that have been These values may depend on dynamic conditions of each
extensively used for planning in AI domains, and have been robot, such as its computational and physical resources at the
imported to the robotic domain in abundant researches and time the allocation process starts, the number of tasks it was
applications. already allocated, the reward it gets, and so on. It is crucial
to adopt allocation mechanisms that can take into account of
In the literature [4], tasks may be also characterized by such a variability. In addition, robots may decide to change
different parameters that are related to the way the task is the values of these non–functional parameters to accommodate
executed, i.e. to non–functional attributes whose values are some global requirements specified for the complex task in
determined by the specific robot able to execute it. The most order to have the subtask assigned.
common parameters are:
Here, it is assumed that a complex task is represented
• Cost, i.e., a measure of the effort made by the robot as a task tree, we refer to as an Abstract Task Tree (ATT),
to execute a task, in terms of time to reach a goal, whose leaves are the subtasks composing it, we refer to
energy and resources consumed, and so on [5]; as Abstract Tasks (Ts). The complex task is required to be
executed with specific QoS end–to–end requirements, referring
• Accuracy, i.e., a characterization of goodness of the
to non-functional attributes of the complex task. The request
task execution [6] performed by a robot (e.g. the map
is managed by an agent, we refer to as the Task Allocator
accuracy produced using a laser range-finder);
Agent (TAA), responsible for finding an allocation of these
• Reward, i.e., a measure of the profit gained by the subtasks to a team of robots providing them with values of
robot for performing a task [7]; the considered attributes that, once aggregated, meet the end–
to–end requirements. Robots are modeled as task providers,
• Priority, i.e., the task urgency required for its execution i.e. “market vendors” of tasks characterized by QoS values
(higher priority tasks have to be executed before lower accounting for these non–functional attributes. They negotiate
priority ones [8]). these values with the TAA, so that a successful negotiation
determines an allocation of subtasks to the robots able to exe-
When a complex task has to be executed by a team of
cute them with suitable values of the non–functional attributes.
robots with specific values of these non–functional parameters,
Robots, referred to as Task Provider Agents (TPAs), aim to win
the allocation of subtasks to the suitable robots, is an NP–hard
the negotiation so to obtain the allocation of the task, and they
decision problem. Market–based approaches for task allocation
may change the QoS values they provide during negotiation
have received significant attention within the robotics research
according to their own negotiation strategies. In fact, while
community [1], [9], in order to efficiently produce sub–optimal
some values may depend only on the robot capabilities, others
allocations [2].
can be modified proactively by the robot. For example, it
Generally, in reply to a task request, robots may submit bids can dynamically modify the execution speed of a task or the
based on their abilities to perform the tasks and the highest accuracy of a provided sampling.
(lowest) bid wins the assignment. Moreover, when more than More specifically, each robot is modeled as composed of:
one task can be assigned to each robot (and the evaluation of
the robot non–functional parameters depends on its complete • a deliberative layer responsible for negotiating with
assignment), the robots can negotiate their respective assign- the TAA the allocation of tasks;
ments in order to optimize the task distribution. Typical alloca-
tion approaches adopt optimization algorithms based on some • a dispatching layer responsible for scheduling the
utility function. Indeed, the measure of utility is considered tasks allocated to the robot;
as a combination of these non–functional parameters, and it is • an execution layer responsible for the actual execution
used for evaluating the impact of the chosen tasks execution of the allocated tasks.
on the system performance. Utility functions can be based
on different parameters, such as sensors-based metrics [10] In the following only the deliberative layer is addressed,
or sophisticated planner–based measures [11] (multi–attribute while the other two layers are outside the scope of the work.
130
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
The negotiation mechanism adopted in this work is based the TAA is a solver of an Integer Linear Programming problem
on the one proposed in [14], a one–to–many iterative protocol, formulated as follows:
used to select services when a composition of services is
required with specific end–to–end requirements. It allows a n
X
composer agent, acting on behalf of the consumer, to nego- xi,j = 1, ∀i = 1, . . . , m (1)
tiate QoS attribute values of the functionality requested in j=1
the composition, both with different providers of the same
functionality, and with the providers of different functionalities Xn
in a coordinated way, since it is not always possible to aggri ( xi,j · qi,j,k ) ≤ Qk , ∀k = 1, . . . , r (2)
decompose these requirements in individual requirements for j=1
each functionality of the composition.
n
X
Here the same negotiation protocol is adopted, while new xi,j · qi,j,k 6= N U LL, ∀k = 1, . . . , r (3)
negotiation strategies are provided, specifically designed for j=1
the multi–robot task allocation domain.
The negotiation protocol consists of a number of negotia- Hence, there are n·m decision variables xi,j , where i identifies
tion rounds proceeding until either the negotiation is successful one of the m Ts, and j identifies one of the n TPAs that replied
(i.e., all subtasks are allocated), or a deadline (i.e., a maximum to the cfp. Such variables assume value 1 if the j − th TPA
number of allowed rounds) is reached. The deadline can be set is selected for the i − th T, 0 otherwise. Equation 3 verifies
according to the nature of the required tasks, or other criteria that agent j is able to execute the task corresponding to the
depending on the considered scenario. At each negotiation i − th T. Equation 1 verifies that exactly one TPA has to be
round, the TAA sends n call for proposals (cfps), one for selected for each T (such value can be changed in case task
each available TPA, specifying the subtasks in the ATT to be replication is required). Equation 2 evaluates that the global
allocated ({T1 , . . . , Tm }), with n ≥ m, and it waits for replies constraint for each considered non–functional parameter is
for a given time, known as the expiration time of a negotiation met. Typically, additive (e.g., price and execution time) and
round. Each T P Aj provides an offer oj containing the k multiplicative (e.g., reliability and availability) parameters are
QoS values qi,k for each of the Ti it is able to perform, and considered [15], so aggr is either a sum or a multiplication
m − k N U LL values for the Ti it is unable to perform. Such over the number of Ts.
QoS values represent measures of non–functional parameters Once that combinations of offers that satisfy the ILP are
characterizing the way the robot can execute the task Ti (such found, the TAA selects the one that maximizes its own utility,
as for example battery consumption, the speed, the accuracy, that is evaluated as follows:
and so on). Hence, the TAA receives a set of offers {o1 , ..., on },
with n the number of TPAs. Pn
r
1 X Qmax0 (k) − aggri ( j=1 xi,j · q i,j,k )
At the first negotiation iteration, the TAA checks if there UT AA = (4)
are offers for each required subtasks specified in the ATT. If r Qmax0 (k) − Qmin0 (k)
k=1
there are no offers for all the required subtasks, it declares
a failure since it is not possible to find a set of TPAs for where, Qmax0 (k) = aggrk (max(qi,j,k )) aggregates the local
all required Ti . Otherwise, it evaluates the received offers maxima of the offers received for the i − th task, Qmin0 (k) =
and the iteration number, and, according to the result of such aggrk (min(qi,j,k )) aggregates the corresponding local min-
evaluation, it performs one of the following actions: ima, and q i,j,k are the values of one offer of the found
combinations.
1) if the aggregated QoS values of the received offers
do not meet the global QoS requirements and the The adopted negotiation mechanism is one–sided, since
deadline is not reached (not final iteration), it asks the TAA cannot make counterproposals, but it only evaluates
for new offers by sending again n cfps, so starting offers in an aggregated manner, while TPAs can send new
another negotiation round; offers. The TAA could formulate counterproposals relying on
2) if the aggregated QoS value of the received offers heuristics methods to decompose the end–to–end requirements
meets the global QoS requirements (final iteration), it into individual requirements. But this approach is not followed
selects the best set of offers, in terms of its own utility, in the present work, since it increases the constraints to be
and it accepts such offers and rejects the others, so satisfied by individual offers. In fact, when an aggregated value
ending the negotiation successfully. is required, it is possible that individual offers are acceptable
3) if the deadline is reached without a success, it de- when aggregated with the others, while they are not acceptable
clares a failure to all robots that took part in the according to the chosen decomposition criteria.
negotiation (final iteration). TPAs are provided with strategies and tactics to generate
offers to send at each negotiation round to the TAA for the
A. Negotiation strategies subtasks they are able to execute. Several strategies and tactics
have been proposed in the literature for different types of nego-
In order to decide whether to accept a set of offers, the TAA tiation [16]. Here, a stochastic monotonic concession strategy
evaluates first if there is a combination of offers satisfying the is adopted for the TPAs, that models a cooperative behavior
global end–to–end requirements, intended as upper bounds for coming from the robot objective to obtain the allocation of the
the aggregated offers values. The evaluation function used by task.
131
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
IV. A P RACTICAL E XAMPLE
In our reference scenario, we assume that robots may vmaxi,j = bs /Ti . (6)
execute different type of tasks, and that they have the goal
of maximizing the number of tasks to be executed according
to the resources they have. For simplicity, we consider as a
working example a global task AT T that consists in covering
a specific total distance, and it is requested to be executed with
a global completion time T CTreq , that represents the only
constraint to be met. The task is decomposed in 3 subtasks
{T1 , T2 , T3 }, each one characterized by a pair < xi , diri >,
where xi is a distance in a specific direction diri . The tasks
have to be executed sequentially. At each negotiation, the 3
subtasks will be assigned to 3 different robots if the negotiation
is successful, i.e. if the sum of the execution times tcti
proposed by each triple of robots does not exceed the upper
bound T CTreq :
3 X
X n
( xi,j ∗ tcti,j ) ≤ T CTreq (5)
i=1 j=1
where n is the number of available robots. Hence, the negoti-
ation is single–issue and the issue is additive. Fig. 1. An example of Gaussian functions for two robots j and k.
It is assumed that each robot is able to cover a distance To model a stochastic behavior of robots taking part in
only in a specific direction, so it is able to execute only one of the negotiation, the offers generation strategy is given by a
the 3 tasks, i.e. each subtask has to be allocated to a different Gaussian function, representing the probability distribution of
robot. the offers in terms of the robot utility, as proposed in [17]. In
The TAA initiates the negotiation by issuing the n call particular, the Gaussian function depends on the specific task
for proposals, one for each robot (or TPA), containing the Ti , and it accounts for the robot utility obtained when covering
reference to the 3 subtasks to be executed. Each robot Rj will the distance of the task Ti at velocity vi,j (tcti,j = xi /vi,j ). As
reply providing an offer characterized by a triple of values, shown in Figure 1, the mean value of the Gaussian Ui,j (vmin)
with a N U LL value for the subtasks it is unable to execute, represents the best offer the Rj may propose in terms of its
and a task completion times tcti,j the robot Rj offers for the own utility with the highest probability to be selected, and it
subtask Ti it is able to execute. The offered time tcti,j depends corresponds to the maximum tcti,j it may provide the Ti with,
on the velocity vi,j the robot j decides to cover the distance i.e. the one obtained by executing the task at the minimum
of subtask Ti with. velocity possible. The rationale of this choice is that the robot
prefers to use the less battery possible when providing the task,
Each robot Rj is represented by a state s affecting the so that it can try to maximize the number of tasks it may be
offers it provides to the TAA for a specific task Ti . In assigned, so its most convenient offer is the one that minimizes
particular, it is assumed that the state s of each robot is a n– the battery discharge. The standard deviation σ represents the
tuple composed of the current battery level bs ∈ [bmin, bmax], attitude of the Rj to concede during negotiation, and it is given
depending on the current task allocation, a function f deter- by σi,j = vmaxi,j − vmin, if vmaxi,j > vmin, 0 otherwise.
mining the battery consumption according to the velocity the It takes into account the computational load of the robot in
robot offers to cover the distance of a task Ti with, the tasks terms of the number of tasks it was assigned to execute. In fact,
{Tk , . . . , Th } that it committed to execute and that are in its at each new negotiation the σ is decreased according to the
agenda, and a minimum allowed velocity vmin that is the battery consumption due to an assigned task since the vmaxi,j
minimum functioning robot velocity (i.e., it depends on the depends on the remaining battery level, so generating a new
robot and not on the task). Gaussian function to be used in the new negotiation. The value
The initial state is defined as s0 =< bs0 , f, {}, vmin >, vmaxi,j represents the reservation value for the robot, since it
and it is updated at the end of each negotiation. The maximum is the maximum velocity it can execute the task with its current
level of battery bs0 can be different for each robot, and it level of battery. Furthermore, the robot can make an offer only
determines the maximum velocity the robot can execute a task if the remaining battery level allows it to cover the distance of
with, when it is fully charged (a maximum initial value when the task Ti at the minimum velocity. The parameter σ varies
the robot is not committed to execute any task), i.e. bs0 = from robot to robot providing the same task Ti , in such a way
α · vmaxi,j · xi . Hence, if the robot executes the task at the that the lower its computational load (in terms of available
maximum velocity, it will use all its battery. battery) is, the more it is available to concede in utility, and
the lower its reservation value is.
In order to reply to a cfp, the j − th robot evaluates
its current state in terms of the current battery level bs , to The battery consumption is assumed to be linearly depen-
determine the maximum velocity it can execute a task with dent on the velocity the robot can cover the distance xi of the
(vmaxi,j ), where task Ti , according to the following equation:
132
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
T CTreq2 = 130s and T CTreq1 = 160s), and, for each
f = α · vi,j · xi (7) configuration, we perform 100 runs. The deadline of each ne-
gotiation is 100 rounds. Table I reports for each configuration
Whenever the robot Rj is selected for executing task Ti at the following information: average values, standard deviation,
the end of a negotiation, it adds it to its agenda and evaluates maximum and minimum values of the number of allocated
the remaining battery as follows: complex tasks, the number of tasks allocated to each robot, the
remaining battery at the end of the all negotiations, the time
to complete each complex task, and the number of rounds
bs0 = bs − α · vi,j · xi (8) for successful negotiations (i.e., the ones terminated with a
complete allocation).
The new state will be s0 =< bs0 , f, {Ti }, vmin >.
When a global constraint is required, the possibility to offer
In Figure 1, the functions associated to two different robots different values of the constraint parameter, allows to allocate
for the same Ti are reported. The best offer is the same for both a greater number of complex tasks with respect to a static
robots (i.e., Ui,1 (vmin) = Ui,2 (vmin)), since it is assumed allocation at a fixed velocity for each robot, in fact, at a fixed
that the robots have the same minimum velocity, while their maximum or medium velocity, only 3 complex tasks could
concession strategies are different according to their workload be allocated. As expected, when increasing the required T CT
when the negotiation takes place. In fact, σi,1 is greater than for the task execution, the number of complex tasks allocated
σi,2 meaning that R1 has a lower computational load than R2 , increases, with a consequent increase in battery consumption.
so it concedes more in utility than R2 . Moreover, let us note that the probabilistic distributions of
At each negotiation round, each robot generates, following offers lead to a global time value that is lower than the set
its Gaussian distribution, a new utility value corresponding constraint. Hence, different concession strategies may further
to a new offer. If this value is lower than the one offered improve these results on the constraints satisfaction. Finally,
in the previous round and within the negotiation set, then the number of rounds necessary to reach a complete allocation
the robot proposes the new value. The negotiation set is is smaller in the first negotiations, while it drastically increases
[Ui,j (vmin); Ui,j (vmin + σi,j ]. If the new utility value gener- in the final ones since it is more difficult to find a complete
ated is higher than that offered in the previous round, or it is allocation once the battery level of the robots decreases. This
outside the negotiation set, the robot proposes the same value is also shown by the high values of standard deviation for the
offered in the previous round. This strategy allows to simulate Rounds number reported.
different and plausible behaviors of robots that prefer not More specifically, this behavior is shown in Figures 2 and
having a consistent loss in utility, even though by increasing 3, reporting respectively, for one run of a complete set of
the number of negotiation rounds the probability for the robot negotiations with the T CTreq = 130s, the battery levels for
to move towards its reservation value increases. each robot and the number of rounds for each negotiation.
As shown in Figure 3, in the first four negotiations, robots
A. Results easily find an agreement in 1 round; while, from the forth
In our testing scenario, we evaluate the behavior of a set of to the seventh negotiation the number of rounds in order
negotiations carried out with 9 TPAs to allocate the complex to reach an agreement increases considerably leading to a
task AT T composed of 3 subtasks T1 , T2 , T3 . There are 3 lack of agreements from the seventh negotiation onward.
robots able to perform one of the three tasks. This behavior is explained in Figure 2 where the trends of
the battery level for each robot show that after the seventh
Multiple negotiations are carried out since the TAA aims negotiation the battery levels decreased for each robot. In
to allocate as many complex tasks as possible with the addition the stochastic behavior of the offers generation leads
available robots. In this preliminary analysis it is assumed to different final battery levels for different robots.
that each xi = 3m, diri = north, south, west, and each
robot can perform the task with a velocity vj in a range V. C ONCLUSION
between vminj = 0.05m/s and vmaxj = 0.3m/s. The initial
battery for each robot is bs0 = vmaxj ∗ xi , and the battery In this paper, we investigated the possibility to adopt
consumption is computed as defined in Equation 8 with α = 1. heuristic approaches to find allocations of tasks to teams
of robots when tasks are characterized by non–functional
In such scenario, if a robot performs a single task with attributes, and the complete allocation has to meet global con-
its minimum velocity (vminj = 0.05m/s), each task is straints expressed as end–to–end requirements of these non–
completed in tcti,j = 60 seconds, while the complex task functional attributes. A market–based negotiation mechanism
requires T CT req = 180 seconds. Hence, at the minimum where robots are modeled as task providers with negotiable
velocity, each robot could execute 6 subtasks before consuming non–functional parameters is proposed as an heuristic method
all its battery. Without considering the global constraint, 18 to address the NP–hard task distribution problem.
complex tasks (AT T ) could be allocated to the robots. So, we
set the maximum number of negotiations at 18. If we assume This preliminary study showed that the adopted negotiation
that robots perform the tasks at maximum velocity, each robot mechanism is a promising approach when trying to optimizing
can execute only 1 task, so 3 complex tasks could be allocated the number of complete allocations given a fixed number of
to the available robots. available robots in the team.
We simulate the set negotiations with 3 different global The approach relies on the possibility for the robots to
time constraints for the complex task (T CTreq1 = 100s, change the values of the parameters characterizing the tasks
133
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
Limit 100s 130s 160s
AVG SD MIN MAX AVG SD MIN MAX AVG SD MIN MAX
Allocated Tasks 5.02 0.43 4 6 6.27 0.55 5 7 8.06 0.51 7 9
Tasks for each robot 1.67 0.48 1 3 2.08 0.55 1 3 2.68 0.58 1 4
Remaining Battery 37% 9% 2% 64% 30% 7% 19% 50% 21% 6% 7% 39%
Time 83 15 70 93 99 27 85 109 116 38 106 126
Rounds 9 16 1 97 5 10 1 97 4 7 1 100
TABLE I. N EGOTIATION RESULTS WITH T CTreq =100 S , 130 S AND 160 S .
R EFERENCES
[1] M. Dias, R. Zlot, N. Kalra, and A. Stentz, “Market-based multirobot
coordination: A survey and analysis,” Proceedings of the IEEE, vol. 94,
no. 7, pp. 1257–1270, July 2006.
[2] R. Cui, J. Guo, and B. Gao, “Game theory-based negotiation for
multiple robots task allocation,” Robotica, vol. 31, pp. 923–934, 9 2013.
[3] P. Doherty, F. Heintz, and J. Kvarnström, “High-level mission specifi-
cation and planning for collaborative unmanned aircraft systems using
delegation,” Unmanned Systems, vol. 1, no. 1, pp. 75–119, January
2013.
[4] L. M. Alejandro R. Mosteo, “A survey of multi-robot task allocation,”
Aragon Institute of Engineering Research, Tech. Rep., 2010.
[5] M. G. Lagoudakis, E. Markakis, D. Kempe, P. Keskinocak, A. Kley-
wegt, S. Koenig, C. Tovey, A. Meyerson, and S. Jain, “Auction-based
multi-robot routing,” Robotics: Science and Systems, 2005.
[6] P. Stone and M. M. Veloso, “Task decomposition and dynamic role
assignment for real–time strategic teamwork,” in Agent Theories, Ar-
chitectures, and Languages, 1998, pp. 293–308.
[7] A. Stentz and M. B. Dias, “A free market architecture for coordinating
multiple robots,” Tech. Rep., 1999.
[8] F. Antonelli, G.; Arrichiello and S. Chiaverini, “The null–space-based
Fig. 2. Robot battery consumption trends for one set of negotiations. behavioral control for mobile robots,” in IEEE Computational Intelli-
gence in Robotics and Automation (CIRA’05), 2005, pp. 15–20.
[9] R. M. Zlot and A. T. Stentz, “Market-based multirobot coordination
for complex tasks,” International Journal of Robotics Research, Special
Issue on the 4th International Conference on Field and Service Robotics,
vol. 25, no. 1, pp. 73–101, 2006.
[10] B. P. Gerkey, M. J. Matari, and M. robot Systems, “A formal analysis
and taxonomy of task allocation in multi-robot systems,” Int. J. of
Robotics Research, 2004.
[11] S. Botelho and R. Alami, “M+: a scheme for multi-robot cooperation
through negotiated task allocation and achievement,” in IEEE Inter-
national Conference on Robotics and Automation, vol. 2, 1999, pp.
1234–1239 vol.2.
[12] S. Mokarizadeh, A. Grosso, M. Matskin, P. Kungas, and A. Haseeb,
“Applying semantic web service composition for action planning in
multi-robot systems,” in Internet and Web Applications and Services,
2009. ICIW ’09. Fourth International Conference on, May 2009, pp.
370–376.
[13] Y.-G. Ha, J.-C. Sohn, and Y.-J. Cho, “Service-oriented integration of
networked robots with ubiquitous sensors and devices using the seman-
tic web services technology,” in IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS 2005), Aug 2005, pp. 3947–3952.
[14] C. Di Napoli, P. Pisa, and S. Rossi, “Towards a dynamic negotiation
mechanism for qos-aware service markets,” in Trends in Practical
Applications of Agents and Multiagent Systems. Springer, 2013, vol.
Fig. 3. Negotiation rounds for one set of negotiations. 221, pp. 9–16.
[15] L. Zeng, B. Benatallah, A. H. Ngu, M. Dumas, J. Kalagnanam, and
H. Chang, “Qos-aware middleware for web services composition,” IEEE
they can execute dynamically, so modeling an innovative Transactions on Software Engineering, vol. 30, no. 5, pp. 311–327, may
2004.
behavior of robots that can make decisions on how to perform
[16] P. Faratin, C. Sierra, and N. R. Jennings, “Negotiation Decision Func-
a task. tions for Autonomous Agents,” Robotics and Autonomous Systems,
Further investigation is necessary to optimize the battery vol. 24, pp. 3–4, 1998.
level consumption of each involved robot that allows to still [17] S. Rossi, D. Di Nocera, and C. Di Napoli, “Normal distributions
and multi-issue negotiation for service composition,” Advances in Soft
meet the constraints so leading to an increased number of Computing, vol. 293, pp. 1–8, 2014.
complete allocations.
134