=Paper= {{Paper |id=Vol-2806/short10 |storemode=property |title=On Efficiency in Dynamic Multi-Robot Task Allocation |pdfUrl=https://ceur-ws.org/Vol-2806/short10.pdf |volume=Vol-2806 |authors=Marin Lujak,Mislav Matezović |dblpUrl=https://dblp.org/rec/conf/aiia/LujakM20 }} ==On Efficiency in Dynamic Multi-Robot Task Allocation== https://ceur-ws.org/Vol-2806/short10.pdf 
On Efficiency in Dynamic Multi-Robot Task Allocation

Marin Lujaka , Mislav Matezovićb

a
    CERI Numerique, IMT Lille Douai, University of Lille, Lille, France

b
    Faculty of Mechanical Engineering and Naval Architecture, University of Zagreb, Zagreb, Croatia



                                          Abstract

                                          A mobile robot is able to perform simple tasks like food and medicine delivery. Multi-robot teams can be used for
                                          the delivery of goods to patients in hospitals as well as to elderly and disabled people in nursing homes. For an
                                          efficient and effective team performance in such dynamically changing environments, we need an efficient online
                                          coordination approach that will dynamically allocate tasks to robot teams while adapting to the changing envi-
                                          ronment. In this paper, we study the related dynamic multi-robot task allocation (MRTA) problem. We compare
                                          the performance of the lexicographic, First-Come-First-Served (FCFS), and the Bertsekas auction algorithm in the
                                          dynamic one-on-one multi-robot task allocation considering perfect communication network. Contrary to the first
                                          two solution approaches, the Bertsekas auction algorithm is a distributed algorithm with quality of solution guar-
                                          antees. We explore the degradation of the quality of solution with diminishing communication range and compare
                                          the multi-robot team’s performance when using the auction algorithm with the other two approaches.




                                          Keywords

                                          Multi-robot task allocation, MRTA, dynamic optimization, real-time coordination, imperfect communication




1. Introduction

   The objective of the Multi-Robot Task Allocation (MRTA) problem is to find the assignment of a set
of robots to a set of tasks based on the optimization of some objective function (e.g. [1, 2]). In case of the
one-on-one homogeneous task and robot allocation, this problem corresponds to the Linear Assignment
Problem (LAP), e.g., [3]. In the latter problem, given is a set of 𝑛 agents and a set of 𝑛 tasks to whom
the agents need to be assigned in one-on-one manner minimizing the overall cost of assignment. Each
agent (in our case, a mobile robot) is assigned to one task and each task is executed by one and only one
agent. Such a problem can be represented by bipartite graph 𝐺 = (𝑅 βˆͺ 𝑇 , 𝐸) with two vertex sets 𝑅 and
𝑇 such that every edge 𝑒 ∈ 𝐸 of the edge set 𝐸 = 𝑅 Γ— 𝑇 connects a vertex in 𝑅 to one in 𝑇 . Let 𝑅 be
a set of mobile robots 𝑖 ∈ 𝑅 and 𝑇 a set of tasks 𝑗 ∈ 𝑇 . Moreover, let 𝑐𝑖𝑗 be weight of edge (𝑖, 𝑗) ∈ 𝐸,
where 𝑖 ∈ 𝑅, 𝑗 ∈ 𝑇 . This weight can represent, e.g., cost of travel, travel time, distance, etc. The objective
is to find a minimum weight perfect matching of 𝐺, i.e., a perfect matching among vertices in 𝑅 and
vertices in 𝑇 such that the sum of the costs of the matched edges is minimum. An edge (𝑖, 𝑗) ∈ 𝐸 is
matched if two extreme vertices 𝑖 and 𝑗 are mutually matched, and a matching is perfect if every vertex
𝑖 ∈ 𝑅 is matched (assigned) to exactly one vertex 𝑗 ∈ 𝑇 , and viceversa. The LAP is equivalent to the
weighted bipartite matching, since we may assume that the bipartite graph is always complete by letting

The 7th Italian Workshop on Artificial Intelligence and Robotics - AIRO 2020, November 25–27, 2020, Online

                                       Β© 2020 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073       CEUR Workshop Proceedings (CEUR-WS.org)
the weights of the edges that are missing being sufficiently large. In case of different cardinalities, i.e.,
|𝑅| β‰  |𝑇 |, we can add a number of dummy nodes to the set with lower cardinality and connect them by
dummy arcs of zero cost to the other set. With only one decision maker, we speak about a centralized
MRTA solution approach, while in the presence of multiple decision makers, we have a distributed or a
decentralized case, depending on the context. Also, if the robot-task allocation is updated dynamically as
the robots move through environment, we speak about a dynamic MRTA. Conventional MRTA solution
approaches (e.g., [2, 4, 5]) need all the assignment information for functioning, which is unavailable in
intrinsically dynamic and decentralized environments. Distributed Constraint Optimization methods are
computationally expensive and are not scalable to large MRTA scenarios, e.g., [6]. In this work, we
compare in simulation the performance of the lexicographic ordering, First-Come-First-Served, and the
auction algorithm in the dynamic one-on-one MRTA considering perfect and imperfect communication.
The evaluation is done based on an online iterative algorithm for dynamic MRTA that facilitates coor-
dination decentralization. In each period, it enables a robot with a limited communication range i) to
exchange and update the allocation information in a multi-hop fashion with other communicating robots,
and ii) to find the task allocation in collaboration with them. The robot then moves one step towards the
assigned task. The process repeats until the robot reaches its target. Given that the Bertsekas auction
algorithm has quality of solution guarantees, we test the degradation of the MRTA performance from full
(perfect) to no communication in the team. Simulation results for the solution approaches considering
perfect information are presented in Section 2, while the results with imperfect communication are given
in Section 3, which closes the paper with conclusions and future work.



