Constraint programming is a programming approach used to describe and solve large classes of problems such as searching, combinatorial, planning problems, etc. Lately, the AI community has shown increasing interest in the distributed problems that are solvable through modeling by constraints and agents. The idea of sharing various parts of the problem among agents that act independently and collaborate among themselves to find a solution by using messages proves itself useful. It was also lead to the formalized problem known as the Distributed Constraint Satisfaction Problem (DCSP) [4][5].
There are some complete asynchronous searching techniques for solving the DCSP, such as the ABT (Asynchronous Backtracking)[1][5], Asynchronous Search with Aggregations (AAS) [3] and DisDB (Distributed Dynamic Backtracking)[1] . There is also the AWCS (Asynchronous Weak-Commitment Search) [5] algorithm which records all the nogood values. The ABT algorithm has also been generalized by presenting a unifying framework, called ABT kernel [1]}. From this kernel two major techniques ABT and DisDB can be obtained.
NetLogo is a cross-platform multi-agent programmable modeling environment. NetLogo was authored by Uri Wilensky in 1999 [6] and is under continuous development at the CCL. NetLogo, is a programmable modelling environment, which can be used for simulating certain natural and social phenomena. It offers a collection of complex modelling systems, developed in time. The models could give instructions to hundreds or thousands of independent agents which could all operate in parallel. It is a medium written entirely in Java, therefore it can be installed and activated on most of the important platforms.
The aim of this site is to introduce an as general as possible model of implementation and evaluation for the asynchronous search techniques, in two possible cases: synchronous and asynchronous. In the case of the synchronous model, a synchronization of the agents' execution is done after each computing cycle. This model can be used in the study of agents behavior in several situations, like the priority order of the agents, the synchronous and asynchronous case, leading, therefore, to identifying possible enhancements of the performances of asynchronous search techniques. Implementation examples of the asynchronous techniques that use the two multi-agent system can be found on the link NetLogo Models .
P.S. If you use or refer to a model from the NetLogo Models, we ask that you cite it as follows:
[1]. C. Bessiere, I. Brito, A. Maestre, P. Meseguer, Asynchronous Backtracking without Adding Links: A New Member in the ABT Family. Artificial Intelligence, 161:7-24, 2005.
[2]. Muscalagiu, I., Jiang, H., Popa, H. E. Implementation and evaluation model for the asynchronous techniques: from a synchronously distributed system to a asynchronous distributed system. Proceedings of the 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2006), Timisoara, Romania, IEEE Computer Society Press, (2006) 209--216.
[3]. M.C. Silaghi, D. Sam-Haroud and B. Faltings. ”Asynchronous Search with Aggregations”, in Proceedings of the 17th National Conference on Artificial Intelligence- AAAI’00, Austin, Texas, 2000, pp. (917-922).
[4]. G. Solotorevsky, E. Gudes and A. Meisels. “Modeling and solving distributed constraint satisfaction problems (dcsps)”, in Proceedings of Constraint Processing-96, New Hamphshire, October 1996.
[5]. M. Yokoo, E. H. Durfee, T. Ishida, K. Kuwabara. The distributed constraint satisfaction problem: formalization and algorithms. IEEE Transactions on Knowledge and Data Engineering 10(5), page. 673-685, 1998.
[6]. U. Wilensky. “NetLogo itself”. Available: NetLogo: http://ccl.northwestern. edu/netlogo/, Center for Connected Learning and Computer-Based Modeling, Northwestern University. Evanston, IL, 1999.
[7]. J. Vidal. Fundamentals of Multiagent Systems with NetLogo Examples. Available: http://multiagent.com/p/fundamentals-of-multiagent-systems.html.