TraderBots: A New Paradigm for Robust and Efficient Multirobot Coordination in Dynamic Environments

M Bernardine Dias
doctoral dissertation, tech. report , Robotics Institute, Carnegie Mellon University, January, 2004


Download
  • Adobe portable document format (pdf) (4MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
The problem of efficient multirobot coordination has risen to the forefront of robotics research in recent years. The wide range of application domains demanding multirobot solutions motivates interest in this problem. In general, multirobot coordination strategies assume either a centralized approach, where a single robot/agent plans for the group, or a distributed approach, where each robot is responsible for its own planning. Inherent to many centralized approaches are difficulties such as intractable solutions for large groups, sluggish response to changes in the local environment, heavy communication requirements, and brittle systems with single points of failure. The key advantage of centralized approaches is that they can produce globally optimal plans. While most distributed approaches can overcome the obstacles inherent to centralized approaches, they can only produce suboptimal plans because they cannot take full advantage of information available to all team members.

This work develops TraderBots, a market-based coordination approach that is inherently distributed, but also opportunistically forms centralized sub-groups to improve efficiency. Robots are self-interested agents with the primary goal of maximizing individual profits. The revenue/cost models and rules of engagement are designed so that maximizing individual profit has the benevolent effect of, on average, moving the team toward the globally optimal solution. This approach inherits the flexibility of markets in allowing cooperation and competition to emerge opportunistically. The outlined approach addresses the multirobot coordination problem for autonomous robotic teams executing tasks in dynamic environments where it is highly desirable to produce efficient solutions. This dissertation details the first in-depth study of the applicability of market-based techniques to the multirobot coordination and provides a detailed study of the requirements for robust and efficient multirobot coordination in dynamic environments. Contributions of this dissertation are the first extensive investigation of the application of market-based techniques to multirobot coordination, the most versatile coordination-approach for dynamic multirobot application domains, the first distributed multirobot coordination-approach that allows opportunistic optimization by "leaders", the first in-depth investigation of the requirements for robust multirobot coordination in dynamic environments, the most extensively implemented market-based multirobot coordination approach, and the first systematic comparative analysis of multirobot coordination approaches implemented on a robot team.


Notes
Number of pages: 139

Text Reference
M Bernardine Dias, "TraderBots: A New Paradigm for Robust and Efficient Multirobot Coordination in Dynamic Environments," doctoral dissertation, tech. report , Robotics Institute, Carnegie Mellon University, January, 2004

BibTeX Reference
@phdthesis{Dias_2004_4675,
   author = "M Bernardine Dias",
   title = "TraderBots: A New Paradigm for Robust and Efficient Multirobot Coordination in Dynamic Environments",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "January",
   year = "2004",
}