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 for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

Title: Graph Coloring using ABT kernel (ABT kernel is sound but may not terminate)
Author: Ionel Muscalagiu, Jose M. Vidal
Description:
This is the implementation of the ABT kernel for the graph coloring problem. We solve the graph coloring problem using the ABT kernel algorithm from
<ul>
C. Bessiere, I. Brito, A. Maestre, P. Meseguer.
<a href="www.lirmm.fr/~bessiere/stock/aij05.pdf ">
"Asynchronous Backtracking without Adding Links: A New Member in the ABT Family"
</a>.
Artificial Intelligence, volume 161, pages 7-24.
</ul>
In this paper, it is presented a general framework for solving DCSP-s, framework which we will refer to as ABT kernel. The ABT kernel algorithm, a new ABT-based algorithm that does not require to add communication links between initially unconnected agents. The ABT kernel algorithm is sound but may not terminate (the ABT kernel may store obsolete information). We start at this procedure, which forms the basic centre or the unifying framework, we could reach the known algorithms or versions close to this ( such as Yokoo's ABT or a correct version of DIBT, DisDB).
In this centre it is considered that the agents are in a static order, based on a certain criteria. Therefore, an agent having a higher priority than other will be considered at a higher level in a tree that represents the hierarchy of the agents. If self is a generic agent, than G-(self) is the group of agents that have self constraints and that occur at higher levels in this hierarchy (called the parents group) and with G+(self) it is the group of agents that have self constraints that occur at inferior levels in hierarchy (called the children group). The agents, along with their constraints form a graph acyclic oriented, in which the constraints are oriented from the higher priority agents to lower priority agents.
Each agents needs to record certain information relative to the global state of searching. This state implies that the values affected to the higher level agents to be known (these values are called agent view) and they form the context of local work and we should also know the lists of unsatisfactory values (called nogood). The agents exchange these affected values and nogoods by, practically, searching through a simple curl that continues until a solution is found or an inconsistence is found. This mechanism is what we meet in all the asynchronous techniques.
The algorithm uses three types of messages, resembling to the ABT technique:
ˇInfo type messages, sent to children (resembling to the ok type messages), in order to inform the attribute of a new value
ˇBack type messages ( resembling to the nogood type messages), that occur in the situation of an agent not finding a consistent value (practically any value is inconsistent with the local context).
ˇStop system message