2. Dynamic MRTA with perfect information

   The lexicograpic ordering algorithm is the simplest computationally efficient algorithm for the
MRTA. First, the elements of each set are labeled. Then, the elements of one set are matched to the
elements of the other set in a one-on-one manner based on the nondecreasing alphabetical order of their
labels. Since the elements of the two sets are allocated randomly and there is no optimisation in the
process, we expect poor efficiency in terms of overall, minimum, and maximum distance passed by the
robot team. The found solution is feasible but not optimum.

   First-Come-First-Served (FCFS) (e.g., [7]) is the simplest scheduling algorithm that allocates the
first robot in the alphabetically ordered robot list (in the off-line case) or the first one that appears avail-
able (in the dynamic case) to the closest task to it. Then, the second one in the lexicographic order (or the
one becoming available after the first one) is assigned to the closest task out of all the remaining tasks,
and so on. In the end, the last robot is assigned to the last available task. This approach gives priority to
the robots that arrive earlier.

   The Bertsekas auction algorithm has quality of solution guarantees in the case of perfect task allo-
cation information available to all robot agents (e.g., [4, 5, 8]). Its advantage is that it is intuitive and can
be explained in economical terms. It considers individually rational bidder agents that interact with an
auctioneer agent in the bidding phase, while in the assignment phase, the auctioneer allocates the tasks
to the bidders considering the maximization of the system’s utilitarian welfare and updates the prices of
the tasks with the aim to resolve all conflicts among bidders and receive one and only one bid for each
task. This is similar to a conventional (e.g., English or Dutch) auction. The solution is approximately
optimal when one-on-one assignment is reached for all tasks.
3. Dynamic MRTA with imperfect communication

   Given a robot’s limited communication range, we assume that, in each period, robots have access
to the information about the locations of tasks but not to the locations of the robots located outside
their multi-hop communication graph (their connected component). The communicating robots in a
connected component perform task allocation through the auction algorithm, e.g., [5, 9]. The information
exchanged by communicating robots is the task they are assigned to, the distance they have travelled,
information about the task costs of other mobile robots they have encountered, and the period of last
update. In this way, in each time period, the tasks get (re-)allocated based on the exchanged information
that might not be up to date for the robots encountered previously. The most up-to-date information is
used to solve conflicts of differing information among the robots in a connected component, which may
differ from the actual updated information of the robots not present in the component. The algorithm
runs in phases. In the initialization phase, robots check if there are other communicating robots in their
communication range and exchange the task allocation cost matrix in a multi-hop manner. We assume
that robots share all the information. In the robot movement phase, a robot moves towards its assigned
task by the predefined speed. These phases conclude one iteration of the algorithm, and repeat until a
robot has reached the location of its assigned task.

   In [9, 10, 11], performance degradation of different auction-based allocation algorithms were tested
in simulated experiments with incomplete communication graphs with varying communication range.
Here, we compare the performance of the auction algorithm with the benchmark lexicographic and the
FIFO algorithm in a complete communication graph, considering the overall, average, minimum, and
maximum passed distance and the number of iterations. Moreover, we test the overall distance vs.
communication range and number of iterations to explore the convergence properties of the auction
algorithm with imperfect communication.



4. Simulation experiment setting and results

   For the dynamic MRTA, we tested the performance of the lexicographic, FCFS, and the auction algo-
