Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class

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-Horn 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.     

RCC5与主方位关系结合的定性空间推理

解决实际问题需要将多方面空间信息结合进行推理,仅考虑单方面空间信息是不够的.多方面空间信息结合推理已成为定性空间推理的一个研究热点.现有拓扑与方位结合推理工作主要集中在与基于最小外包矩形或单片方位模型的结合.方位信息描述是近似的,不适于精确推理;因此分别采用主方位模型和RCC5描述方位、拓扑信息.根据定义给出基本RCC5和主方位关系间的相互依赖及异质复合表;讨论了其上约束满足问题,得到一个路径相容算法,并分析了推理复性问题.