REPLI: Constraint-based reasoning and combinatorial optimization:
Application to planning and uncertainty managementCoordinated project: TIC2002-04470-C03
Main researchers:
Abstract:
- Hector Geffner
- Javier Larrosa
- Pedro Meseguer
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.