Evaluating Consistency Algorithms for Temporal Metric Constraints

We study the performance of some known algorithms for solving the Simple Temporal Problem (STP) and the Temporal Constraint Satisfaction Problem (TCSP). In particular, we empirically compare the Bellman-Ford (BF) algorithm and its incremental version (incBF) by (Cesta & Oddi 1996) to the 4STP of (Xu & Choueiry 2003a). Among the tested algorithms, we show that 4STP is the most efficient for determining the consistency of an STP, and that incBF combined with the heuristics of (Xu & Choueiry 2003b) is the most efficient for solving the TCSP. We plan to improve 4STP by exploiting incrementality as in incBF and other new incremental algorithms.

Authors

• Yang Shi School of Software, Shandong University, Jinan 250101, China

Keywords

No keywords are indexed for this paper.