DisChoco: A platform for distributed constraint programming

DisChoco project

The DisChoco project has been proposed by M. Christian BESSIERE and supported by the Maroc-France PAI project no. MA/05/127.
Author: Redouane EZZAHIR PhD student in University of Mohammed V.
Collaborators: El Houssine Bouyakhf and Mustapha Belaissaoui (LIMIARFF).

DisChoco platform

DisChcoco is an open-source platform for development and experimentation in distributed constraint programming. DisChoco is a Java library implemented using the Choco solver and simple agent communication infrastructure (SACI). DisChoco can be used for simulation of a multiagents environment on a single Java virtual machine, or performed in an environment physically distributed for a realistic use. DisChoco takes into account agent with a complex local problem and lead to simulate message loss, message corruption, and message delay. The implementation of DisChoco was made to offer a modular software architecture which accepts extensions easily.

Download

Objectif of the project:

Realization of an open-source platform in which it is possible to implement and simulate as much as possible the different concerns of distributed constraint programming account :

• DisCSP and DisCOP.
• Agents with complex local problem.
• Using the already existing centralized solver (Choco).
• Message delay, message loss, and message corruption.
• Simulation use and Realistic use.
• Independent of the communication system.
• Parallel search.

The overall structure of a DisChoco agent

DisChoco provides two cases of usage: simulation and realistic use. Both use a communication system for managing message communication between agents. For the simulation use, the multi-agent system is implemented in a single Java virtual machine environment. Thus, each agent is a simple thread and the communication system is localy implemented in deal with more realistic networkmodels. The communication system is represented by MailerAMDS class. The MailerAMDS class implements ChocoCommunication interface, serves as a message relay in the system and implements an Asynchronous Message Delay Simulator [Zivan and Meisels, 2006].

Asynchronous Message delay simulator

User interface: (simulation Use)

DisChoco is based on Choco, a platform for research in centralized constraint programming and combinatorial optimization. This significant choice of design enabled us to keep the same philosophy of design as Choco and to benefit from the modules already implemented in it. We kept the same instructions notations of programming that were used in Choco.

Example of disChoco code for a simulation Use:

• DisProblem DisCSP = new DisProblem ("HelloDisChoco")


• ChocoAgent ag1 = DisCSP.makeAgent("Toto");
• ChocoAgent ag2 = DisCSP.makeAgent("Fofo");


• choco.Problem p1 = ag1.getLocalProblem();
• choco.Problem p2 = ag2.getLocalProblem();


• //use Choco instruction to define your locals problems


• List nogood = { (0,0) (0,1) ...(2,1)}


• DisCSP.post(DisCSP.infeasPairAC(ag1, X0, ag2, X1, infeasP));
• DisCSP.post(DisCSP.infeasPairAC(ag1, X1, ag2, X1, infeasP));


• DisCSP.solve();

User interface: (Realistic Use)

DisChoco can be performed in an environment physically distributed using SACI library. The system is controlled by an agent Master that extends saci agent. Each agent has a SaciCommunication entity that allows him to communicate with other agents. A Main class has been implemented in DisChoco for loading problem properties file, instantiate agent and start resolution. The figure below shows an example of Sudoku problem property file.

Example of resolution

A random binary DisCSP class is characterized by random generator with arguments:
(A, n, d, Pintra , Pconnexity , Pinter , T ) where

• A is the number of agents
• n is the number of variables
• d the domain size
• Pintra the intra-agent constraints density on each agent
• Pconnexity the connectivity density of agents graph
• Pinter the interagent constraints density on each edge
• T the constraint tightness defined as the number of forbidden value pairs on constraints.

Reference
[Zivan and Meisels, 2006] R. Zivan and A. Meisels. Message delay and discsp search algorithms. Journal paper in Ann. of Math & AI (vol. 46, pp, 415--439, April 2006