ECAI-2000 Logo

ECAI-2000 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Incremental Forward Checking for the Disjunctive Temporal Problem

Angelo Oddi, Amedeo Cesta

This paper studies algorithms for the Disjunctive Temporal Problem (DTP) a quite general temporal reasoning problem introduced in \cite{stergiou-koubarakis-98}. This problem involves the satisfaction of a set of constraints represented by disjunctive formulas of the form $x_1 -y_1 \leq r_1 \vee x_2 -y_2 \leq r_2 \vee \dots \vee x_k -y_k \leq r_k$. The paper starts sketching why DTPs are potentially very useful in plan management applications, then analyzes the current solutions to DTP, and introduces a constraint-satisfaction problem solving algorithm where different aspects of current DTP's literature are integrated. This basic algorithm is then improved exploiting the quantitative temporal information in the ``distance graph''. Using this knowledge an incremental version of the forward checking is obtained and shown to be competitive with current best results. The whole approach allows to understand pros and cons of the current algorithms for the DTP and suggests further future developments as discussed in the final part of the paper.

Keywords: temporal reasoning, constraint satisfaction, planning

Citation: Angelo Oddi, Amedeo Cesta: Incremental Forward Checking for the Disjunctive Temporal Problem. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.108-112.

[prev] [tofc] [next]

ECAI-2000 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Humboldt University on behalf of Gesellschaft für Informatik.