= 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] == Predicates == * '''Input''': {{{node1/1, node2/1, rel/1, lc/3}}} * '''Output''': {{{label/3}}} == 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. == Example(s) == 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). }}} == Problem Peculiarities == '''Type''': Formal logic '''Competition''': System Track == Notes and Updates == == Author(s) == * Author: Jason Jingshi Li * Affiliation: Artificial Intelligence Laboratory, Swiss Federal Institute of Technology, Switzerland == References == [1] J. J. Li. Qualitative Spatial and Temporal Reasoning as Answer Set Programming. In ICTAI'12, 2012.