Specialized constraint reasoners

We have addressed specialized CSP representations for classes of constraints by means of quantitative temporal reasoners.

Simple Temporal Problem (STP): we have incrementally generated a series of results, which are best expressed in the following papers:

The STP (defined in [Dechter et al. 91]) is polinomial due to restrictions on expressivity. Our work is motivated by the fact that the constraint database uses these algorithms continuously, thus the efficiency of constraint network updating is very important. We have developed dynamic propagation algorithms, and formalized various properties related to minimal circuits on temporal distances in order to increase the efficiency of the solving algorithms. In particular, we have obtained relevant results with respect to constraint retraction, which is notoriously critical in the case of generic CSPs. In our work we define conditions for local propagation of the constraint network after retraction obtaining remarkable computational advantages in the average case.

Time Net Generation: we have also addressed the issue of parameter-controllable random STP generation. Our results are reported in:

Disjunctive Temporal Problem (DTP): recently we have worked on more expressive problem than the previous, which we call Disjunctive Temporal Problems. As the name says, DTPs model disjunctive relations between time variables. Maintaining updated information in these problems is exponential. We have studied CSP algorithms which guarantee the presence of at least one consistent solution. Another research community which studies DTPs is located in the University of Genoa (see ). A nice result we have obtained is reported in:

Resource reasoning: back in the period 1995-97 we have produced some pioneering work on resource constraints. We have produced a formalization of the problem which allows the representation of both renewable and consumable resources. We have shown that the problem of propagating this class of constraints is exponential because of the presence of n-ary consrraints. Among our results, we have produced a series of propagation rules (synthesizing new constraints from the current constraint data base context) which enable us to filter out inconsistent solutions. Our work is reported in:

The problem we describe in the above paper has recently been picked up by Laborie (2001), who has extended the propagation rules we had proposed and shown excellent computational results for difficult scheduling problems.

Also, our group has produced two award-winning (AI*IA best thesis award) Master Theses on the subject, by Cristiano Stella (1996) and Nicola Policella (2001).