In this work we address the Multi-Robot Task Allocation Problem (MRTA). We assume that the decision making environment is decentralized with as many decision makers (agents) as the robots in the system. To solve this problem, we developed a distributed version of the Hungarian Method for the assignment problem. The robots autonomously perform different substeps of the Hungarian algorithm on the base of the individual and the information received through the messages from the other robots in the system. It is assumed that each robot agent has an information regarding its distance from the targets in the environment. The inter-robot communication is performed over a connected dynamic communication network and the solution to the assignment problem is reached without any common coordinator or a shared memory of the system. The algorithm comes up with a global optimum solution in O(n^3) cumulative time (O(n^2) for each robot), with O(n^3) number of messages exchanged among the n robots.
Giordani, S., Lujak, M., Martinelli, F. (2010). A Distributed algorithm for the multi-robot task allocation problem. In Trends in applied intelligent systems: 23rd International conference on industrial engineering and other applications of applied intelligent systems: IEA/AIE 2010, Cordoba, Spain, June 1-4, 2010: proceedings (pp.721-730). Berlin : Springer [10.1007/978-3-642-13022-9_72].
A Distributed algorithm for the multi-robot task allocation problem
GIORDANI, STEFANO;MARTINELLI, FRANCESCO
2010-01-01
Abstract
In this work we address the Multi-Robot Task Allocation Problem (MRTA). We assume that the decision making environment is decentralized with as many decision makers (agents) as the robots in the system. To solve this problem, we developed a distributed version of the Hungarian Method for the assignment problem. The robots autonomously perform different substeps of the Hungarian algorithm on the base of the individual and the information received through the messages from the other robots in the system. It is assumed that each robot agent has an information regarding its distance from the targets in the environment. The inter-robot communication is performed over a connected dynamic communication network and the solution to the assignment problem is reached without any common coordinator or a shared memory of the system. The algorithm comes up with a global optimum solution in O(n^3) cumulative time (O(n^2) for each robot), with O(n^3) number of messages exchanged among the n robots.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
