Skip to main content

Consistency of Chordal RCC-8 Networks

We consider chordal RCC-8 networks and show that we can check their consistency by enforcing partial path consistency
with weak composition. We prove this by using the fact that RCC-8 networks with relations from the maximal tractable subsets ^H8; C8; and Q8 of RCC-8 have the patchwork property. The use of partial path consistency has important practical consequences that we demonstrate with the implementation of the new reasoner PyRCC85, which is developed by extending the state of the art reasoner PyRCC8. Given an RCC-8 network with only tractable RCC-8 relations, we show that it can be solved very efficiently with PyRCC85 by making its underlying constraint graph chordal and running path consistency on this sparse graph instead of the completion of the given network. In the same way, partial path consistency can be used as the consistency checking step in backtracking algorithms for networks with arbitrary RCC-8 relations resulting in very improved pruning for sparse networks while incurring a penalty for dense networks.
Citation
M. Sioutis, M. Koubarakis, "Consistency of Chordal RCC-8 Networks ", In the 24th IEEE International Conference on Tools with Artificial Intelligence. Athens, Greece. November 7-9, 2012
TAGS
Access
Unknown
Published at
In the 24th IEEE International Conference on Tools with Artificial Intelligence. Athens, Greece. November 7-9
Related research area
No related research area
Related Organizations
No related organizations