Information Technology Reference
In-Depth Information
for example, to have a predicate
At
(
l,s,e
)
and a predicate
GoingTo
(
l,s,e
)
. We know
for sure that tokens assuming
At
and
GoingTo
values cannot overlap. However, two
tokens both assuming the
At
value can overlap if and only if their respective parameters
(
l
,
s
and
e
) are pairwise constrained to be equal. In this case we talk about
merging
(or,
in some cases,
unification
)oftokens.
Now let us suppose that we want a rule stating that every time we are going to a given
location we will reach that location. We can enforce such rule by temporally constrain-
ing the
GoingTo
(
l,s,e
)
and the
At
(
l,s,e
)
predicates by means of the Allen's
meet
relation having the same location
l
(see [14]). In other words, for each token
t
i
with a
GoingTo
(
l,s,e
)
value the planner must ensure that
t
i
meets
another token
t
j
with an
At
(
l,s,e
)
value, either by imposing the
meet
constraint between
t
i
and
t
j
if they both
exist, or by adding the missing token
t
j
before enforcing the same constraints. This
kind of “rules” are generalized in a concept usually called
compatibility
(again, here
we use a terminology consistent with [13]). Compatibilities define causal relations that
must be complied to in order for a given token to be valid. Although the syntax can be
quite different among various planners, a compatibility can be recursively defined by
means of a
reference
predicate and a
requirement
where a requirement can be a slave
(or target) predicate, a relation among predicates, a conjunction of requirements or, in
rare cases, a disjunction of requirements. It is important to underscore that the com-
patibilities may often involve predicates defined on different timelines, thus allowing
to synchronize concurrent activities on different domain components. Most timeline-
based planners admit only conjunctions of requirements and reproduce disjunctions by
assigning multiple compatibilities to the same predicate.
To
simplify
matters,
we
describe
compatibilities
through
logic
implications
reference
requirement
. In some cases, we will give tokens a specific name and
will address their arguments using a Java style
dot
notation (i.e., given a token
t
having
proposition
P
(
s, e
)
its starting point will be expressed as
t.s
).
Other commonly used types of timelines are the
resources
characterized by a
re-
source level
→
, representing the amount of available resource at any given
time, and by a
resource capacity
L
:
T
→
R
C∈
R
, representing the physical limit of the available
resource.
We can identify several types of resources depending on how the resource level can
be increased or decreased in time. A
consumable resource
is a resource whose level
is increased or decreased by some activities in the system. An example of consumable
resource is a reservoir which is produced when a plan activity “fills” it (i.e., a tank re-
fueling task) as well as consumed if a plan activity “empties” it (i.e., driving a car uses
gas). We model consumable resources through a timeline that has two allowed predi-
cates: a predicate
produce
(
a, s, e
)
to represent a resource production of amount
a
from
time
s
to time
e
and a predicate
consume
(
a, s, e
)
to represent a resource consumption
of amount
a
from time
s
to time
e
. The planner may need to identify an ordering of the
involved activities in order to avoid overproductions (resource level
L
cannot exceed
capacity
C
) as well as overconsumption (resource level
L
cannot cannot be lower than
zero).
The last commonly used timeline type, quite popular in the scheduling literature,
is the
reusable resource
. Reusable resources can be modeled as consumable resources
