Information Technology Reference
In-Depth Information
2
Background
In this section, we briefly review basic notions on constraint networks and the main
calculi regarding qualitative relations on points, intervals and rectangles.
Temporal (resp., spatial) knowledge is commonly represented in a qualitative cal-
culus by means of a
qualitative network
consisting of a complete constraint-labeled
digraph
N
=(
V,C
)
,where
V
=
{
v
1
,...,v
n
}
is a finite set of variables, interpreted
over an infinite domain
D
, and the labeled edges in
C
specify the constraints defin-
ing qualitative temporal (resp., spatial) configurations. An edge from
v
i
to
v
j
labeled
with
R
corresponds to the
constraint
v
i
Rv
j
,where
R
denotes a binary relation over
D
which restricts the possible values for the pair of variables
(
v
i
,v
j
)
.Thefullsetof
relations of the calculus is usually taken as the powerset
2
B
,where
B
is a finite set of
2
B
is of
binary
basic relations
that forms a partition of
D
×
D
. Thus, a relation
R
∈
the form
R
=
, where each
r
i
is a basic relation, and
R
represents the
union of the basic relations it contains. If
m
=1
, we call
R
a
basic relation
;other-
wise (
m>
1
),wecallita
disjunctive relation
. A special case of disjunctive relation
is the
universal relation
, denoted by '?', which contains all the basic relations. A
basic
constraint
v
i
{
{
r
1
,...,r
m
}
v
j
expresses definite knowledge about the values that the two vari-
ables
v
i
,v
j
can take, while a
disjunctive constraint
v
i
{
r
}
v
j
expresses indefi-
nite or imprecise knowledge about these values. In particular, the
universal constraint
v
i
?
v
j
states that the relation between
v
i
an
v
j
is totally unknown. From a logical point
of view, a disjunctive constraint
v
i
{
r
1
,...,r
m
}
r
1
,...,r
m
}
v
j
can be viewed as the disjunction
v
i
{
v
j
.
An
instantiation
of the constraints of a qualitative network
N
is a mapping
ι
repre-
senting an assignment of domain values to the variables of
N
. A constraint
v
i
Rv
j
is
said to be
satisfied
by an instantiation
ι
if the pair
(
ι
(
v
i
)
,ι
(
v
j
))
belongs to the binary
relation represented by
R
.A
consistent instantiation
,or
solution
, of a network is an as-
signment of domain values to variables satisfying all the constraints. If such a solution
exists, then the network is consistent, otherwise it is inconsistent.
The main reasoning task in qualitative reasoning is
consistency checking
,which
amounts to deciding if a network is consistent. If all relations are considered, consis-
tency checking is usually NP-hard. Hence, finding subsets of
2
B
for which consistency
checking turns out to be polynomial (
tractable subsets
) is an important issue to address.
Another common task in qualitative reasoning is computing the unique
minimal net-
work
equivalent to a given one by determining, for each pair of variables, the
strongest
relation
(minimal relation
) entailed by the constraints of the network. It can be easily
shown that each basic relation in a minimal network is
feasible
, i.e., it participates in
some solution of the network. To deal with these tasks, constraint propagation tech-
niques are usually exploited [25,23]. The most prominent method for constraint prop-
agation in qualitative temporal reasoning is the so-called
path-consistency algorithm
,
PC-algorithm for short [15]. Such an algorithm refines relations by successively apply-
ing the operation
R
ij
←
r
1
}
v
j
∨
...
∨
v
i
{
r
m
}
R
kj
)
for every triple of variables
(
v
i
,v
k
,v
j
)
,
until a stable network is reached, where
R
ij
,R
ik
,R
kj
are the relations constraining the
pair of variables
(
v
i
,v
j
)
,
(
v
i
,v
k
)
,
(
v
k
,v
j
)
, respectively (
R
ij
∩
(
R
ik
◦
stands for the composition of
relations). If the empty relation is obtained during the process, then the input network
is inconsistent; otherwise, we can conclude that the output network is
path consistent
,
◦
