Research Interest: Artificial Intelligence
I belong to the Artificial Inteligence Section of my Department.
My overall research interest is Automated Reasoning and the
development of efficient algorithms for it. In particular, in my work I
use the Constraint Satisfaction framework for knowledge representation
and problem solving.
Algorithms for Constraint Satisfaction Problems
The aim of my research is the development of efficient techniques
for Constraint Reasoning. Regarding computational complexity, constraint
satisfaction is an NP-complete task. Therefore, it is believed that all
algorithms for these problems will present an exponential worst-case behaviour.
In this situation and considering the practical importance of constraint
satisfaction, developing efficient average-case algorithms is of obvious
interest. One has to accept the existence of perverse problem instance
for which known algorithms are not suitable. However, as better algorithms
are developed, larger and more difficult instances will be succesfully
considered. My research goes after that goal. More specifically, I have
worked in the following lines:
Heuristics. It is well known that algorithms can be profoundly accelerated
when combined with variable and value ordering heuristics. However, little
is known about the reasons of it. I'm very interested on both, the development
of new variable and value ordering heuristics, and the understanding of
why some heuristics perform well and some others do not.
Symmetries. Many real problems have symmetries that can be exploited to
simplify the search space. I'm interested on detecting generic types of
symmetries and devising techniques to take profit of them.
Valued Constraints. When casting real problems as CSPs one often encounters
that the classic CSP framework is too strict because all constraints are
treated alike. In real situations it often happens that some constraints
are mandatory (hard), while some others are just desirable (soft).
In that situation the task is to find a solution respecting all hard constraints
and best respecting soft constraints. This problems are usually called
Valued
CSPs. I'm also interested on the development of suitable algorithms for
this type of problems.
External Collaborations:
With Rina Dechter and Kalev Kask (University of California at Irvine,
UCI) on dynamic programming methods for exact and approximate combinatorial
optimization problems.
With Pedro Meseguer (Institut d'investigacions en Intelligencia Artificial,
IIIA/CSIC) on almost everything I have worked on.
With Thomas Schiex (Institut National de la Recherche Agronomique,
INRA) and Gerard Verfaillie (Office National d'Etudes et de Recherches
Aeroespatiales, ONERA-CERT), on algorithms for the Maximal Constraint
Satisfaction Problem
With Christian Bessiere (Laboratoire d'Informatique, de Robotique
et de Micro-electronique de Montpellier, LIRMM) on heuristics and algorithms
for Constraint Satisfaction Problems