You are here


Constraint-based reasoning and combinatorial optimization: Application to planning and uncertainty management
Nov 2002 - Oct 2005
Main researcher
Project description
The inclusion of soft constraints in the constraint-based reasoning model has connected this model with combinatorial optimization. This allows one to have a common view of both areas, exchanging methods between them. This project tries to use, integrate and extend ideas that have been shown successful for constraint reasoning in a double dimension: Soft constraints. Contribution to the issues caused by the inclusion of soft constraints in the constraint model, extending existing results for hard constraints. In particular, we will focus on soft constraint propagation and local consistency, resolution algorithms and their complexity, and the efficient formulation of real problems. Applications. To apply constraint techniques to two different fields: planning and uncertainty management. On planning, the idea of planning as heuristic search wll be extended to produce a temporal planner of high performance, combining a branch-and-bound scheme with prunning techniques based con constraint propagation. On uncertainty management, constraint-solving algorithms based on decomposition will be applied to bayesian networks and to the possibilistic model. Finally, other problems will be studied, in particular the optimization of circuit design. Project benefits include not only the above mentioned contributions and the resolution of the applications, but also the integration of research groups with complementary backgrounds.
Research Line
Constraint Satisfaction