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