Information Technology Reference
In-Depth Information
Timeline Planning in the J-TRE Environment
Riccardo De Benedictis and Amedeo Cesta
CNR, Italian National Research Council, ISTC, Rome, Italy
{
name.surname
}
@istc.cnr.it
Abstract.
Timeline-based representations constitute a quite natural way to rea-
son on time and resource constraints while planning. Additionally timeline-based
planners have been demonstrated as successful in modeling and solving prob-
lems in several real world domains. In spite of these successes, any aspect re-
lated to search control remains a “black art” for few experts of the particular
approach mostly because these architectures are huge application developments
environments. For example, the exploration of alternative search techniques is
quite hard. This paper proposes a general architecture for timeline-based reason-
ing that brings together key aspects of such reasoning leaving freedom to specific
implementations on both constraint reasoning engines and resolution heuristics.
Within such architecture, called J-
TRE
, three different planners are built and com-
pared with respect to a quite challenging reference problem. The experiments
shed some light on key differences and pave the way for future works.
1
Introduction
Common timeline-based planners like E
UROPA
[1], ASPEN [2], IxTeT [3] and T
RF
[4,5] are defined as complex software environments suitable for generating planning
applications, but quite heavy to foster research work on specific open issues. Some theo-
retical work on timeline-based planning like [6] was mostly dedicated to explain details
of [1] identifying connection with classical planning
a-la
PDDL [7]. The work on Ix-
TeT and T
RF
have tried to clarify some key underlying principles but mostly succeeded
in underscoring the role of time and resource reasoning [8,9]. The search control part
has always remained significantly under explored. The current realm is that although
these planners capture elements that are very relevant for applications, their theories are
often quite challenging from a computational point of view and their performance are
rather weak compared with those of state of the art classical planners. Indeed, timeline-
based planners are mostly based on the notion of partial order planning [10] and have
almost neglected advantages in classical planning triggered from the use of G
RAPH
-
PLAN
and/or modern heuristic search [11,12]. Furthermore, these architectures rely on
a clear distinction between temporal reasoning and other forms of constraint reasoning
and there is no sign of attempts to change.
This paper, after a brief introduction on timeline-based planning basics, introduces
the J-
TRE
architecture, an open refinement search framework that encloses common
elements of timeline-based planners. Furthermore, three different planners are instan-
tiated which rely on different generic technologies. This approach allows us to fairly
compare them as possible alternatives and even propose new ones by opening the way
