Here, There, but Not Everywhere: An Extended Framework for Qualitative Constraint Satisfaction

IOS Press
Publication Type:
Conference Proceeding
Proceedings of the 20th European conference on artificial intelligence (ECAI-2012), 2012, pp. 552 - 557
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2011006784OK.pdf1.34 MB
Adobe PDF
Dealing with spatial and temporal knowledge is an indispensable part of almost all aspects of human activities. The qualitative approach to spatial and temporal reasoning (QSTR) provides a promising framework for spatial and temporal knowledge representation and reasoning. QSTR typically represents spatial/temporal knowledge in terms of qualitative relations (e.g., to the east of, after), and reasons with the knowledge by solving qualitative constraints. When formulating a qualitative constraint satisfaction problem (CSP), it is usually assumed that each variable could be âhere, there and everywhere2.â Practical applications e.g. urban planning, however, often require a variable taking values from a certain finite subset of the universe, i.e. require it to be âhere or thereâ. This paper extends the classic framework of qualitative constraint satisfaction by allowing variables taking values from finite domains. The computational complexity of this extended consistency problem is examined for five most important qualitative calculi, viz. Point Algebra, Interval Algebra, Cardinal Relation Algebra, RCC-5, and RCC-8. We show that the extended consistency problem remains in NP, but when only basic constraints are considered, the extended consistency problem for each calculus except Point Algebra is already NP-hard.
Please use this identifier to cite or link to this item: