Here, there, but not everywhere: An extended framework for qualitative constraint satisfaction

Liu, W; Li, S

Here, there, but not everywhere: An extended framework for qualitative constraint satisfaction

Liu, W Li, S

Permalink

Publication Type:: Conference Proceeding
Citation:: Frontiers in Artificial Intelligence and Applications, 2012, 242 pp. 552 - 557
Issue Date:: 2012-01-01

Closed Access

	Filename	Description	Size
	2011006784OK.pdf		1.34 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Liu, W	en_US
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.date.issued	2012-01-01	en_US
dc.identifier.citation	Frontiers in Artificial Intelligence and Applications, 2012, 242 pp. 552 - 557	en_US
dc.identifier.isbn	9781614990970	en_US
dc.identifier.issn	0922-6389	en_US
dc.identifier.uri	http://hdl.handle.net/10453/22276
dc.description.abstract	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. © 2012 The Author(s).	en_US
dc.relation.ispartof	Frontiers in Artificial Intelligence and Applications	en_US
dc.relation.isbasedon	10.3233/978-1-61499-098-7-552	en_US
dc.title	Here, there, but not everywhere: An extended framework for qualitative constraint satisfaction	en_US
dc.type	Conference Proceeding
utslib.citation.volume	242	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
dc.location.activity	Montpellier, France	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	closed_access
pubs.publication-status	Published	en_US
pubs.volume	242	en_US

Abstract:

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. © 2012 The Author(s).

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

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