Graph Coloring using APO

by Jose M Vidal

An implementation of a very simplified version of the Asynchronous Partial Overlay (APO) algorithm as presented in

Roger T. Mailler and Victor Lesser. “Using Cooperative Mediation to Solve Distributed Constraint Satisfaction Problems”. In Proceedings of the Third International Joint Conference on Autonomous Agents and MultiAgent Systems, p. 446--453, ACM. 2004.

This version uses a simplified Iterative Deepening and fails to implement other optimizations in APO. However, I believe that it captures the basic idea of the APO algorithm: do individual hill climbing and when stuck have one agent mediate. The size of the mediation session increases if the problem remains unsolved. The program correctly shows the size and number of mediation sessions.

You can download the source code: APOgc.nlogo, or go back to the list.

Created with NetLogo