AAAI Publications, Sixth European Conference on Planning

Font Size: 
Constraint-Based Strategies for the Disjunctive Temporal Problem: Some New Results
Angelo Oddi

Last modified: 2014-05-21


The Disjunctive Temporal Problem (DTP) involves the satisfaction of aset of constraints represented by disjunctive formulas of the form x1 - y1 <= r1 or x2 - y2 <= r2 or ... or xk - yk <= rk. DTP is a  general temporal reasoning problem which includes the well-known Temporal Constraint Satisfaction Problem (TCSP) introduced by Dechter, Meiri and Pearl. This paper describes a basic constraint satisfaction algorithm where several aspects of the current literature are integrated, in particular the so-called incremental forward checking.  Hence,two new extended solving strategies are proposed and experimentally evaluated. The new proposed strategies are very competitive with the best results available in the current literature. In addition, the analysis of the empirical results suggests future research directions concerning in particular the use of arc-consistency filtering strategies.


temporal reasoning, constraint-based algorithms, planning, scheduling

Full Text: PDF