Asynchronous Partial Overlay

History of APO

The Asynchronous Partial Overlay (APO) algorithm is one in a class of algorithms that are based on Cooperative Mediation (CM). Conceptually, CM uses a mixture of distributed and centralized problem techniques to solve difficult distributed problems. Distributed techniques are used to identify highly interdependent portions of a shared problem, which are then centralized and solved using state-of-the-art centralized algorithms.

APO is a direct decedent of the Scalable, Periodic, Anytime Mediation (SPAM) protocol. SPAM was created to solve a real-time, resource allocation problem in a sensor network as part of the DARPA ANTS program. SPAM was designed to operate in highly communication restricted domains where the cost of communicating increased over distance. This meant that in order to operate effectively, SPAM needed to operate using only local or nearly local information (out to distance k). In its final form SPAM was a k=1 optimal protocol.

APO in Action

• Video of APO solving a 45 node, 122 edge graph coloring problem in the Farm
• Jose Vidal's Netlogo Implementation of APO

APO Publications

Mailler, Roger; and Lesser, Victor. Asynchronous Partial Overlay: A New Algorithm for Solving Distributed Constraint Satisfaction Problems. In Journal of Artificial Intelligence Research (JAIR) . To appear 2005.

Mailler, Roger. Comparing Two Approaches to Dynamic, Distributed Constraint Satisfaction. In Proceedings of Fourth International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2005), pp. 1049-1056. July, 2005.

Mailler,Roger; and Lesser,Victor. Using Cooperative Mediation to Solve Distributed Constraint Satisfaction Problems. In Proceedings of Third International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2004), pp. 446-453. July, 2004.

Mailler, Roger. Solving Distributed DCSPs using Dynamic, Partial Centralization without Explicit Constraint Passing. In Proceedings of the Second Workshop on the Challenges in the Coordination of Large Scale Multi-agent Systems (LSMAS 2005). July, 2005.

Mailler, Roger; and Lesser, Victor. A Mediation Based Protocol for Distributed Constraint Satisfaction. In The Fourth International Workshop on Distributed Constraint Reasoning, pp. 49-58. August, 2003.

Benisch, Michael; and Sadeh, Norman. Examining Distributed Constraint Satisfaction Problem (DCSP) Coordination Tradeoffs. International Conference on Automated Agents and Multi-Agent Systems (AAMAS), 2006.

Benisch, Michael; and Sadeh, Norman. Effects of Mediator Selection Strategies for Distributed Constraint Satisfaction. Workshop on Distributed Constraint Reasoning (DCR), 2005.

Download

The following is a zip file that contains the APO implementation for solving graph coloring problems in the Farm simulator. This implementation includes a fix to the original protocol that corrects an oscillation problem that was caused by the distributed locking mechanism. This implementation does not include the modification suggested by Benisch and Sadeh in the papers listed above. I think that work is excellent, but have not had an opportunity to make the changes to this code. The internal solver is quite primitive and could stand a serious upgrade. I expect that one could see a substantial boost in performance by replacing this solver with something a bit better.

This code should be easily modifiable to work with nearly any simulator. If you make these sorts of changes, I ask that you forward them to me and I will put them up on this web site.

Asynchronous Partial Overlay

The Farm simulator can be downloaded from here. I believe that the current version of APO will still compile with this version of the Farm, but as I have been out of the UMass MAS Lab for several years, I have added and modified this code, and my version of the Farm is quite a bit.