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

被引：1

作者：

Fargier, Helene ^{[1
]}

Maris, Frederic ^{[1
]}

Roger, Vincent ^{[1
]}

机构：

[1] Univ Toulouse, IRIT, Toulouse, France

来源：

2015 IEEE 27TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI 2015) | 2015年

关键词：

Temporal Constraint Satisfaction Problems; Difference Decision Diagrams; Knowledge Compilation; Computational Complexity; KNOWLEDGE COMPILATION;

D O I：

10.1109/ICTAI.2015.71

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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.

引用

页码：429 / 436

页数：8

共 12 条

[1] Consistency restoration and explanations in dynamic CSPs-Application to configuration [J].