QUALITATIVE SPATIAL REASONING VIA 3-VALUED HETEROGENEOUS LOGIC

Konstantine Arkoudas, Selmer Bringsjord, Sangeet Khemlani

2009

Abstract

Systems for qualitative spatial reasoning (QSR) are usually formulated as relation algebras, and reasoning in such systems is performed by constraint-satisfaction techniques. While this is often adequate, it is a rather inexpressive framework that cannot model and solve many spatial reasoning problems; it can also complicate the combination of different spatial formalisms, e.g., the combination of topological with metric primitives, or absolute orientation with relative orientation. Here we suggest an alternative approach, whereby spatial information is expressed in a rich quantified 3-valued logic, equipped with a novel semantics for dealing with incomplete information. Decidability is ensured by a systematic compilation into propositional logic and the use of SAT solvers. To illustrate, we define and implement a new system for two-dimensional positional reasoning that combines Frank’s cardinal-direction calculus, the ip- op calculus for reasoning about relative orientation, and various new positional primitives. Unlike previous work, the system uses diagrams as well as symbolic formulas. In particular, the logic we introduce is heterogeneous, meaning that it combines symbolic and diagrammatic representation and inference.

Paper Citation

in Harvard Style

Bringsjord S., Arkoudas K. and Khemlani S. (2009). QUALITATIVE SPATIAL REASONING VIA 3-VALUED HETEROGENEOUS LOGIC . In Proceedings of the International Conference on Knowledge Engineering and Ontology Development - Volume 1: KEOD, (IC3K 2009) ISBN 978-989-674-012-2, pages 80-87. DOI: 10.5220/0002306200800087

in Bibtex Style

@conference{keod09,
author={Selmer Bringsjord and Konstantine Arkoudas and Sangeet Khemlani},
title={QUALITATIVE SPATIAL REASONING VIA 3-VALUED HETEROGENEOUS LOGIC},
booktitle={Proceedings of the International Conference on Knowledge Engineering and Ontology Development - Volume 1: KEOD, (IC3K 2009)},
year={2009},
pages={80-87},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002306200800087},
isbn={978-989-674-012-2},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Knowledge Engineering and Ontology Development - Volume 1: KEOD, (IC3K 2009)
TI - QUALITATIVE SPATIAL REASONING VIA 3-VALUED HETEROGENEOUS LOGIC
SN - 978-989-674-012-2
AU - Bringsjord S.
AU - Arkoudas K.
AU - Khemlani S.
PY - 2009
SP - 80
EP - 87
DO - 10.5220/0002306200800087