A Decomposition-based Approach to Checking the Satisfiability of Temporal Database Query in Temporal Planning
Ho-Jin Choi, Barry Richards · Journal of Electrical Engineering and Information Science · 1999
This paper presents a method for increasing the efficiency of checking the satisfiability of a structure known as a temporal database query(TDBQ), which is an essential component of temporal planning. We develop a new qualitative strategy for decomposing a TDBQ into nearly-independent sub-TDBQ's, whose satisfiability can be checked separately; if all sub-TDBQ's are satisfiable, we use an efficient method of testing for global consistency. To ensure the correctness of the procedure we must impose certain restrictions on the temporal constraints used in specifying planning problems and action operators. But these do not present an awkward restriction on expressiveness. They do, however, lead to a significant reduction in the propagation of constraints and thus greatly enhance the performance of the temporal reasoning system.