DOC PREVIEW
TAMU CSCE 689 - parker06building

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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.002006 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

TAMU CSCE 689 - parker06building

Documents in this Course
slides

slides

10 pages

riccardo2

riccardo2

33 pages

ffd

ffd

33 pages

intro

intro

23 pages

slides

slides

19 pages

p888-ju

p888-ju

8 pages

w1

w1

23 pages

vfsd

vfsd

8 pages

subspace

subspace

48 pages

chapter2

chapter2

20 pages

MC

MC

41 pages

w3

w3

8 pages

Tandem

Tandem

11 pages

meanvalue

meanvalue

46 pages

w2

w2

10 pages

CS689-MD

CS689-MD

17 pages

VGL

VGL

8 pages

ssq

ssq

10 pages

Load more
Download parker06building
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view parker06building and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view parker06building 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?