Optimal Asynchronous Partial Overlay

History of OptAPO

The Optimal Asynchronous Partial Overlay (OptAPO) algorithm is an optimization version of the APO algorithm. Like APO, OptAPO 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.

OptAPO is a direct decedent of the APO protocol and shares many common features with it. However, due to the nature of optimization, OptAPO has some characteristic differences. One of the primary differences is in the determination of when an agent elects to mediate. In APO, it was enough to have an agent only want to mediate when its variable was involved in an unsatisified constraint. However, in optimization, there are instances where having a violated (or less than optimal constraint value) is acceptable. In OptAPO mediators decide to mediate when they determine they have a sub-optimal subproblem. In almost all cases, this leads to an optimal solution, but while writing the proof, I discovered a simple counter example where the agents could terminate in a sub-optimal condition. (See below)

An optimal solution to a two coloring problem.
A non-optimal solution that could be derived if ND4 and ND5 have a sub-problem of (ND2, ND3, ND4, ND5, and ND6) and ND1 and ND7 have a sub-problem of (ND0, ND1, ND2, ND6, ND7). All other agents never extended their views past their immediate neighbors.

I quickly realized that the problem stemmed from the fact that satisfaction problem have the idempotency property (if all sub-problems are satisfied then global problem is satisfied) and that optimization did not. In other words, you can have optimal sub-problems and not have an optimal global solution.

To counter this rather significiant inconvience, a second termination condition was added to the algorithm. Namely, ther agents cannot terminate until they sure that the sub-optimalities are being placed on the correct constraints. Another way of saying this is to say that if an agent owns a variable that is part of a justification for a sub-optimal condition then it too need to agree that the sub-optimality is positioned within the correct constraint. Looking at the diagrams above, it is easy to see that if ND2 and/or ND1 had extended their view past their immediate neighbors then they would have found out that their variable should have had it constaint violated in order to solve two sub-systems.

OptAPO Publications

Mailler, Roger; and Lesser, Victor. Solving Distributed Constraint Optimization Problems Using Cooperative Mediation. In Proceedings of Third International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2004), pp. 438-445. July, 2004.

Oliveira, D. and Bazzan, A. L. C. and Lesser, V. Using Cooperative Mediation to Coordinate Traffic Lights: a Case Study. In Proceedings of Fourth International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2005). 2005.

Davin, John; and Modi, Pragnesh Jay. Impact of Problem Centralization in Distributed Constraint Optimization Algorithms. In Proceedings of Fourth International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2005). 2005.

Petcu, Adrian; Faltings, Boi; and Mailler, Roger. PC-DPOP: A New Partial Centralization Algorithm for Distributed Constraint Optimization. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Jan 2007.

Download

The following is a zip file that contains the OptAPO implementation for solving constraint optimization 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. 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.

Optimal Asynchronous Partial Overlay

The Farm simulator can be downloaded from here. I believe that the current version of OptAPO 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.

Last revised: 04/13/07