基于结合空间拓扑和方向关系信息的空间推理

Spatial Reasoning Combining Topological and Cardinal Directional Relation Information

摘要: 结合了定性空间推理中著名的区域连接演算(region connection calculus, RCC)和基于区域的方向关系演算(cardinal direction calculus, CDC)，并且给出两个演算在两个方向上的交互表，即RCC8-To-CDC 和CDC-To-RCC8.给出了结合RCC8和CDC知识的约束满足问题的路径一致算法(path consistency algorithm)(该算法是对Allen著名的路径一致算法的修改)，并且采用两个队列实现了该算法，采用这种结构可以实现并行计算.在该算法中，基于以上两个交互表的交互操作被嵌入到算法里面来保证整个约束满足问题的一致性.算法的计算复杂性证明是多项式的.

Abstract: RCC8 calculus (RCC8) and cardinal direction calculus (CDC) based on regions in qualitative spatial reasoning are combined and the interaction tables for the two calculi in two directions, i.e. RCC8-To-CDC and CDC-To-RCC8, are presented. The path consistency algorithm for constraint satisfaction problems combining RCC8 and CDC knowledge is proposed, which is the adaptation of Allen's famous algorithm. The path consistency algorithm is implemented using two queues, which can be operated in parallel. In this algorithm, the interaction operation based on the interaction tables is embedded into it to enforce the whole consistency for the CSPs combining RCC8 and CDC knowledge. The computational complexity of this algorithm is polynomial.