Processing disjunctions in temporal constraint networks

摘要

Temporal constraint satisfaction problems (TCSPs) provide a formal framework for representing and processing temporal knowledge. Deciding the consistency of TCSPs is known to be intractable. We demonstrate that even local consistency algorithms like path-consistency (PC) can be exponential on TCSPs 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. Our experiments on hard problems in the transition region show that LPC has the best effectiveness-efficiency tradeoff for processing TCSPs. When incorporated within backtrack search, LPC is capable of improving search performance by orders of magnitude.