Student Project Proposal:


Supervisors

Nicoleta Neagu
Office: INR 218
Tel: 693 66 79
Email: nicoleta.neagu@epfl.ch

Description

In this project we propose the integration of solution update algorithms developed for constraint satisfaction problems (CSPs) as adaptation methods in case based reasoning (CBR) systems.
We consider the restricted domain of problems which can be formulated as CSPs, and propose a general method for the adaptation process of the CBR system. This method is based on constraint solving and interchangeability concept.

We developed solution update algorithms for CSPs based on the interchangeability concept. They can compute the minimal and minimum set of variables changing in a CSP solution when the value of one variable of the CSP is changing. The method is able to determine how change propagates in a solution set and generate a minimal/minimum set of choices which need to be changed to adapt an existing solution to a new problem.

The reliance on past experience that is such an integral part of human problem solving has motivated the use of CBR techniques. A CBR system stores its past problem solving episodes as cases which later can be retrieved and used to help solve a new problem. CBR is based on two observations about the nature of the world: that the world is regular, and therefore similar problems have similar solutions, and that the types of problems encountered tend to recur.
Case-Based Reasoning techniques solve problems by reusing, adapting and combining earlier solutions. CBR based reasoners are able to learn simply by storing cases. The project deals with a CBR system for resource allocation. The resource allocation problems will be represented as CSPs. Each case of the CBR system will be represented as a CSP solution which need to be adapted to the new resource requirements.

The project propose to integrate the interchangeability algorithms in the adaptation process of a CBR system and to develop an application for a resource allocation problem.

Skills

Java language

Environment

Unix

Last modified: Fri May 17 18:42:47 MEST 2002 Webmaster