A Decomposition Framework for Inconsistency Handling in Qualitative Spatial and Temporal Reasoning

Decomposition can be a fundamental process for dealing with

inconsistency in different domains. Among other things, it

allows us to capture potential contexts, identify conflicting

factors, restore consistency, and measure inconsistency. The

aim of this paper is to explore the process of decomposition

in qualitative spatial and temporal reasoning. We first study

a problem that consists in decomposing the original

inconsistent constraint network into the fewest possible

consistent subnetworks (components) that share a given part.

After establishing several interesting theoretical properties,

such as providing bounds on the number of components in a

decomposition, as well as computational complexity results, we

propose two methods for solving this problem. The first method

is based on a SAT encoding, while the second one corresponds to

a greedy constraint-based algorithm, a variant of which involves

the use of spanning trees to reduce the number of oracle calls.

Secondly, we consider a version of the previous decomposition

problem by focusing on maximizing the similarity between the

decomposition components; the similarity in this context is

represented by the common constraints among components. We then

adapt our methods to solve this new problem. Thirdly, we propose

two inconsistency measures that are based on our decomposition

framework and show that they satisfy several desired properties.

Finally, we provide implementations of our decomposition methods

and perform an experimental evaluation.