Efficiently characterizing non-redundant constraints in large real world qualitative spatial networks
- Publication Type:
- Conference Proceeding
- Citation:
- IJCAI International Joint Conference on Artificial Intelligence, 2015, 2015-January pp. 3229 - 3235
- Issue Date:
- 2015-01-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. We focus on efficiently characterizing non-redundant constraints in large real world RCC8 networks and obtaining their prime networks. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. We make use of a particular partial consistency, namely, G⋄-consistency, and obtain new complexity results for various cases of RCC8 networks, while we also show that given a maximal distributive subclass for RCC8 and a network N defined on that subclass, the prunning capacity of G⋄-consistency and ⋄-consistency is identical on the common edges of G and the complete graph of N, when G is a triangulation of the constraint graph of N. Finally, we devise an algorithm based on G⋄-consistency to compute the unique prime network of a RCC8 network, and show that it significantly progresses the state-of-the-art for practical reasoning with real RCC8 networks scaling up to millions of nodes.
Please use this identifier to cite or link to this item: