Backtracking Algorithms for Disjunctions of Temporal Constraints

Weextendthe framework of simple temporalproblems studied originally by Dechter, MeiriandPearl to consider constraints of the formxl - yl 1. Wehave implemented four progressively moreefficient algorithmsfor the consistencychecking problemfor this class of temporalconstraints. We havepartially orderedthose algorithmsaccordingto the number of visited search nodesand the number of performedconsistencychecks. Finally, wehavecarried out a series of experiments onthe location of the hard region. Theresults showthat hard problemsoccur at a critical valueof the ratio of disjunctionsto variables. Thisvalue is between 6 and7.

Authors

• Kostas Stergiou

Keywords

No keywords are indexed for this paper.