Information Technology Reference
In-Depth Information
Ta b l e 1 .
Translation of convex PA-constraints to STP-constraints via the
toSTP
mapping
Convex PA relation STP constraint
p
i
<p
j
p
j
−
p
i
∈
]0
,
+
∞
[
p
i
≤ p
j
p
j
− p
i
∈
[0
,
+
∞
[
p
i
=
p
j
p
j
− p
i
∈
[0
,
0]
p
i
>p
j
p
j
− p
i
∈
]
−∞,
0[
p
i
≥ p
j
p
j
− p
i
∈
]
−∞,
0]
p
i
?
p
j
p
j
− p
i
∈
]
−∞,
+
∞
[
variables (convex IA-relations) or between the endpoints of the projections of rectan-
gle variables (convex RA-relations). It is worth to mention that a convex RA-relation
is equivalently characterized as an RA-relation which can be obtained as the Cartesian
product of two convex IA-relations. Both the consistency and the minimality problems
in the convex fragments of PA, IA, and RA can be solved in
O
(
n
3
)
,where
n
is the
number of variables of the input network.
2.4
Simple Temporal Problem
The Simple Temporal Problem (STP) formalism was introduced in [7] to process metric
information about time points. Formally, an STP is specified by a constraint network
S
=(
P,M
)
,where
P
is a set of
n
point variables, whose values range over a dense
domain (which we assume to be
), and
M
is a set of
binary metric
constraints over
P
.
A metric constraint
M
ij
=[
q,q
]
(open and semi-open intervals can be used as well),
with
q,q
∈
Q
Q
, on the distance between (the values of)
p
i
,p
j
∈
P
states that
p
j
−
p
i
∈
[
q,q
]
, or, equivalently, that
q
q
. Hence, the constraint
M
ij
defines the set
≤
p
j
−
p
i
≤
of possible values for the distance
p
j
−
p
i
. In the constraint graph associated to
S
,
M
ij
=
[
q,q
]
is represented by an edge from
p
i
to
p
j
labeled by the rational interval
[
q,q
]
.
Unary metric
constraints restricting the domain of a point variable
p
i
can be encoded
as binary constraints between
p
i
and a special starting-point variable with a fixed value,
e.g., 0. The
universal constraint
is
]
−∞
,
+
∞
[
. The operations of composition (
◦
)and
inverse (
−
1
) of metric constraints are computed by means of interval arithmetic, that
is,
[
q
1
,q
2
]
[
q
3
,q
4
]=[
q
1
+
q
3
,q
2
+
q
4
]
and
[
q
1
,q
2
]
−
1
=[
◦
−
q
2
,
−
q
1
]
. Intersection of
constraints (intervals) is defined as usual.
Assuming such an interpretation of the operations of composition, inverse, and inter-
section, in [7] Dechter et al. show that any path-consistency algorithm can be exploited
to compute the minimal STP equivalent to a given one, if any (if an inconsistency is
detected, the algorithm returns an empty network). In the following, we will denote
such an algorithm by
PC
stp
. Making use of such a result, in [16], Meiri proposes a
formalism to combine qualitative constraints between points and intervals with (possi-
bly disjunctive) metric constraints between points (as in TCSP). An easy special case
arises when only convex PA-constraints and STP-constraints are considered. Convex
PA-constraints can be encoded as STP-constraints by means of the
toSTP
translation
function described in Table 1. The following result can be found in [16].
