On Efficiency in Dynamic Multi-Robot Task Allocation

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 environment. 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 guarantees. 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. 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 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 coordination 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 ifrst robot in the alphabetically ordered robot list (in the off-line case) or the first one that appears available (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 allocation 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 algorithm 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 algorithms 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 Figures 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 (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 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 information 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 applications 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 , volume 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 assignment , 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, SpringerVerlag 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 .