Overview
The many formalisms and algorithms proposed in the literature
for Temporal Constraint Satisfaction Problems (TCSP) have
essentially ignored the subtleties
involved in the presence of multiple time granularities in the
temporal constraints. An example of a simple constraint specified in terms of a
time granularity is the following:
"package shipment must occur the next business day after check clearance".
A first issue immediately arises: what is the exact semantics of this
constraint? Is a business day intended as the common business day in
the United States, i.e. any day between Monday and Friday excluding
U.S. holidays, or the company is located in a different country
and we should consider different holidays? Does the company have particular
rules so that, for example, Saturday is considered a business day?
Similar problems will be encountered when considering constraints in
terms of other time granularities that we commonly use in our
language, like academic semesters and fiscal years.
In [WBB+97] we have
proposed a very expressive formalism for time granularities with a clear set-theoretic semantics.
The formalism has been refined later and adopted in different application contexts
[BWJ00], among which temporal constraint satisfaction.
If all the constraints in the CSP are in terms of the same time granularity,
some of the standard algorithms for CSP, like consistency checking through arc- or path-consistency
([DMP91],
[Bes94]),
can be successfully applied.
For CSP's with multiple granularities, however, we have shown in
[BWJ98]
that the same algorithms cannot be straightforwardly adapted.
Any conversion necessarily introduces an approximation;
For example, the above constraint
may be translated in terms of hours with a minimum of 1 hour and a
maximum of 95 hours. The number 95 takes into account a check clearance at
the beginning of a Friday and a shipment at the end of next
Monday according to the constraint. However, if the check is cleared
on Monday, the new constraint would allow a shipment on Thursday which is
clearly a violation of the original constraint. Approximate conversion algorithms are
extensively discussed in
[BWJ98].
Any consistency algorithm adopting these conversions as the only tool to
reduce the problem to a standard CSP is inevitably incomplete.
A complete algorithm adopting a different approach is described in detail in [BWJ02a].
Our system adopts a conversion based approximate algorithm as a preprocessing to this complete algorithm.
The GSTP system allows the user to specify constraint networks similar
to STP
[DMP91],
but where constraints are in terms of (possibly
different) time granularities. A rich pre-defined set of time
granularities is available, but new user-defined
granularities can be easily added, and they will be handled by the
constraint solving algorithms.
Here is a slightly more detailed introduction to GSTP.