Information Technology Reference
In-Depth Information
that are produced at their start time and are consumed at their end time. We can model
reusable resources through a predicate
use
(
a, s, e
)
that is true iff there is a production
of resource of amount
a
at time
s
and a consumption of resource of amount
a
at time
e
.
Now let's assume we have two tokens
t
0
and
t
1
belonging to a reusable resource timeline
such that
t
0
.s < t
1
.e
t
1
.s < t
0
.e
(this constraint simply forces their overlapping). The
expected behavior of the resource is to have a resource usage of
t
0
.a
during
t
0
's duration
when there isn't overlapping with
t
1
, a resource usage of
t
0
.a
+
t
1
.a
when
t
0
overlaps
with
t
1
, a resource usage of
t
1
.a
during
t
1
's duration when there is no overlapping with
t
0
and a resource usage of 0 elsewhere.
We also want to define constraints on both reusable and consumable resource levels.
We are interested in supporting the following constraints making use of special predi-
cates:
∧
-
gt
(
a, s, e
)
to force the profile of the resource to be strictly greater than
a
-
ge
(
a, s, e
)
to force the profile of the resource to be greater than
a
-
le
(
a, s, e
)
to force the profile of the resource to be lower than
a
-
lt
(
a, s, e
)
to force the profile of the resource to be strictly lower than
a
3
Reasoning on Timelines
Having defined the basic terminology to describe a partial plan and the timelines, we ad-
dress the problem of reasoning with such building blocks introducing first our planning
architecture. A
Domain Definition Language
called DDL.4 is the entry point to the
J-
TRE
environment, allowing the final user to specify the domain objects of interest,
the relevant physical constraints that influence their possible temporal evolutions (e.g.,
compatibility/coordination constraints among different objects, maximum capacity of
resources, etc.), as well as the planning goals.
Common timeline-based planners reach a solution state by applying an iterative re-
finement procedure. If we call
flaw
every possible inconsistency of the current plan, the
role of the planner can be reduced to the identification and the resolution of each flaw in
the plan. The planning process proceeds until a consistent plan is found, i.e., the propaga-
tion of the solving constraints succeeds and all flaws are eliminated. The general solving
strategy broadly entails: (i) identifying a set of flaws, (ii) selecting a flaw according to
a
selection strategy
, and (iii) solving it by using a
resolution strategy
(see Figure 1 as
a reference). During the solving process, a consistency check routine is called on each
domain object, possibly generating new flaws to be solved. The solving procedure ends
when a consistent node (i.e., containing no flaws) is found. While flaws can be of dif-
ferent types and can arise for different reasons, what they all have in common is that a
search choice
is necessary to solve each of them. Depending on the reason why a flaw
arises, there can basically be four kinds of flaws: (i)
goal flaws
,arisingwhenanewtoken
is added to a state variable to satisfy a compatibility requirement, (ii)
disjunction flaws
,
arising when a disjunction statement is found while enforcing some domain rule (ex-
pressed in DDL code), (iii)
preference flaws
, arising when a preferred statement is found
again while enforcing some domain rule, and (iv)
timeline inconsistency flaws
,arising
when an inconsistency is detected on some domain object like, for example, different
