Information Technology Reference
In-Depth Information
to new possible future evolutions with respect to search control. We also present an in-
teresting comparison of the planner with respect to a quite challenging problem domain.
2
Basics on Timelines
This section introduces some basic concepts. For a more detailed dissertation on time-
line based planners the reader should make reference to [13,3,6,4].
2.1
Time, Tokens and Relations: The Plan
To include time into a logic formalism we choose to provide the predicates with extra
arguments belonging to the Time domain
T
(real or discrete). For example, a predicate
At
(
l
)
, denoting the fact that an agent is at a certain location
l
, can be extended with two
temporal arguments
s
, with
s<e
, representing its starting and ending
times, respectively; the
At
(
l,s,e
)
formula would be true only if the agent is at location
l
from time
s
to time
e
. Similarly to what described in [13], we call
token
a proposition
that has temporal arguments.
In order to force the proposition arguments to assume the desired values, J-
TRE
allows the imposition of any kind of linear constraints among the arguments and/or be-
tween the arguments and other variables. Since common timeline-based planners typ-
ically accept any kind of quantitative temporal interval relations [14] between tokens,
that must often be customized by the user, the J-
TRE
framework facilitate the synthe-
sis of planning domains by allowing the organization of constraints in macros called
relations
.
The task of the solver is to find a legal sequence of tokens that bring the timelines
(that constitute the partial and final
plan
) into a final configuration that verifies both the
domain theory
1
as well as a determined set of desired conditions called
goals
. Starting
from an initial state, the planner moves in the search space by adding or removing
tokens and/or relations (i.e., changing the current state) until all goals are satisfied.
∈
T
and
e
∈
T
2.2
Interactions among Tokens: The Timelines
From a planning perspective, the easiest way to describe a
timeline
is to consider it a
mere collection of tokens. The predicates that can be accommodated on a timeline as
well as the behavior assumed by the planner when a new token is added to a timeline
depend on the nature of the timeline itself and, in some cases, on the modeled domain.
J-
TRE
allows the utilization of families of timelines which provide different modeling
ability, such as multi-valued state variables [13] as well as renewable and consumable
resources like those commonly used in constraint-based scheduling [9].
The
state variable
is the most used type of timeline in this approach to planning. State
variable predicates are defined by the user during domain definition. The semantics of a
state variable is that for each time instant
t
the timeline can assume only one value.
This corresponds to a mutual exclusion rule between different tokens. Let us assume,
∈
T
1
The set of rules that model the domain's dynamic behavior.
