A binarized-domains arc-consistency algorithm for TCSPs: its computational analysis and its use as a filtering procedure in solution search algorithms

Amar Isli

TCSPs (Temporal Constraint Satisfaction Problems), as defined in [Dechter et
al., 1991], get rid of unary constraints by binarizing them after having added
an "origin of the world" variable. In this work, we look at the constraints
between the "origin of the world" variable and the other variables, as the
(binarized) domains of these other variables. With this in mind, we define a
notion of arc-consistency for TCSPs, which we will refer to as
binarized-domains Arc-Consistency, or bdArc-Consistency for short. We provide
an algorithm achieving bdArc-Consistency for a TCSP, which we will refer to as
bdAC-3, for it is an adaptation of Mackworth's [1977] well-known
arc-consistency algorithm AC-3. We show that if a convex TCSP, referred to in
[Dechter et al., 1991] as an STP (Simple Temporal Problem), is
bdArc-Consistent, and its "origin of the world" variable disconnected from none
of the other variables, its binarized domains are minimal. We provide two
polynomial backtrack-free procedures: one for the task of getting, from a
bdArc-Consistent STP, either that it is inconsistent or, in case of
consistency, a bdArc-Consistent STP refinement whose "origin of the world"
variable is disconnected from none of the other variables; the other for the
task of getting a solution from a bdArc-Consistent STP whose "origin of the
world" variable is disconnected from none of the other variables. We then show
how to use our results both in a general TCSP solver and in a TCSP-based job
shop scheduler. From our work can be extracted a one-to-all all-to-one shortest
paths algorithm of an IR-labelled directed graph. Finally, we show that an
existing adaptation to TCSPs of Mackworth's [1977] path-consistency algorithm
PC-2 is not guaranteed to always terminate, and correct it.