rithm in a simulated 2D environment 𝐸𝑛𝑣 = [0; 10]2 βŠ‚ 𝐑2 in Matlab with a priori and dynamic allocation
of tasks and robots. We consider multi-robot teams composed of 10 to 50 mobile robots with the increase
of 10. We perform 3 experiments with uniformly randomly generated tasks’ and robots’ positions in 𝐸𝑛𝑣.
The overall and average passed distance in relation to the number of robots in the simulated experiments
can be seen in Figures 1a, 1b. We see decrease in every category we observed, total distance, average
distance, minimum distance and maximum distance. In all experiments the auction algorithm performed
the best, followed closely by FCFS algorithm. The biggest difference between auction and FCFS al-
gorithms is in the maximum distance, which was expected because the auction algorithm is optimised
algorithm, and in FCFS algorithm robots choose the closest tasks, and the mobile robots that are first
listed have better choices than those that are listed later.

   The strength of the FCFS method is that it lowers the average minimum distance and the average
distance that mobile robots travel compared to the lexicographic method, but the weakness is that the
distances aren’t distributed evenly among the mobile robots and the expected average distance passed
by all robots is still high, which is solved using an optimised algorithm like the auction algorithm. In
Figure 1c, it can be seen the minimum distances, and that for the FCFS and auction algorithm the min.
distances are much shorter and overall similar, while the lexicographical method has larger minimal
distances. The maximum distance, Figure 1d, show the biggest difference between algorithms. In Fig-
ures 2a, 2b the influence of the communication range is presented. The bigger the communication range
                (a) Total distance                                        (b) Avg. distance




                (c) Min. distance                                         (d) Max. distance
Figure 1: Key Performance Indicators of the dynamic MRTA with perfect information




      (a) Overall distance vs. comm. range                      (b) No. of iterations vs. comm. range




      (c) Overall distance vs. No. of robots                    (d) No. of iterations vs. No. of robots
Figure 2: Key Performance Indicators of the dynamic MRTA with imperfect information


the smaller is the overall distance travelled and the number of iterations. The biggest drop in overall
distance is between the values of 0 and 10. For our experiments the results converge around 60% of the
simulated area. In Figures 2c, 2d, the influence of the team size is presented. For increase in team size,
the overall distance increased less. With the combination of communication range and the number of
robots, the best results are with larger team sizes and a higher communication range.
In this paper, we considered a homogeneous one-on-one MRTA with deterministic perfect/imperfect in-
formation sharing and showed in simulation experiments that the auction algorithm outperforms the other
two methods. In future work, we will focus on heterogeneous robots and tasks with different priorities
and time windows, robots’ remaining battery autonomies, and fairness and envy-freeness issues.
References
 [1] B. Gerkey, M. J. Mataric, A formal framework for the study of task allocation in multi-robot
     systems, International Journal of Robotics Research 23 (2004) 939–954.
 [2] S. Giordani, M. Lujak, F. Martinelli, A distributed algorithm for the multi-robot task allocation
     problem, in: IEA/AIE 2010: International conference on industrial, engineering & other applica-
     tions of applied intelligent systems, volume 6096 of Lecture Notes in Computer Science, 2010, pp.
     721–730.
 [3] R. Burkard, M. Dell’Amico, S. Martello, Assignment problems: revised reprint, SIAM, 2012.
 [4] D. P. Bertsekas, Network optimization: continuous and discrete models, Athena Scientific Belmont,
     MA, 1998.
 [5] M. M. Zavlanos, L. Spesivtsev, G. J. Pappas, A distributed auction algorithm for the assignment
     problem, in: 47th IEEE Conference on Decision and Control, IEEE, 2008, pp. 1212–1217.
 [6] B. Faltings, Distributed constraint programming, in: Foundations of Artificial Intelligence, vol-
     ume 2, Elsevier, 2006, pp. 699–729.
 [7] M. Pinedo, Scheduling, volume 29, Springer, 2012.
 [8] M. Lujak, S. Giordani, A. Omicini, S. Ossowski, Decentralizing coordination in open vehicle fleets
     for scalable and dynamic task allocation, Complexity 2020 Open Access (2020) 1–21.
 [9] M. Lujak, S. Giordani, On the communication range in auction-based multi-agent target assign-
     ment, in: Proc. of the 5th International Workshop on Self-Organizing Systems, volume 6557 of
     LNCS, Springer, 2011, pp. 32–43.
[10] M. Lujak, S. Giordani, S. Ossowski, Value of incomplete information in mobile target allocation, in:
     Ninth German Conference on Multi-Agent System Technologies, volume 6973 of LNCS, Springer-
     Verlag Berlin, 2011, pp. 89–100.
[11] M. Otte, M. J. Kuhlman, D. Sofge, Auctions for multi-robot task allocation in communication
     limited environments, Autonomous Robots 44 (2020) 547–584.