SFB/TR8 - Project R3   - Project R3-[Q-Shape]
 





Complexity of constraint-based reasoning algorithms for ternary calculi

Introduction

Qualitative knowledge about relative distance and orientation can be expressed in form of ternary point relations. Results by Scivos and Nebel showed that Freksa's Double Cross calculus is $NP$-hard [SN01].

The calculus we will use for our investigations, the Ternary Point Configuration Calculus (TPCC) [MNF03], is derived from the Double Cross calculus [Fre92] and is developed under the premises being suitable for robot navigation human machine interaction.

We investigate the question whether ternary point configuration calculi are useful for polynomial but incomplete reasoning. Therefore we investigate properties and complexity issues of several algorithms calculating fix points within TPCC constraint systems.

A prerequisite to using the standard constraint algorithms, especially the Ladkin and Reinefeld's algorithm [LR92] extended for ternary relations [IC00], is to express the calculi in terms of relation algebras in the sense of Tarski [LM94]. But since the TPCC-Calculus is not closed under the transformations and under the composition we can not use this scheme.

However, simple path-based inferences can be performed using the following scheme. The two last relations of a path are composed. Then the reference system is incrementally moved towards the beginning of the path in form of a backward chaining. [Link zu Aibo Example aus Paper geben] Here we will look at four different algorithms calculating a fix point for a given constraint system with ternary relations with more general methods. The result is some sort of hyper-arc-consistency.

In the following we denote the set of objects involved with $O$ and we define a triple of objects $x,y,z \in O$ as $<x,y,z>$. In the following we may refer to a triple as well as node or point configuration. We name the set of all possible valid triples $V_n^{(3)}$ with $n$ objects given. Thus the number of valid nodes is $\vert V_n^{(3)}\vert=3!\left(\begin{array}{c}n 3 \end{array}\right) < n^3$. For each triple we have a number of $a = \vert Rel_{TPCC}\vert$ possible relations, what is the number of base relations of the TPCC calculus. The constraints for a single configuration are summarized in $C_{<X,Y,Z>} = \{ rel \vert rel \in Rel_{TPCC} \land rel(<X,Y,Z>)=true \} $ and the union of all constraints over all nodes is named $C$. The rules given by the TPCC for transformation are refered as $Rule_{Unary}$ and for composition as $Rule_{Binary}$.

Algorithm 1 is a naive implementation like the one proposed by Montanari [Mon74], Algorithm 2 is similar to the first one, but with recursive precalculations of depth two on all initially given constraints. Method 3 shows an extended version following Mackworth [Mac77], listing all changes in a $queue$, and Algorithm 4 is a method propagating all effects of the initially given constraints and the emerging changes recursively.

Algorithm 1 – Naive fix point calculation

alg1

The naive implementation (Alg. 1) checks all combinations of triples whether they have a composition and calculating the emerging changes on the dependant relations. This loop is iterated until a fix point is reached. With the approximation of $\vert V_n^{(3)}\vert \leq n^3$ we have $O(n^6c)$ for the inner loop, with $c$ denoting the costs for calculating the composition of two configurations. With $c = a^2$ follows $O(n^6a^2)$. Following [Mon74] the outer loop is executed maximal linear in the number of nodes times the maximum domain size. This results in $O( n^3a )$. Thus an overall complexity of $O(n^9a^3 )$ follows.



Algorithm 2 – Recursive Propagation with bounded depth

alg2

In the case of Algorithm 2 the recursive propagation of all initially given constraints with depth two takes $O(n^4ca^2+2n^5c^2) = O(n^4a^4 + 2n^5a^4)$. The loop for propagating the changes with depth one is executed $n^3a$ times in the worst case. The propagation itself takes $O(2n^7c)=O(2n^7a^2)$. This results in a worst case complexity of $O(n^{10}a^3)$. This is worse than Algorithm 1, but in the average the loop is called only a few times ($\leq n$), which leads to $O(n^8a^3)$.

Algorithm 3 – AC-3/PC-2 like algorithm

alg3

Algorithm 3 is modified in the sense of Mackworth listing all changes occurring within a loop and revising only these in the next loop. A first investigation resulted in a complexity of $O(enca) = O(n^7a^3)$ [DM04]. Having a closer look at subprogram checkUnaryRules revealed a lower complexity of $O(n^4)$ [MR05]. The subprogram returns TRUE, if by using the transformation tables, a constraint is replaced by a stricter one.. Analogically, the subprogram checkBinaryRules returns TRUE, if by using the composition table a constraint is replaced by a stricter constraint. The variable $changed$ is true if and only if for one node at least one base relation has been excluded. If this happens, the $queue'$ has been extended by a new element. For that reason, we have in the worst case no more than $n^3\vert Rel_{TPCC}\vert$ nodes in the $queue$ (for each $C_{\langle x_i,y_i,z_i \rangle}$ with ${\langle x_i,y_i,z_i \rangle} \in queue$). In the iteration of the loop each element leads to $n$ calls of $checkBinaryRules$. Therefore the complexity of this algorithm is $O(n^4)$.

Algorithm 4 – Recursive propagation

alg4

The recursive algorithm (Alg. 4) propagates all changes originating in the initially given constraints ($\leq k*n$ with a constant $k$). The maximum depth is bounded in the number of nodes $V_n^{(3)} < n^3 $. Executing the function $propagateChange(.)$ with depth one takes $O(a^2 + 2nc)$. The recursive call with depth $>$ 1 leads to $2nc$ calls of $propagateChange(.)$ plus an additional overhead of $O(a^2)$. This can be summarized with $(2nc)^d + a^2\sum_{d=1}^{n^3} (2nc)^{(d-1)}$ resulting in a term exponential in the maximum number of nodes, what is $d = n^3$.

Copyright © 2005 - 2012 by R3 - SFB/TR 8

webmaster     disclaimer