Qualitative Spatial Reasoning
One of the most fundamental reasoning tasks in qualitative spatial and temporal reasoning is to decide whether a set of spatial and temporal constraints is consistent. Deciding consistency for qualitative constraint networks from the temporal calculus Interval Algebra and spatial calculus Region Connection Calculus is NP-hard. Given a finite set of possible spatial or temporal atomic relations, the weak-composition table of the relations from the corresponding qualitative spatial and temporal calculus, and a constraint network specifying possible relations that hold between nodes of the network, a solution to the problem is to encode an assignment of atomic relations to the labels of the network such that no constraint from the weak-composition table is violated.
This folder contains the disjunctive encoding of RCC8, which encodes RCC8 problems into ASP by specifying constraints as disjunction of possible relations. It is modified from an earlier disjunctive encoding described in 
Input: node1/1, node2/1, rel/1, lc/3
Given a set of spatial relations in RCC8 rel(L) over pairs of variables node1(X), node2(Y). lc(X,Y,L) specifies that relation L is not possible between X and Y.
A correct answer should contain a set of labels over pairs of variables in the form label(X1,Y1,L1), such that the qualitative constraint network described by these labels is consistent.
Given the input:
% Csp node1(0..2). node2(0..2). % 0 1 ( DC ) lc(0,1,rEQ). lc(0,1,rEC). lc(0,1,rPO). lc(0,1,rTPP). lc(0,1,rNTPP). lc(0,1,rTPPI). lc(0,1,rNTPPI). % 1 2 ( PO ) lc(1,2,rEQ). lc(1,2,rDC). lc(1,2,rEC). lc(1,2,rTPP). lc(1,2,rNTPP). lc(1,2,rTPPI). lc(1,2,rNTPPI).
The output of the solver should look like:
label(1,2,rPO). label(0,2,rNTPP). label(0,1,rDC).
Type: Formal logic Competition: System Track
Notes and Updates
- Author: Jason Jingshi Li
- Affiliation: Artificial Intelligence Laboratory, Swiss Federal Institute of Technology, Switzerland
 J. J. Li. Qualitative Spatial and Temporal Reasoning as Answer Set Programming. In ICTAI'12, 2012.