NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled because this model uses external files.)

Title: Graph Coloring using DisDB
Author: Ionel Muscalagiu and Jose M Vidal
Description:
We solve the graph coloring problem using the
DisDB algorithm from <ul>
<li>Christian Bessiere, Arnold Maestre, Pedro Meseguer.
<a href="http://www-sop.inria.fr/coprin/jnpc2002/actes_jnpc02/bessiere57.ps">
Distributed Dynamic Backtracking (english version).</a> or
<a href="http://www.lirmm.fr/~bessiere/stock/jnpc01-ddb.ps">
Distributed Dynamic Backtracking. </a>
In Proceedings of the CP00 Workshop on Distributed Constraint Satisfaction Problems, Singapore, Thailand, 2000.</li>
</ul>
<p>
In the constraint graph, constraints are oriented forming a directed acyclic graph, from which an agent hierarchy may be built using heuristic criteria (max-degree, for instance) following the DisAO ordering scheme [Hamadi et al., 1998]. If no heuristic is used, this hierarchy defaults to lexicographic ordering among agents. Considering a generic agent self in the hierarchy, Gama<SUP>-</SUP>(self), it the set of agents constrained with self and appearing at higher levels in the hierarchy. Conversely, Gama<SUP>+</SUP>(self) is the set of agents constrained with self appearing at lower levels in the hierarchy. This hierarchy induces a partial order among agents, which should be completed to form the total order (using for instance agents identifiers) to ensure completeness.
</p>
<p>
The DisDB algorithm is executed on each agent, keeping its own agent view and nogood store. The agent view of self is the set of values that it believes to be assigned to agents before self in the total order. The agent view is always consistent with the nogoods in the store. Agents exchange assignments and nogoods. DisDB always accepts new assignments, updating the agent view accordingly. When receiving a nogood, it is accepted if it is consistent with the agent view in Gama <SUP> -</SUP> (self) and self , otherwise it is discarded due to obsolescence. An accepted nogood is used to update the agent view of agents not in Gama<SUP>-</SUP>(self), and the set of stored nogoods. When all values of an agent are discarded by some nogood, the set of stored nogoods is resolved as in the centralised case, generating a new nogood which is sent to the variable in its right-hand side. This variable plus all variables in the left-hand side of the new nogood that are not in Gama<SUP>-</SUP>(self) are unassigned in the agent view, and nogoods are updated accordingly. The process terminates when achieving quiescence, meaning that a solution has been found, or when the empty nogood is generated, meaning that the problem is unsolvable.

</p>