|
Size: 2805
Comment: Example added
|
← Revision 3 as of 2013-03-20 18:38:30 ⇥
Size: 2458
Comment: fix description of Qualitative Spatial Reasoning
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 20: | Line 20: |
| 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. The answer set contains a set of labels over pairs of variables in the form of {{{label(X1,Y1,L1)}}}, such that the qualitative constraint network described by these labels is consistent. | 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. |
| Line 24: | Line 24: |
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. |
|
| Line 44: | Line 46: |
| 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). 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). rel(rEQ). rel(rDC). rel(rEC). rel(rPO). rel(rTPP). rel(rNTPP). rel(rTPPI). rel(rNTPPI). node1(0). node1(1). node1(2). node2(0). node2(1). node2(2). label(1,2,rPO). label(0,2,rNTPP). label(0,1,rDC). |
label(1,2,rPO). label(0,2,rNTPP). label(0,1,rDC). |
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.