Effective solution of qualitative interval constraint problems

摘要

We present a fast algorithm for solving qualitative interval constraint problems, which returns solutions of random problems in less than half a second on average, with the hardest problem taking only half a minute on a RISC workstation. This is a surprising result considering the problem is NP-complete. The fast solution time is attributed to the extraordinary pruning power of the path-consistency computation, and to the fact that all our randomly generated interval networks of size ⩾ 14 were found to be inconsistent, which is rapidly detected by a path-consistency computation.While inconsistency is relatively easy to prove, our algorithm also solves large consistent networks with 100 edges. We conclude that our algorithm suffices for solving qualitative interval constraint problems in practice. Other conclusions are that path-consistency reduces the solution search to an almost linear selection of atomic labels and that path-consistency is by itself an excellent consistency heuristic for random networks with fewer than 6 or more than 15 nodes.