Information Technology Reference
In-Depth Information
Fig. 3. An example of Simple Temporal Network with four time points in the J- TRE (stp) planner
information, often, is not propagated correctly. This problem can be easily solved by
adding further constraints: for each couple of variables d ij and d jk we add the con-
straint d ik = d ij + d jk . Figure 3 shows an example of Simple Temporal Network with
four time points. Notice that since d ij =
d ji we can economize on the number of
variables and constraints.
It is worth underscoring how the use of numeric variables for maintaining distances
between temporal points opens to interesting opportunities like linking the duration of
an action to the amount of production (or consumption) of a given resource. By simply
adding more variables and more constraints to our simple AC-3 based CSP solver we
have obtained an efficient dynamic All Pair Shortest Path behavior providing constant
time queries (once constraints have been propagated) about distance between temporal
points.
Flaw Management in J-TRE (stp) . The flaw management in J- TRE (stp) is much more
fruitful compared to J- TRE (ac) having the possibility to exploit information from the
Simple Temporal Network. For example, it may happen that two overlapping tokens
cannot be ordered in both ways or that some unifications cannot happen for temporal
reasons. Moreover, if we find in a given search space node that a scheduling flaw cannot
be solved in any way we can conclude that the entire node is an inconsistent one without
caring of further flaws neither performing any constraint propagation.
It is worth underscoring that temporal constraints can no longer be defined among
temporal variables but must be defined among distance variables. As an example, let
us suppose we have two overlapping tokens t i and t j that result in a scheduling flaw.
We know from querying distances between variables that d t i .e,t j .s
[
inf,
1] and
d t j .e,t i .s
inf, + inf ] . From this information we deduce that we can schedule the
two tokens only as t j
[
t i .s wouldn't
be enough as it wouldn't propagate temporal distance information. In order to schedule
these tokens we need to force domain of variable d t j .e,t i .s to be greater or equal than 0.
In a similar way, when unifying two tokens t i and t j , adding the multi-equals constraint
is not enough as we also need to add constraint d t i .s,t j .s =0 as well as constraint
d t i .e,t j .e =0 .
t i ( t j before t i ). A simple constraint like t j .e
Search WWH ::




Custom Search