Consistency of Chordal RCC-8 Networks
Authors: 
M. Sioutis
Authors: 
M. Koubarakis
Date published: 
2012
Published In: 
In the 24th IEEE International Conference on Tools with Artificial Intelligence. Athens, Greece. November 7-9
Type: 
Conference Article
Abstract: 
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.
Related files: 
application/pdf iconieee2012.pdf 476.55 KB

MaDgIK 2009-2016