Task allocation is an important aspect of many multi-robot systems. The features and complexity of multi-robot task allocation (MRTA) problems are dictated by the requirements of the particular domain under consideration. These problems can range from those involving instantaneous distribution of simple, independent tasks among members of a homogenous team, to those requiring the time-extended scheduling of complex interrelated multi-step tasks for members of a heterogenous team related by several constraints. The existing widely used taxonomy for task allocation in multi-robot systems was designed for problems with independent tasks and does not deal with problems with interrelated utilities and constraints. While that taxonomy was a ground-breaking contribution to the MRTA literature, a survey of recent work in MRTA reveals that it is no longer a sufficient taxonomy, due to the increasing importance of interrelated utilities and constraints in realistic MRTA problems under consideration. Thus, in this paper, we present a new, comprehensive taxonomy, iTax, that explicitly takes into consideration the issues of interrelated utilities and constraints. Our taxonomy maps categories of MRTA problems to existing mathematical models from combinatorial optimization and operations research, and hence draws important parallels between robotics and these fields.
BektasT (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega34(3): 209–219.
4.
BerhaultMHuangHKeskinocakP. (2003) Robot exploration with combinatorial auctions. In: Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003 (IROS 2003), volume 2. pp. 1957–1962.
5.
BiancoLDell’OlmoPGiordaniSSperanzaMG (1999) Minimizing makespan in a multimode multiprocessor shop scheduling problem. Naval Research Logistics46: 893–911.
6.
BotelhoSCAlamiR (1999) M+: a scheme for multirobot cooperation through negotiated task allocation and achievement. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 1234–1239.
7.
BredströmDRönnqvistM (2007) A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. Discussion Paper Number FOR7, Norwegian School of Economics and Business Administration, Department of Finance and Management Science.
8.
BredströmDRönnqvistM (2008) Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. European Journal of Operations Research191: 19–31.
BrummitBStentzA (1998) GRAMMPS: A generalized mission planner for multiple mobile robots. In: Proceedings of the IEEE International Conference on Robotics and Automation.
11.
BrunoJE G CoffmanJSethiR (1974) Scheduling independent tasks to reduce mean finishing time. Communications of the ACM17: 382–387. DOI: 10.1145/361011.361064.
12.
ChienSBarrettAEstlinTRabideauG (2000) A comparison of coordinated planning methods for cooperating rovers. In: Proceedings of the Fourth International Conference on Autonomous Agents (AGENTS ’00). New York: ACM Press, pp. 100–101. DOI: 10.1145/336595.337057.
13.
CordeauJFLaporteG (2007) The dial-a-ride problem: models and algorithms. Annals of Operations Research153(1): 29–46.
14.
DesaulniersGDesrosiersJErdmannASolomonMMSoumisF (2001) VRP with pickup and delivery. In: The Vehicle Routing Problem. Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 225–242.
15.
DiasMB (2004) TraderBots: A New Paradigm for Robust and Efficient Multirobot Coordination in Dynamic Environments. Ph.D. thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
16.
GerkeyBP (2003) On Multi-Robot Task Allocation. Ph.D. thesis, University of Southern California Computer Science Department, Los Angeles, CA.
17.
GerkeyBPMataric’MJ (2002) Sold!: auction methods for multirobot coordination. IEEE Transactions on Robotics and Automation18(5): 758–768.
18.
GerkeyBPMataric’MJ (2004) A formal analysis and taxonomy of task allocation in multi-robot systems. The International Journal of Robotics Research23(9): 939–954.
19.
GuerreroJOliverG (2003) Multi-robot task allocation strategies using auction-like mechanisms. Artificial Intelligence Research and Development in Frontiers in Artificial Intelligence and Application100: 111–122.
20.
JonesEDiasMBStentzAT (2009) Time-extended multi-robot coordination for domains with intra-path constraints. In: Robotics: Science and Systems (RSS).
21.
JonesEG (2009) Multi-Robot Coordination in Domains with Intra-path Constraints. Ph.D. thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
22.
KoenigSToveyCZhengXSungurI (2007) Sequential bundle-bid single-sale auction algorithms for decentralized control. In: Proceedings of the 20th International Joint Conference on Artifical Intelligence. San Francisco, CA: Morgan Kaufmann, pp. 1359–1365.
23.
KoesMNourbakhshISycaraK (2006) Constraint optimization coordination architecture for search and rescue robotics. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) 2006, pp. 3977–3982.
24.
KorsahGA (2011) Exploring Bounded Optimal Coordination for Heterogeneous Teams with Cross-schedule Dependencies. Ph.D. thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
25.
KorsahGAKannanBBrowningBStentzADiasMB (2012) xBots: An approach to generating and executing optimal multi-robot plan with cross-schedule dependencies. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) 2012.
26.
KuhnHW (1955) The Hungarian method for the assignment problem. Naval Research Logistics Quarterly2: 83–97.
27.
LagoudakisMGMarkakisEKempeD. (2005) Auction-based multi-robot routing. In: Proceedings of Robotics: Science and Systems, Cambridge, MA.
LarsenJDohnARasmussenMS (2009) The Vehicle Routing Problem with Time Windows and Temporal Dependencies. Technical Report 1.2009, DTU Management Engineering.
30.
LemaireTAlamiRLacroixS (2004) A distributed tasks allocation scheme in multi-UAV context. In: Proceedings of the 2004 IEEE International Conference on Robotics and Automation, 2004 (ICRA 2004).
31.
LenstraJKRinnooy KanAHG (1978) Complexity of scheduling under precedence constraints. Operations Research26(1): 22–35. DOI: 10.1287/opre.26.1.22.
32.
LinLZhengZ (2005) Combinatorial bids based multi-robot task allocation method. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 2005 (ICRA 2005), pp. 1145–1150.
33.
MacKenzieDC (2003) Collaborative tasking of tightly constrained multi-robot missions. In: SchultzACParkerLESchneiderFE (eds.) Multi-Robot Systems: From Swarms to Intelligent Automata (Proceedings Second International Workshop on Multi-Robot Systems), volume 2. Washington, DC: Kluwer Academic Publishers, pp. 39–50.
MelvinJKeskinocakPKoenigSToveyCAOzkayaBY (2007) Multi-robot routing with rewards and disjoint time windows. In: Intelligent Robots and Systems (IROS) 2007, pp. 2332–2337.
36.
MosteoAMontanoLLagoudakisMG (2008) Multi-robot routing under limited communication range. In: Proceedings of the IEEE International Conference on Robotics and Automation, Pasadena, CA, pp. 1531–1536.
37.
ParkerLE (1998) Alliance: An architecture for fault tolerant multi-robot cooperation. IEEE Transactions on Robotics and Automation14: 220–240.
38.
ParkerLETangF (2006) Building multirobot coalitions through automated task solution synthesis. Proceedings of the IEEE94(7): 1289–1305. DOI: 10.1109/JPROC.2006.876933.
39.
RamchurnSDPolukarovMFarinelliATruongCJenningsNR (2010) Coalition formation with spatial and temporal constraints. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS ’10), Vol. 3. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, pp. 1181–1188.
40.
RasmussenMSJustesenTDohnALarsenJ (2010) The Home Care Crew Scheduling Problem: Preference-based Visit Clustering and Temporal Dependencies. Technical Report 11.2010, DTU Management Engineering.
41.
SavelsberghM (1997) A branch-and-price algorithm for the generalized assignment problem. Operations Research45(6): 831–841. DOI: 10.1287/opre.45.6.831.
42.
ShehoryOKrausS (1995) Task allocation via coalition formation among autonomous agents. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence, Vol. 1. San Francisco, CA: Morgan Kaufmann, pp. 655–661.
43.
ShehoryOKrausS (1998) Methods for task allocation via agent coalition formation. Artificial Intelligence101(1–2): 165–200. DOI: 10.1016/S0004-3702(98)00045-9.
44.
ShiromaPCamposM (2009) Comutar: A framework for multi-robot coordination and task allocation. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009 (IROS 2009), pp. 4817–4824. DOI: 10.1109/IROS.2009.5354166.
45.
ShmoysDBTardosE (1993) An approximation algorithm for the generalized assignment problem. Mathematical Programming62: 461–474. DOI: 10.1007/BF01585178.
46.
SimmonsRGApfelbaumDBurgardW. (2000) Coordination for multi-robot exploration and mapping. In: Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence. AAAI Press/The MIT Press, pp. 852–858.
47.
TothPVigoD (2001) An overview of vehicle routing problems. In: The Vehicle Routing Problem. Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 1–26.
48.
VailDVelosoMs (2003) Multi-robot dynamic role assignment and coordination through shared potential fields. In: SchultzAParkerLSchneiderF (eds.) Multi-Robot Systems. Dordrecht: Kluwer.
VotawDJrOrdenA (1952) The personnel assignment problem. In: Symposium on Linear Inequalities and Programming. Washington, DC: Planning Research Division, Comptroller, Headquarters U.S. Air Force, pp. 155–163.
51.
ZlotRM (2006) An Auction-Based Approach to Complex Task Allocation for Multirobot Teams. Ph.D. thesis, Robotics Institute, Carnegie Mellon University.
