Gaining Efficiency and Flexibility in the Simple Temporal Problem

A. Cesta and A. Oddi

In L. Chittaro, S. Goodwin, H. Hamilton, A.Montanari, Proceedings of the Third International Workshop on Temporal Representation and Reasoning (TIME-96), KeyWest, FL, May 19-20, 1996, IEEE Computer Society Press: Los Alamitos, CA, 1996

The paper deals with the problem of managing quantitative temporal networks without disjunctive constraints. The problem is known as Simple Temporal Problem. Dynamic management algorithms are considered to be coupled with incremental constraint posting approaches for planning and scheduling. A basic algorithm for incremental propagation of a new time constraint is presented that is a modification of the Bellman-Ford algorithm for Single Source Shortest Path Problem. For this algorithm a sufficient condition for inconsistency is given based on cycle detection in the shortest paths graph. Moreover, the problem of constraint retraction from a consistent situation is considered and properties for repropagating the network locally are exploited. Some experiments are also presented that show the usefulness of the properties.