Solving qualitative constraints involving landmarks

Liu, W; Wang, S; Li, S; Liu, D

Solving qualitative constraints involving landmarks

Liu, W Wang, S Li, S

Liu, D

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2011, 6876 LNCS pp. 523 - 537
Issue Date:: 2011-09-26

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download full textAdobe PDF (626.56 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Liu, W	en_US
dc.contributor.author	Wang, S	en_US
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.contributor.author	Liu, D	en_US
dc.date.issued	2011-09-26	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2011, 6876 LNCS pp. 523 - 537	en_US
dc.identifier.isbn	9783642237850	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/19096
dc.description.abstract	Consistency checking plays a central role in qualitative spatial and temporal reasoning. Given a set of variables V, and a set of constraints Γ taken from a qualitative calculus (e.g. the Interval Algebra (IA) or RCC-8), the aim is to decide if Γ is consistent. The consistency problem has been investigated extensively in the literature. Practical applications e.g. urban planning often impose, in addition to those between undetermined entities (variables), constraints between determined entities (constants or landmarks) and variables. This paper introduces this as a new class of qualitative constraint satisfaction problems, and investigates the new consistency problem in several well-known qualitative calculi, e.g. IA, RCC-5, and RCC-8. We show that the usual local consistency checking algorithm works for IA but fails in RCC-5 and RCC-8. We further show that, if the landmarks are represented by polygons, then the new consistency problem of RCC-5 is tractable but that of RCC-8 is NP-complete. © 2011 Springer-Verlag.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-642-23786-7_40	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Solving qualitative constraints involving landmarks	en_US
dc.type	Conference Proceeding
utslib.citation.volume	6876 LNCS	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
dc.location.activity	Perugia, Italy	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US
pubs.volume	6876 LNCS	en_US

Abstract:

Consistency checking plays a central role in qualitative spatial and temporal reasoning. Given a set of variables V, and a set of constraints Γ taken from a qualitative calculus (e.g. the Interval Algebra (IA) or RCC-8), the aim is to decide if Γ is consistent. The consistency problem has been investigated extensively in the literature. Practical applications e.g. urban planning often impose, in addition to those between undetermined entities (variables), constraints between determined entities (constants or landmarks) and variables. This paper introduces this as a new class of qualitative constraint satisfaction problems, and investigates the new consistency problem in several well-known qualitative calculi, e.g. IA, RCC-5, and RCC-8. We show that the usual local consistency checking algorithm works for IA but fails in RCC-5 and RCC-8. We further show that, if the landmarks are represented by polygons, then the new consistency problem of RCC-5 is tractable but that of RCC-8 is NP-complete. © 2011 Springer-Verlag.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/19096