welcome: please sign in
location: FinalProblemDescriptions / QualitativeSpatialTemporalReasoning

Qualitative Spatial Reasoning

Problem Description

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 [1]


Input format

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.

Output format

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).
%  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).

The output of the solver should look like:

label(1,2,rPO). label(0,2,rNTPP). label(0,1,rDC).

Problem Peculiarities

Type: Formal logic Competition: System Track

Notes and Updates



[1] J. J. Li. Qualitative Spatial and Temporal Reasoning as Answer Set Programming. In ICTAI'12, 2012.

ASP Competition 2013: FinalProblemDescriptions/QualitativeSpatialTemporalReasoning (last edited 2013-03-20 18:38:30 by FrancescoCalimeri)