INVITEDPAPERBuilding Multirobot CoalitionsThrough Automated TaskSolution SynthesisA group of robots can move to, or push boxes to, specified locations by sharinginformation when individual robots cannot perform the tasks separately.By Lynne E. Parker, Senior Member IEEE, and Fang Tang, Student Member IEEEABSTRACT|This paper presents a reasoning system thatenables a group of heterogeneous robots to form coalitions toaccomplish a multirobot task using tightly coupled sensorsharing. Our approach, which we call ASyMTRe, maps environ-mental sensors and perceptual and motor control schemas tothe required flow of information through the multirobot sys-tem, automatically reconfiguring the connections of schemaswithin and across robots to synthesize valid and efficientmultirobot behaviors for accomplishing a multirobot task. Wepresent the centralized anytime ASyMTRe configuration algo-rithm, proving that the algorithm is correct, and formally ad-dressing issues of completeness and optimality. We thenpresent a distributed version of ASyMTRe, called ASyMTRe-D,which uses communication to enable distributed coalition for-mation. We validate the centralized approach by applying theASyMTRe methodology to two application scenarios: multi-robot transportation and multirobot box pushing. We thenvalidate the ASyMTRe-D implementation in the multirobottransportation task, illustrating its fault-tolerance capabilities.The advantages of this new approach are that it: 1) enablesrobots to synthesize new task s olutions using fundamentallydifferent combinations of sensors and effectors for differentcoalition compositions and 2) provides a general mechanismfor sharing sensory information across networked robots.KEYWORDS|Coalition formation; information invariants;multirobot teams; schema theory; sensor sharing; taskallocationI. INTRODUCTIONResearchers generally agree that multirobot systems haveseveral advantages over single-robot systems [1], [5]. Themost common motivations for developing multirobot sys-tem solutions are that: 1) the task complexity is too highfor a single robot to accomplish; 2) the task is inherentlydistributed; 3) building several resource-bounded robots ismuch easier than having a single powerful robot; 4) mul-tiple robots can solve problems faster using parallelism;and 5) the introduction of multiple robots increases ro-bustness through redundancy. The issues that must beaddressed in developing multirobot solutions are depen-dent upon the task requirements and the sensory andeffector capabilities of the available robots. The earliestresearch in multirobot systems focused on swarm intelli-gence approaches using homogeneous robot teams, in-spired by insect societies (e.g., [3], [28]). In theseapproaches, individual robots typically perform the sametype of subtask in the same environment, resulting inglobal group behaviors that emerge from the local inter-action of individual robots. The fundamental researchchallenge in these systems is designing the local controllaws so as to generate the desired global team behavior.Other types of robot systems involve heterogeneousrobots, which have differing sensor and effector capabil-ities. In these teams, the mapping of tasks to robots ismuch more important to the efficiency of the system, sincerobots vary in the quality of their solutions to tasks. Tra-ditionally, this problem has been called the multirobot taskallocation (MRTA) problem. Gerkey [14] has developed ataxonomy for describing these problems, distinguishingrobots as either single-task (ST) or multitask (MT), tasks aseither single-robot (SR) or multirobot (MR), and assign-menttypesaseitherinstantaneous (IA) or time-extended(TA). The vast majority of prior work on MRTA (e.g., [4],Manuscript received June 1, 2005; revised June 1, 2006.The authors are with the Distributed Intelligence Laboratory, Department of ComputerScience, University of Tennessee, Knoxville, TN 37996 USA (e-mail: [email protected];[email protected]).Digital Object Identifier: 10.1109/JPROC.2006.876933Vol. 94, No. 7, July 2006 | Proceedings of the IEEE 12890018-9219/$20.002006 IEEEAuthorized licensed use limited to: University of Southern California. Downloaded on September 22, 2009 at 23:45 from IEEE Xplore. Restrictions apply.[8], [16], [23], [31], [45], [47], [48]) has addressed single-task robots executing single-robot tasks using eitherinstantaneous assignment (denoted ST-SR-IA) or time-extended assignment (denoted ST-SR-TA).In this paper, we address a different problem in theMRTA taxonomyVnamely, single-task robots performingmultirobot tasks using instantaneous assignment (ST-MR-IA). In other words, we are addressing the development ofheterogeneous robot coalitions that solve a single multirobottask. While this problem has been addressed extensively inthe multiagent community (e.g., [24], [36], [37]), it hasbeen noted by Vig [44] that most of the multiagent ap-proaches to coalition formation cannot be directly trans-ferred to multirobot applications, since robot capabilitiesand sensors are situated directly on the robots and are nottransferable between robots. Our approach is aimed atenabling sensor-sharing across robots for the purpose offorming coalitions to solve single-multirobot tasks.More generally, multirobot coalition formation dealswith the issue of how to organize multiple robots intosubgroups to accomplish a task. Coalitions are typicallyconsidered to be temporary organizations of entities thatbring together diverse capabilities for solving a particulartask that cannot be handled by single robots. Coalitions aresimilar to the idea of teams,exceptthattheytypicallyhavea shorter duration and can change frequently over time.We are particularly interested in automated techniques forcoalition formation, especially when the specific tasksolution is highly dependent upon the available capabilitiesof the heterogeneous robots, and thus cannot be specifiedin advance. This is especially challenging in heterogeneousrobot systems, in which sensory and computational re-sources are distributed across different robots. For such agroup to accomplish the task as a whole, it must determinehow to couple the appropriate sensory and computationalcapabilities from each robot, resulting in automaticallyformed coalitions that serve specific purposes.To address this challenge, we present our approachcalled ASyMTRe (which stands for BAutomated Synthesisof Multirobot Task solutions through software Recon-figuration,[
View Full Document