Auction-based Multi-Robot Coordination
Overview |
---- | Introduction |
---- | Communication Model |
---- | Auction Protocol |
Experimental Validation |
---- | Publications |
---- |
Videos |
Overview
The key to utilizing the potential of multi-robot systems is coordination. How can we achieve coordination in systems composed of failure-prone autonomous robots operating in noisy, dynamic environments? In this project, we have developed a novel method of dynamic task allocation for groups of such robots. We implemented and tested an auction-based task allocation system which we call MURDOCH, built upon a principled, resource-centric, publish/subscribe communication model. A variant of the Contract Net Protocol, MURDOCH produces a distributed approximation to a global optimum of resource usage. To date we have validated MURDOCH in two very different domains: a tightly-coupled multi-robot physical manipulation task and a loosely-coupled many-robot experiment in long-term autonomy. The primary contribution of this project has been to show empirically that distributed negotiation mechanisms such as MURDOCH are viable and effective for coordinating physical multi-robot systems.
Introduction
In deciding who should do what in a robot team, we take inspiration from the distributed artificial intelligence (DAI) community. Specifically, we employ fitness-based auctions and a simple negotiation protocol. The concept of negotiation necessarily entails some form of task commitment, which can complicate system design and might hinder performance or fault-tolerance. However, a large class of tasks, especially those involving physical state, can benefit from the robots' willingness to commit. Furthermore, as we have demonstrated, task allocation based on explicit negotiation can be an effective and fault-tolerant method for controlling multi-robot systems. Thus, this project answers the challenge posed by Lynne Parker in 1998:"[Negotiation-based] solutions have not been adequately demonstrated in situated agent (i.e., robotic) teams, which have to live in, and react to, dynamic and uncertain environments amidst noisy sensors and effectors, frequent agent failures, and a limited bandwidth, noisy communication mechanism."To address this challenge, we have developed a novel method of dynamic task allocation for groups of robots. We have implemented and tested MURDOCH, a general task allocation system based on a principled, resource-centric, publish/subscribe communication model that makes extensive (but efficient) use of explicit inter-robot communication. MURDOCH is a variant of the well-known Contract Net Protocol (CNP), and uses simple auctions to allocate tasks. Since our goal is not to exploit resources in a globally optimal fashion, but rather to investigate practical and efficient methods for allocating tasks to groups of autonomous and heterogeneous physical robots, we have built MURDOCH as a completely distributed system. As such, it offers a distributed approximation to a global optimum of resource usage which is equivalent to an instantaneous greedy scheduler. We have validated this system in two very different domains: a tightly-coupled multi-robot physical manipulation task and a loosely-coupled many-robot experiment in long-term autonomy. A primary contribution of this project is to empirically demonstrate that distributed negotiation mechanisms, such as MURDOCH, are indeed viable and efficient for coordinating physical multi-robot systems.
Communication Model
In implementing distributed control systems for teams of robots, researchers typically resort to ad hoc communication strategies. These specialized strategies are often implemented as hand-crafted, task-specific communication graphs. While this model is well-suited to the design of special-purpose, single-task systems, it has not been demonstrated for the general case of controlling a large groups, in which the members dynamically form teams to accomplish different tasks as they are presented to the system. As an alternative to such special-purpose systems, we use a principled communication model based on publish/subscribe messaging, an instance of anonymous communication.Background
The unifying concept of publish/subscribe systems is that messages are addressed by content rather than by destination. This idea, often called subject-based addressing, is used to divide the network into a loosely-coupled association of anonymous data producers and data consumers. A data producer simply tags a message with a subject describing its content, and "publishes" it onto the network; any data consumers who have registered interest in that subject by "subscribing" will automatically receive the message. Data producers need not have any knowledge of which consumers, if any, are receiving their messages, and vice versa. This kind of communication represents a fundamental departure from the traditional unicast model. We have tailored this idea slightly so that when a message is published, it is addressed to a set of subjects, rather than just one. A data consumer will receive a message if the subjects in the message comprise any subset of the consumer's current subscription list. Although we have not optimized the subset matching algorithm in our implementation, others have investigated the topic.Subject Namespace
The first step in creating a publish/subscribe system is designating the semantics of the subject namespace. Analogous to deciding the layout of a database, the interpretation of subjects will heavily influence the rest of the system. In MURDOCH, since we are allocating tasks among a group of potentially heterogeneous robots, we use subjects to represent their "resources." Resources can be physical devices (e.g., camera, gripper, sonar), higher-level capabilities (e.g., mobile, door-opener) or abstracted notions of current state (e.g., idle, have-puck, currently-pushing-box). Thus, if we have a task that involves going to some location and observing it, we can reach the capable robots (who are otherwise unengaged) by addressing a message to the set {mobile camera idle}. Since messages are addressed to subjects and subjects represent resources, all inter-robot communication will necessarily be resource-centric, which we believe to be fundamental in achieving our goals. The robots never interact with each other by name and in fact have no explicit knowledge of each others' existence; rather they only communicate about tasks and all messages are addressed in terms of the resources required to perform those tasks.Auction Protocol
At the heart of MURDOCH lies a simple distributed negotiation protocol that allocates tasks via a sequence of first-price one-round auctions. The process is triggered by the introduction of a task to the system. The task could be introduced in many ways, including a human user, a cron-style alarm, or an already ongoing task. In every case, the auction proceeds in five steps:- Task announcement - An agent (working on behalf of a user, alarm, or task) acts as ``auctioneer'' by publishing an announcement message for the task. The message contains details about the task, such as its name, length, and a new subject on which to negotiate it. The message is addressed to the set of subjects which represent the resources required to execute the task; thus only those robots currently capable of performing the task will receive the message.
- Metric evaluation - Since there may be more than one capable robot available for a given task, we need a method for deciding among them. This decision process is the very basis of achieving effective task allocation; the goal is to allocate each task to the most fit robot. Thus the announcement also includes metric(s) with which each candidate robot can determine its fitness (see next section for details on metrics).
- Bid submission - After evaluating the appropriate metric(s), each candidate robot publishes its resulting task-specific fitness "score" as a bid message.
- Close of auction - After sufficient time has passed, the auctioneer processes the bids, determines the winner, and notifies the bidders with a close message. The winner is awarded a time-limited contract to execute the task and the losers return to listening for new tasks.
- Progress monitoring / contract renewal - While the winner executes the task, the auctioneer monitors task progress. Assuming sufficient progress is being made, the auctioneer periodically sends a renewal message to the winner, which responds with an acknowledgment message, until the task is completed.
The fact that the winner's contract is time-limited is an essential part of MURDOCH's fault-tolerant capabilities. Recalling the argument for "soft state", time-limited contracts provide a built-in timeout that can trigger fault detection and recovery. For example, if the auctioneer fails to receive an acknowledgment after sending a renewal, it can assume that the robot previously executing the task has failed and so it can reassign the task. Similarly, the task can be reassigned if the auctioneer finds that insufficient progress has been made. In either case, the previous winner will terminate task execution when its contract has expired without renewal.
Since each task will always be claimed by the most capable robot available at the time, MURDOCH acts as an instantaneous greedy task scheduler. Thus it suffers from the well-known problems of greedy algorithms; they are manifested in our domain as situations in which, although sufficient resources exist to achieve a given set of tasks, the order in which the tasks are presented causes resources to be exploited in a non-optimal manner such that not all the tasks are actually achieved. Centralized broker and matchmaker systems sometimes avoid this pitfall by analyzing concurrent tasks before allocating them. That kind of planning, however, will not help in the class of domains where individual tasks are input stochastically from some outside source, such as a human user.
Metrics
Metrics can take many forms, with the restriction that each one, when evaluated in the context of a specific robot, should return a scalar "score" representing that robot's fitness for the task. A metric is usually defined as some function of the robot's current state, although in general, a metric could perform any arbitrary computation, including inter-robot communication. As an example, if the task under consideration is to go to a certain location and pick up an object, one possible metric is to compute the Cartesian distance from the robot's current position to the goal position, with a shorter distance scoring better. Multiple metrics can be defined for a single task, with the final score being some combination of the individual scores; we have experimented with combining metrics through both simple sums and weighted sums that allow for a prioritization of metrics. It is important to note that metrics, being functions of each robot's own sensor data, may not accurately represent the current state of the robots, possibly resulting in a non-optimal allocation of the task. Since finding an optimal allocation would require gathering global data, guaranteeing its accuracy, and centralizing control, we find our metric-based distributed approximation to be a parsimonious alternative.
Experimental Validation
In order to validate our approach, we have performed experiments with MURDOCH on our Pioneer mobile robots in two different task domains.The first domain, shown in Figure 1, is a tightly-coupled cooperative box-pushing task. The two pushing robots must push the large box to a goal location, but they cannot see over the box to the goal. So, a third robot, acting as a "watcher", guides the coordination of the pushers by continually auctioning new pushing tasks (e.g., "push-left-side-of-box", "push-right-side-of-box"). These tasks are automatically allocated by MURDOCH to the most capable pusher. If a pusher fails during the task, the systems degrades gracefully, with the other pusher picking up the slack (see videos for examples).
|
We are also interested in exploring long-term autonomy, in which the robots are awake and available for long periods of time, and can be dynamically tasked and retasked. To that end, we have experimented with MURDOCH in allocating a variety of loosely-coupled single-robot tasks to a group of robots over periods of time up to 3 hours (see Figure 2). The tasks are stochastically introduced, and eligible (and available) robots bid for them, with the most fit robot claiming each task. The tasks are relatively short-lived (less than 10 minutes), so over an entire experiment, each robot executes many different tasks. The robots in the group are heterogeneous, having a variety of sensors, including lasers, cameras, and tactile bumpers; each task requires a unique subset of these resources. Since the experiments run for a relatively long time, the robots automatically seek a charging station (and revoke their availability for future tasks) when their battery levels are low.
|
Relevant Publications
-
"Sold!: Auction methods for multi-robot coordination".
Brian P. Gerkey and Maja J Mataric´. IEEE Transactions on Robotics and Automation, Special Issue on Multi-robot Systems, 18(5):758-768, October 2002. (Also Technical Report IRIS-01-399)
[PDF: 684k] -
"Pusher-watcher: An approach to fault-tolerant tightly-coupled
robot coordination".
Brian P. Gerkey and Maja J Mataric´. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2002), pages 464 - 469, Washington, DC, May 11 - 15, 2002. (Also Technical Report IRIS-01-403)
[gzipped PS: 144k] [PDF: 164k]
-
"Principled Communication for Dynamic Multi-Robot Task Allocation".
Brian Gerkey and Maja J Mataric´. In D. Rus and S. Singh, editors, Experimental Robotics VII, LNCIS 271, pages 353-362. Springer-Verlag Berlin Heidelberg, 2001 (ISER 2000).
[gzipped PS: 372k] [PDF: 192k] -
"MURDOCH: Publish/Subscribe Task Allocation for
Heterogeneous Agents".
Brian Gerkey and Maja J Mataric´. In Proceedings of Autonomous Agents 2000, Barcelona, Spain, June 3-7, 2000, pp 203-204.
[gzipped PS: 32k] [PDF: 80k]