On redundant topological constraints

doi:10.1016/j.artint.2015.03.010

CSpace

	On redundant topological constraints
	Li, Sanjiang 1,2; Long, Zhiguo 1; Liu, Weiming 3; Duckham, Matt 4; Both, Alan 4
	2015-08-01
发表期刊	ARTIFICIAL INTELLIGENCE
ISSN	0004-3702
卷号	225 页码:51-76
摘要	Redundancy checking is an important task in the research of knowledge representation and reasoning. In this paper, we consider redundant qualitative constraints. For a set Gamma of qualitative constraints, we say a constraint (xRy) in Gamma is redundant if it is entailed by the rest of Gamma. A prime subnetwork of Gamma is a subset of Gamma which contains no redundant constraints and has the same solution set as Gamma. It is natural to ask how to compute such a prime subnetwork, and when it is unique. We show that this problem is in general intractable, but becomes tractable if Gamma is over a tractable subalgebra S of a qualitative calculus. Furthermore, if S is a subalgebra of the Region Connection Calculus RCC8 in which weak composition distributes over nonempty intersections, then Gamma has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from Gamma. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal and globally consistent in a "qualitative sense. A thorough empirical analysis of the prime subnetwork upon real geographical data sets demonstrates the approach is able to identify significantly more redundant constraints than previously proposed algorithms, especially in constraint networks with larger proportions of partial overlap relations. (C) 2015 Elsevier B.V. All rights reserved.
关键词	Qualitative spatial reasoning Region connection calculus Redundancy Prime subnetwork Distributive subalgebra
DOI	10.1016/j.artint.2015.03.010
语种	英语
资助项目	ARC[FT0990811] ; ARC[DP120103758] ; ARC[DP120104159] ; NSFC[61228305]
WOS研究方向	Computer Science
WOS类目	Computer Science, Artificial Intelligence
WOS记录号	WOS:000357904700003
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/20348
专题	中国科学院数学与系统科学研究院
通讯作者	Li, Sanjiang
作者单位	1.Univ Technol Sydney, Ctr Quantum Computat & Intelligent Syst, Sydney, NSW 2007, Australia 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 3.Baidu China Co Ltd, Shanghai, Peoples R China 4.Univ Melbourne, Dept Infrastruct Engn, Melbourne, Vic, Australia
推荐引用方式 GB/T 7714	Li, Sanjiang,Long, Zhiguo,Liu, Weiming,et al. On redundant topological constraints[J]. ARTIFICIAL INTELLIGENCE,2015,225:51-76.
APA	Li, Sanjiang,Long, Zhiguo,Liu, Weiming,Duckham, Matt,&Both, Alan.(2015).On redundant topological constraints.ARTIFICIAL INTELLIGENCE,225,51-76.
MLA	Li, Sanjiang,et al."On redundant topological constraints".ARTIFICIAL INTELLIGENCE 225(2015):51-76.