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