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 Asynchronous Weak-Commitment with nogood processor centralized
Author: Ionel Muscalagiu, Jose M. Vidal
Description:
This is the implementation of the Asynchronous Weak-Commitment Search with nogood processor for the graph coloring problem. We adapt the nogood processor technique from <ul>
<li>Armstrong A., Durfee E. <a href="ftp://www.eecs.umich.edu/people/durfee/IJCAI97-ad.ps.Z">
Dynamic Prioritization of Complex Agents in Distributed Constraint Satisfaction Problems.</a>. <i>In. Proceedings of the 15th IJCAI, Nagoya, Japan,</i> 620-625, 1997. >
</li>
</ul>
We solve the graph coloring problem using the AWCS algorithm (with nogood processor centralized) from
<ul>
<li>Makoto Yokoo and Katsutoshi Hirayama. <a href="http://jmvidal.cse.sc.edu/library/yokoo00a.pdf">Algorithms for Distributed Constraint Satisfaction: A Review</a>. <i>Autonomous Agents and Multi-Agent Systems,</i> 3(2):185--207, 2000. <a href="http://dx.doi.org/10.1023/A:1010078712316">doi:10.1023/A:1010078712316</a>
</li>
and
<li>Ionel Muscalagiu. <a href="">The Analysis of the Impact of the „Nogood Processor” Technique on the Efficiency of the Asynchronous Techniques.</a> <i>Sent to Nordic Journal of Computing.</i>
</li>
</ul>
<p>
When a nogood is discovered, the variable assignments causing it and the IDs of the agents involved are sent to the no-good processor, which saves the nogood. Later, when an agent has found a tentative assignment for its variables, it consults the nogood processor to make sure that its assignment along with any known assignments of higher priority agents do not constitute a nogood.
</p>