FIRE

Market-Based Multirobot Coordination

This work focusses on developing a market-based architecture that is inherently distributed, but also opportunistically forms centralized sub-groups to improve efficiency, and thus approach optimality. Robots in this architecture 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 moving the team toward the globally optimal solution. This architecture inherits the flexibility of market-based approaches in allowing cooperation and competition to emerge opportunistically.

A Simple Example

A principal advantage of the market-based architecture is its ability to opportunistically optimize resource utilization. A simple example is illustrative. Consider a system where we want two items to be retrieved. Two robots are available to do the task.

Figure 1: An illustration of simple reasoning.

The robots incur costs in driving, as indicated by the numerical labels in Figure 1. The robots bid on each of the tasks. The robots are only smart enough to reason about single city tours. Robot 1 bids the cost plus a profit of 20 for task A (120). Robot 2 cannot compete for this task since its costs alone are 220. Robot 1 wins task A. For similar reasons, Robot 2 wins Task B. Both robots are happy, since each makes a profit. The user is happy, since the task is accomplished with a reasonable solution.

Figure 2: An illustration of more complex reasoning.

Now assume that Robot 2 becomes smarter because it acquired more computer power or received a better algorithm. Robot 2 suggests to Robot 1 that it perform Task B immediately after Task A before returning to its base as illustrated in Figure 2. If Robot 2 can subcontract Task B, it will save 150 in cost. Therefore, it will do so if it pays out less than 150. Robot 1 considers the request and determines that the new route will add 110 in cost. Therefore, it will take the subcontract if it will receive more than 110. The two negotiate and agree on 130. Both robots are happy, since they increased their profits, and we are happy because the global task was accomplished at lower cost. Note that Robot 2 was a leader; it didn't do anything except generate and sell a plan. It didn't lead by coercion; instead, it used the additional profit to "buy off" the participant. Good plans generate more profits that can be used to gain participants. Note further that this plan could have been proposed to both robots by a third robot playing a "leader role."

The Market-Based Approach

Consider an economic system for coordinating robots. An economy is essentially a population of agents (i.e., citizens) producing a global output. The agents coordinate with each other to produce an aggregate set of goods. Individuals are often in the best position to understand their needs and the means to satisfy them. In a market economy individuals reap the direct benefits of their own good decisions and suffer the direct consequences of their bad ones. At times they cooperate with other members of the society to achieve an outcome greater than that possible by each member alone. At times they compete with other members to provide goods or services at the lowest possible cost, thus eliminating waste and inefficiency. But at every turn, the individual members act solely to reap the greatest profit for themselves. An important aspect of the market-based approach is that the robots are self-interested.

The Market Mechanism

Consider a team robots assembled to perform a particular set of tasks. Consider further, that each robot in the team is modeled as a self-interested agent, and the team of robots as an economy. Thus, the goal of the team is to complete the tasks successfully while minimizing overall costs, since each robot will aim to minimize its individual cost and maximize its individual profit. A system such as this will inherit many desirable characteristics from the market mechanisms. Presented here is a brief examination of some of these characteristics.

Determining Revenues and Costs
Costs and revenues will dictate to a large extent the performance of a market-based approach. A function, trev, is needed to map possible task outcomes onto revenue values. Another function, tcost, is needed that maps possible schemes for performing the task onto cost values. As a team, the goal is to execute some plan P such that profit, trev(P) - tcost(P), is maximized. Note that trev and especially tcost will not always be simple functions. These functions will need to reflect aspects such as priorities for task completion, hard deadlines for relevant tasks, and acceptable margins of error for different tasks.
Individuals are compensated in accordance with their contribution to the overall task, based on factors that are within the control of the individual. An individual that maximizes its own personal production and minimizes its own personal cost receives a larger share of the overall profit. Note that the revenue/cost models and rules of engagement will be designed so that maximizing individual profit has the benevolent effect of moving the team toward the globally optimal solution.

The Role of Price and the Bidding Process
Robots receive revenue and incur costs for accomplishing a specific team task, but the team's revenue function is not the only source of income. A robot can also receive revenue from another robot in exchange for goods or services. In general, two robots have incentive to deal with each other if they can produce more aggregate profit together than apart --- such outcomes are win-win rather than zero-sum. How is the price determined? The idea is to "strike a bargain" by bidding a price that is personally most favorable, and then successively retreating from this position until a price is mutually agreed upon. Based on basic economic intuition, the negotiated price will tend toward the intersection of the supply and demand curves for a given service. Note that a given robot can negotiate several potential deals at the same time, and that a deal can be multi-party, requiring that all parties agree before any part of the deal is binding. It is important to note that price and bidding are low bandwidth mechanisms for communicating aggregate information about costs.

Cooperation vs. Competition
Two robots are cooperative if they have complementary roles, that is, if both robots can make more profit by working together than by working individually. Conversely, two robots are competitive if they have the same role; that is, if the amount of profit that one can make is negatively affected by the presence of the other robot. Individual robots and robot teams, whether homogeneous or heterogeneous, may be cooperative or competitive depending on the roles they seek. The flexibility of the market-model allows the robots to cooperate and compete as necessary to accomplish a task, regardless of the homogeneity or heterogeneity of the team.

Self Organization
Conspicuously absent from the market is a rigid, top-down hierarchy. Instead, the robots organize themselves in a way that is mutually beneficial. Since the aggregate profit amassed by the individuals is directly tied to the success of the task, this self-organization yields the best results. But there is a limit to this organization. As the group becomes larger, the combinatorics become intractable and the process of gathering all of the relevant information to produce a good group-level plan becomes increasingly difficult.

Learning and Adaptation
The robot economy is able to learn new behaviors and strategies as it executes its task. This learning applies to both individual behaviors and negotiations as well as to the entire team. Individual robots may learn that certain strategies are not profitable, or that certain robots are apt to break a contract by failing to deliver the goods or proper payment. Individuals may also learn successful bidding strategies or which deals to offer when. One of the greatest strengths of the market economy is its ability to deal successfully with changing conditions. Since the economy does not rely on a hierarchical structure for coordination and task assignment, the system is highly robust to changes in the environment.

Key Personnel

M. Bernadine Dias

Back <<