Information Technology Reference
In-Depth Information
Definition 2.
A
cmRCD-network
is an integrated qualitative and metric constraint net-
work
N
consisting of three sub-networks
(
N
c
,
S
x
,
S
y
)
,where
N
c
=(
V,C
)
is a convex
S
x
=
P
(
V
x
)
,M
x
and
S
y
=
P
(
V
y
)
,M
y
are two STPs.
RCD-network, and
cmRCD
Require:
a cmRCD-network
N
=(
N
c
, S
x
, S
y
)
1:
N
r
← toRA
(
N
c
)
;
2:
N
x
← π
x
(
N
r
)
,
N
y
← π
y
(
N
r
)
;
3:
N
x
con
Algorithm 4.1.
The algorithm
-
← toPA
(
N
x
)
,
N
y
← toPA
(
N
y
)
;
intersect
(
toSTP
(
N
x
)
,S
x
)
;
5:
ySTP ← intersect
(
toSTP
(
N
y
)
, S
y
)
;
6: if
xSTP
or
ySTP
is empty, then return 'inconsistent';
7:
xSTP
min
4:
xSTP
←
← PC
stp
(
xSTP
)
;
8:
ySTP
min
← PC
stp
(
ySTP
)
;
9: If
xSTP
min
or
ySTP
min
is empty, then return 'inconsistent'; otherwise, return 'consis-
tent'.
The cmRCD-calculus subsumes both the convex RCD-calculus and the STP formalism.
Moreover, it generalizes the convex fragment of the RA, since convex RA-relations are
expressible as convex PA-relations, which can be encoded into an STP.
In the following, we describe an algorithm, called
con
-
cmRCD
, to solve the con-
sistency problem for cmRCD-networks, that runs in
O
(
n
3
)
. As a matter of fact, a sim-
ilar combination of qualitative and quantitative networks is provided by preconvex-
augmented rectangle networks. An
O
(
n
5
)
algorithm for checking the consistency of
these networks, that subsume
cmRCD-networks
, is given in [6]. We exploit the trade-off
between expressiveness and complexity to obtain a more efficient consistency checking
algorithm for
cmRCD-networks
.
As a preliminary step, we extend the translation mapping
toSTP
of Table 1 to en-
code a convex PA-network
N
P
into an STP
S
by replacing each relation
R
in the
network
N
P
by
toSTP
(
R
)
.First,
con
-
cmRCD
applies the mapping
toRA
to the in-
put convex RCD-network
N
c
to get the corresponding convex RA-network
N
r
. Then,
it computes the projections
N
x
and
N
y
of
N
r
. Next, it applies the mapping
toPA
to
translate the convex IA-networks
N
x
and
N
y
into two equivalent PA-networks
N
x
and
N
y
with convex relations between points variables representing the projections
of the intervals in
N
x
and
N
y
. Thereafter, making use of such an encoding of con-
vex RCD-relations as PA-relations, it looks for possible inconsistencies between these
constraints and the STP-constraints on the same variables given in
S
x
and
S
y
that can
be detected at this stage. To this end, it translates the PA-network
N
x
(resp.,
N
y
)
into an STP-network by applying the extended function
toSTP
, and then it uses the
function
intersect
to compute the “intersection” between
toSTP
(
N
x
)
and
S
x
(resp.,
toSTP
(
N
y
)
and
S
y
). This function simply intersects the constraints associated with
the same pairs of variables in the two STPs. If an interval intersection produces an empty
interval, then
intersect
returns an empty network, and we can conclude that
N
is incon-
sistent. Otherwise, we apply the path-consistency algorithm to the two STPs computed
at lines 4 and 5 independently. The following theorem proves that
con
-
cmRCD
is
sound and complete.
