时空推理中自动生成复合表的通用算法

时空推理是面向时间/空间问题的研究领域,在人工智能(如语义Web、机器人导航、自然语言处理、物理过程的定性模拟和常识推理等)和其他领域有着广泛的应用前景.复合推理在时空推理中具有重要作用,是约束满足问题等其他定性推理的基础.复合推理是由R(a,b)和R(b,c)决定R(a,c)的一种演绎推理.一般将关系复合结果放在复合表中备查.但目前复合表的建立需要逐个模型进行手工推导,少数模型给出了独立的复合表生成算法,没有适合多种时空关系模型、能自动生成复合表的通用算法.为此,提出了一种能自动生成复合表的通用算法.首先,给出了基于空间划分的通用时空表示模型.在此基础上,提出了基于场景检测的通用复合表生成算法.通过理论分析和对RCC、宽边界、区间代数等20余种典型时空模型的测试,证明了本算法对于所有以精确区域(或区间)为基础的确定、不确定时空模型均能正确快速地生成复合表.

A General Algorithm for Automatically Generating Composition Table in Spatio-Temporal Reasoning

Spatio-temporal reasoning(STR),the research field aiming at spatial and?or temporal questions,has a wide variety of potential applications in artificial intelligence(such as semantic Web,robot navigation,natural language processing,qualitative simulation of physical processes and common-sense reasoning) and other fields.Composition inference plays an important role in spatio-temporal reasoning,and it's the basic step of other qualitative reasoning such as constraint satisfaction problem.A compositional inference is a deduction,which decides R(a,c) from R(a,b) and R(b,c).Compositions of pairs of relations can be maintained in composition table for looking up.But composition table needs to be built one by one with manual deduction,and few models have their independent generation algorithms at this time.There is no general automatic algorithm supporting multiple models up to now.So a general algorithm for automatically generating composition table is proposed.First introduced is the general representation method of spatio-temporal relation based on space partition.Then proposed is an algorithm that can automatically generate composition table according to scene checking.Theory analysis and examinations of over 20 representative spatio-temporal models such as RCC,broad boundary,interval algebra,etc.shows that this algorithm can quickly and correctly generate composition table for all the spatio-temporal models based on precise region(or interval).