Abstract

Distributed Constraint Satisfaction (DCSP) has long been considered an important problem in multi-agent systems research. This is because many real-world problems can be represented as constraint satisfaction and these problems often present themselves in a distributed form. In this article, we present a new complete, distributed algorithm called asynchronous partial overlay (APO) for solving DCSPs that is based on a cooperative mediation process. The primary ideas behind this algorithm are that agents, when acting as a mediator, centralize small, relevant portions of the DCSP, that these centralized subproblems overlap, and that agents increase the size of their subproblems along critical paths within the DCSP as the problem solving unfolds. We present empirical evidence that shows that APO outperforms other known, complete DCSP techniques.

1. Introduction

The Distributed constraint satisfaction problem has become a very useful representation that is used to describe a number of problems in multi-agent systems including distributed resource allocation (Conry, Kuwabara, Lesser, & Meyer, 1991) and distributed scheduling (Sycara, Roth, Sadeh, & Fox, 1991). Some researchers in cooperative multi-agent systems have focused on developing methods for solving these problems that are based on one key assumption. Particularly, the agents involved in the problem solving process are autonomous. This means that the agents are only willing to exchange information that is directly relevant to the shared problem and retain the ability to refuse a solution when it obviously conflicts with some internal goal.

These researchers believe that the focus on agent autonomy precludes the use of centralization because it forces the agents to reveal all of their internal constraints and goals which may, for reasons of privacy or pure computational complexity, be impossible to achieve. Several algorithms have been developed with the explicit purpose of allowing the agents to retain their autonomy even when they are involved in a shared problem which exhibits interdependencies. Probably the best known algorithms that fit this description can be found in the work of Yokoo et al. in the form of distributed breakout (DBA) (Yokoo & Hirayama, 1996), asynchronous backtracking (ABT) (Yokoo, Durfee, Ishida, & Kuwabara, 1992), and asynchronous weak-commitment (AWC) (Yokoo & Hirayama, 2000).

Unfortunately, a common drawback to each of these algorithms is that in an effort to provide the agents which complete privacy, these algorithms prevent the agents from making informed decisions about the global effects of changing their local allocation, schedule, value, etc. For example, in AWC, agents have to try a value and wait for another agent to tell them that it will not work through a nogood message. Because of this, agents never learn true reason why another agent or set of agents is unable to accept the value, they only learn that their value in combination with other values doesn’t work.

In addition, these techniques suffer because they have complete distribution of the control. In other words, each agent makes decisions based on its incomplete and often inaccurate view of the world. The result is that this leads to unnecessary thrashing in the problem solving because the agents are trying to adapt to the behavior of the other agents, who in turn are trying to adapt to them. Pathologically, this behavior can be counter-productive to convergence of the protocol(Fernandez, Bejar, Krishnamachari, Gomes, & Selman, 2003). This iterative trial and error approach to discovering the implicit and implied constraints within the problem causes the agents to pass an exponential number of messages and actually reveals a great deal of information about the agents’ constraints and domain values (Yokoo, Suzuki, & Hirayama, 2002). In fact, in order to be complete, agents using AWC have to be willing to reveal all of their shared constraints and domain values. The key thing to note about this statement is that AWC still allows the agents to retain their autonomy even if they are forced to reveal information about the variables and constraints that form the global constraint network.

In this paper, we present a cooperative mediation based DCSP protocol, called Asynchronous Partial Overlay (APO). Cooperative mediation represents a new methodology that lies somewhere between centralized and distributed problem solving because it uses dynamically constructed, partial centralization. This allows cooperative mediation based algorithms, like APO, to utilize the speed of current state-of-the-art centralized solvers while taking advantage of opportunities for parallelism by dynamically identifying relevant problem structure.

APO works by having agents asynchronously take the role of mediator. When an agent acts as a mediator, it computes a solution to a portion of the overall problem and recommends value changes to the agents involved in the mediation session. If, as a result of its recommendations, it causes conflicts for agents outside of the session, it links with them preventing itself from repeating the mistake in future sessions.

Like AWC, APO provides the agents with a great deal of autonomy by allowing anyone of them to take over as the mediator when they notice an undesirable state in the current solution to the shared problem. Further adding to their autonomy, agents can also ignore recommendations for changing their local solution made by other agents. In a similar way to AWC, APO is both sound and complete when the agents are willing to reveal the domains and constraints of their shared variables and allows the agents to obscure the states, domains, and constraints of their strictly local variables.