Advanced Search

Journal Navigation

Journal Home

Subscriptions

Archive

Contact Us

Table of Contents

SAGETRACK

Sign In to gain access to subscriptions and/or personal tools.
The International Journal of Robotics Research
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to Saved Citations
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow Request Reprints
Right arrow Add to My Marked Citations
Citing Articles
Right arrow Citing Articles via ISI Web of Science (3)
Right arrow Citing Articles via Google Scholar
Right arrow Citing Articles via Scopus
Google Scholar
Right arrow Articles by Lerman, K.
Right arrow Articles by Mataric, M. J
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati  
What's this?

Analysis of Dynamic Task Allocation in Multi-Robot Systems

Kristina Lerman

Information Sciences Institute University of Southern California Los Angeles, CA 90089-0781, USA lerman{at}isi.edu

Chris Jones

iRobot Corporation 63 South Ave Burlington, MA 01803 cjones{at}irobot.com

Aram Galstyan

Information Sciences Institute University of Southern California Los Angeles, CA 90089-0781, USA galstyan{at}isi.edu

Maja J Mataric

Computer Science Department University of Southern California Los Angeles, CA 90089-0781, USA maja{at}robotics.usc.edu

Dynamic task allocation is an essential requirement for multi-robot systems operating in unknown dynamic environments. It allows robots to change their behavior in response to environmental changes or actions of other robots in order to improve overall system performance. Emergent coordination algorithms for task allocation that use only local sensing and no direct communication between robots are attractive because they are robust and scalable. However, a lack of formal analysis tools makes emergent coordination algorithms difficult to design. In this paper we present a mathematical model of a general dynamic task allocation mechanism. Robots using this mechanism have to choose between two types of tasks, and the goal is to achieve a desired task division in the absence of explicit communication and global knowledge. Robots estimate the state of the environment from repeated local observations and decide which task to choose based on these observations. We model the robots and observations as stochastic processes and study the dynamics of the collective behavior. Specifically, we analyze the effect that the number of observations and the choice of the decision function have on the performance of the system. The mathematical models are validated in a multi-robot multi-foraging scenario. The model's predictions agree very closely with results of embodied simulations.

Key Words: emergent coordination • mathematic analysis • foraging

The International Journal of Robotics Research, Vol. 25, No. 3, 225-241 (2006)
DOI: 10.1177/0278364906063426
Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us   Add to Digg Digg   Add to Reddit Reddit   Add to Technorati Technorati    What's this?