Student Project Proposal:

"Search algorithms in a Distributed CSP"


Supervisors

Nicoleta Neagu
Office: INR 218
Tel: 693 66 79
Email: nicoleta.neagu@epfl.ch
Santiago Macho Gonzalez
Office: INR 210
Tel: 693 6595
Email: santi.macho@epfl.ch

Description

When multiple agents are in a shared environment, there usually exist constriants among the possible actions of these agents. A distributed constraint satisfaction problem is a problem to find a consitent combination of actions that satisfies these inter-agents constraints. A distributed CSP is a CSP in which variables and constraints are distributed among multiple automated agents. Finding a value assigment to variables that satisfies inter-agent constraints can be viewed as achieving coherence or consitency among agents. Each agent has one variable control and tries to determine its value. However, there exists inter-agent constraints, and the value assigment must satisfy these inter-agent constraints.

While there are many algorithms for searching solutions of a Distributed CSP, few of them study how a change in a known solution propagates throught the problem. For one semester work, a student will have to study and implement a distributed search algorithm which computes the variables affected by a change in a solution and how they have to change in order to stay solution.

The new solution is obtained by generating, exchanging, and maintaining appropriate coherence between variables of the distributed CSP. In order to prove the coherence, the student has to prepare a visual demo at the end of the project. Within that demo, the evolution of the state (value assigned to the corresponding variable) of each agent has to be graphically displayed.

Skills

Java language skills. The papers and documentation in english

Environment

Unix Workstation

Last modified: Wed May 1 10:24:53 MEST 2002 Webmaster