Student Project Proposal:

"Interchangeability algorithms for Soft 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

Soft constraint add to the classical notion of constraint the possibility of dealing with important features like fuzziness, uncertainty, optimization, probability and partial satisfaction.

Classical constraint satisfaction problems (CSPs) are a very expressive and natural formalism to specify many kinds of real-life problems like scheduling, planning, problems ranging from map coloring, vision, robotics etc. However, they also have evident limitations, mainly due to the fact that thay do not appear to be very flexible when trying to represent real-life scenarious where the knowledge is not completely available nor crisp. In fact, in such situations, the ability of stating whether an instantiation of values to variables is allowed or not is not enough or sometimes not even possible.

In this project we will study and implement interchangeability algorithms over Soft CSPs. Interchangeability characterizes the possibility of exchanging one value for another in a CSP solution and obtaining another consitent solution as a result.

The project consits in implementation of interchangeability algorithms for soft CSP and a visual demo ( a java applet) at the end of the project. Within that demo, the evolution of the state of each variable has to be graphically displayed.

Skills

Java language skills. The papers and documentation in english

Environment

Unix Workstation

Last modified: Wed May 1 10:26:49 MEST 2002 Webmaster