Abstract
The framework of Temporal constraint Satisfaction Problems (TCSP) has been proposed for representing and processing temporal knowledge. Deciding consistency of TCSPs is known to be intractable. As demonstrates in this paper, even local consistency algorithms like path-consistency can be exponential due to the fragmentation problem. We present two new polynomial approximation algorithms, Upper-Lower-Tightening (ULT) and Loose-Path-Consistency (LPC), which are efficient yet effective in detecting inconsistencies and reducing fragmentation. The experiments we performed on hard problems in the transition region show that LPC is the superior algorithm. When incorporated within backtrack search LPC is capable of improving performance by orders of magnitude.