Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class
✍ Scribed by Bernhard Nebel
- Book ID
- 104637216
- Publisher
- Springer US
- Year
- 1997
- Tongue
- English
- Weight
- 899 KB
- Volume
- 1
- Category
- Article
- ISSN
- 1383-7133
No coin nor oath required. For personal study only.
✦ Synopsis
While the worst-case computational properties of Allen's calculus for qualitative temporal reasoning have been analyzed quite extensively, the determination of the empirical efficiency of algorithms for solving the consistency problem in this calculus has received only little research attention. In this paper, we will demonstrate that using the ORD-Horn class in Ladkin and Reinefeld's backtracking algorithm leads to performance improvements when deciding consistency of hard instances in Allen's calculus. For this purpose, we prove that Ladkin and Reinefeld's algorithm is complete when using the ORD-Horn class, we identify phase transition regions of the reasoning problem, and compare the improvements of ORD-Hom with other heuristic methods when applied to instances in the phase transition region. Finally, we give evidence that combining search methods orthogonally can dramatically improve the performance of the backtracking algorithm.