Temporal Constraint Satisfaction Problems and Difference Decision Diagrams: A Compilation Map

Hélène Fargier (1, 2) , Frédéric Maris (3) , Vincent Roger (4)

1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
2 CNRS - Centre National de la Recherche Scientifique
3 IRIT - Institut de recherche en informatique de Toulouse
4 IRIT-SAMoVA - Équipe Structuration, Analyse et MOdélisation de documents Vidéo et Audio

The frameworks dedicated to the representation of quantitative temporal constraint satisfaction problems, as rich as they are in terms of expressiveness, define difficult requests - typically NP-complete decision problems. It is therefore adventurous to use them for an online resolution. Hence the idea to compile the original problem into a form that could be easily solved. Difference Decision Diagrams (DDDs) have been proposed by [1] as a possible way to cope with this difficulty, following a compilation-based approach. In this article, we draw a compilation map that evaluates the relative capabilities of these languages (TCSP, STP, DTP and DDD) in terms of algorithmic efficiency, succinctness and expressiveness.

Mots clés: Difference decision diagrams; Temporal constraint satisfaction problems; Computational complexity; Knowledge compilation

Domaines: Intelligence artificielle [cs.AI]; Apprentissage [cs.LG]; Logique en informatique [cs.LO]; Informatique et langage [cs.CL]

Hélène Fargier, Frédéric Maris, Vincent Roger. Temporal Constraint Satisfaction Problems and Difference Decision Diagrams: A Compilation Map. 27th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2015), Nov 2015, Vietri sul Mare, Italy. pp.429-436, ⟨10.1109/ICTAI.2015.71⟩. ⟨hal-01303829⟩