=Paper=
{{Paper
|id=Vol-2785/paper9
|storemode=property
|title=A Language for Timeline-based Planning
|pdfUrl=https://ceur-ws.org/Vol-2785/paper9.pdf
|volume=Vol-2785
|authors=Giulio Bernardi,Amedeo Cesta,Andrea Orlandini,Alessandro Umbrico,Marta Cialdea Mayer
|dblpUrl=https://dblp.org/rec/conf/overlay/0001COUM20
}}
==A Language for Timeline-based Planning==
https://ceur-ws.org/Vol-2785/paper9.pdf
Proceedings of the
2nd Workshop on Artificial Intelligence and Formal Verification, Logics, Automata and Synthesis (OVERLAY),
September 25, 2020
A Language for Timeline-based Planning∗
Giulio Bernardi1 , Amedeo Cesta, Andrea Orlandini, Alessandro Umbrico2 , and Marta
Cialdea Mayer3
1
Indipendent Researcher
2
National Research Council, ISTC-CNR, Rome, Italy
3
ROMA TRE University, Rome, Italy
Abstract
In order to represent planning problems, Artificial Intelligence planning lan-
guages are used to describe environment’s conditions and operators which can lead
to desired goals by generating a chain of actions based on these conditions and
operators. Historically, several languages have been defined according to different
planning paradigms. Most of these languages are often strongly related to specific
planning systems and lack a clear formal semantics. A recent work defines a formal
framework for timeline-based planning and scheduling providing a clear semantics
for planning concepts needed to specify timeline-based planning problems. This
abstract introduces ghost, a new specification language for timeline-based plan-
ning and scheduling based on such a framework. The main aim of ghost is to
provide a concrete and compact specification language for timeline-based planning
and scheduling domains and problems dealing also with uncertainty.
1 Introduction
Among knowledge-based systems, automated planning systems require the definition of domains and
problem instances to be solved. This entails suitable planning specification languages to describe
environment’s conditions and operators which can lead to desired goals by generating a chain of actions
based on these conditions and operators. Historically, several planning specification languages have been
defined according to different planning paradigms. Most of these languages are often strongly related to
specific planning systems and lack a clear formal semantics.
Classical action-based planners usually adopt description languages derived from logic-based formulation
such as, e.g., STRIPS [10], the Situation Calculus [20] and ADL [19]. With the aim of encouraging the
empirical evaluation of planners performance, and the development of standard sets of problems all in
comparable notations, a Planning Domain Description Language (PDDL) [16] was introduced roughly
reproducing the expressiveness of Pednault’s ADL [19] for propositions and the expressiveness of UMCP
[15] for actions. PDDL became the reference language for International Planning Competitions1 and,
with its many extensions [13], it is a sort of standard in the A.I. planning community. Unfortunately,
the above languages are seldom used in real world applications of planning and scheduling technologies.
∗ The CNR authors are partially supported by European Commission under the ShareWork project (G.A. 820807). Giulio
Bernardi is now working at Google.
Copyright © 2020 for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
1 http://www.icaps-conference.org/index.php/Main/Competitions
54 A. Cesta, A. Orlandini, A. Umbrico, M. Cialdea Mayer
Indeed, a gap exists between the above languages and application-oriented proposals. The main difference
lies in the considered problems and domains: quite simplified in the IPC case, more sophisticated in the
application scenarios.
Attempts to bridge this gap have been done in Planning and Scheduling (P&S) with the aim of dealing
with more complex domains while following a principled approach that allows the generalization of results.
Following this trend, some P&S languages have been proposed considering other planning approaches.
Application oriented planners are usually endowed with their own peculiar description languages, for
example the Task Formalism in O-Plan [8], and the specialized languages used in OPIS [21], IxTeT [14]
and HSTS [17]. In [5], Cesta and Oddi propose a Domain Description Language (DDL) for ESA mission
applications also developing a formal analysis of the representation language. DDL constitutes the main
specification language for APSI-TRF [4, 12] and, with some variations [11], for most of its applications
[3, 11]. At NASA, the development of the EUROPA planning system [2] fostered the definition of specific
description languages, i.e., NDDL2 and ANML [9].
Unfortunately, most of the above mentioned languages usually lack a reference to a formal conceptual
framework and present some limits related to expressive power and syntax. A recent work [7] defines a
formal framework for timeline-based planning and scheduling providing a clear semantics for planning
concepts and specifying timeline-based planning problems with uncertainty [6]. This paper presents
ghost, a new language for timeline-based planning and scheduling based on such a framework. The
main aim of ghost is to specifically address the above mentioned weaknesses and having readability,
maintainability, generality and increased expressive power among its design goals. ghost also provides a
concrete and compact modeling language for timeline-based planning and scheduling with uncertainty.
2 Timeline-based Planning and Scheduling
A timeline-based planning domain contains the characterization of a set of state variables, representing the
components of a system. A state variable x is characterized by the set of values it may assume, denoted
by values(x), possible upper and lower bounds on the duration of each value, and rules governing the
correct sequencing of such values. A timeline for a state variable is made up of a finite sequence of valued
intervals, called tokens, each of which represents a time slot where the variable assumes a given value. In
general, timelines may be flexible, i.e., the start and end times of each of its tokens are not necessarily
fixed time points, but may range in given intervals. For the sake of generality, temporal instants are taken
from an infinite set of non negative numbers T, including 0. The notation T∞ will be used to denote
T ∪ {∞}, where t < ∞ for every t ∈ T.
Tokens in a timeline for the state variable x are denoted by expressions of the form xi , where the
superscript indicates the position of the token in the timeline. Each token xi is characterized by a
value vi ∈ values(x), an end time interval [ei , e0i ] referred to as end_time(xi ), and a duration interval
[di , d0i ] (as usual, the notation [x, y] denotes the closed interval {t | x ≤ t ≤ y}). The start time interval
start_time(xi ) of the token xi is [0, 0] if xi is the first token of the timeline (i.e. i = 1), otherwhise, if i > 1,
start_time(xi ) = end_time(xi−1 ). So, a token has the form xi = (vi , [ei , e0i ], [di , d0i ]) and a timeline is a
finite sequence of tokens x1 , . . . , xk . The metasymbol F T L (F T Lx ) will henceforth be used to denote a
timeline (for the state variable x), and FTL to denote a set of timelines. Being tokens flexible, their exact
start and end times will be decided at execution time. Tokens can be either controllable (the controller can
decide their end time, i.e. their duration), or uncontrollable (their duration depends on the environment’s
choices). The controllability of tokens start times depends on the controllability of the respective previous
token in the timeline. Each token is consequently equipped also with a controllability tag, identifying the
class it belongs to.
A scheduled timeline is a particular case where each token has a singleton [t, t] as its end time, i.e., the
end times are all fixed. A schedule of a timeline F T Lx is essentially obtained from F T Lx by narrowing
down token end times to singletons (time points) in such a way that the duration requirements are fulfilled.
In a given timeline-based domain, the behavior of state variables may be restricted by requiring that time
intervals with given state variable values satisfy some temporal constraints. Such constraints are stated as
a set of synchronization rules which relate tokens on possibly different timelines through temporal relations
2 https://github.com/nasa/europa/wiki/Quick-Start
55
between intervals or between an interval and a time point. These temporal relations refer to token start or
end points, that will henceforth be called events. If FTL is a set of timelines and tokens(FTL) the set of
the tokens in FTL, then the set Υ(FTL) of the events in FTL is the set containing all the expressions of
the form start_time(xi ) and end_time(xi ) for xi ∈ tokens(FTL). A temporal relation on tokens has one
of the following forms: p ≤[lb,ub] p0 , p ≤[lb,ub] t, t ≤[lb,ub] p where p, p0 ∈ Υ(FTL), t, lb ∈ T and ub ∈ T∞
and lb ≤ ub.
Intuitively, p ≤[lb,ub] p0 states that the token start/end point denoted by p occurs from lb to ub time
units before that denoted by p0 ; p ≤[lb,ub] t states that the token start/end point denoted by p occurs
from lb to ub time units before the time point t and the third relation that it occurs from lb to ub time
units after t. Other relations between tokens ([1]) can be defined in terms of the primitive ones, e.g.:
xi before[lb,ub] y j is the same as end_time(xi ) ≤[lb,ub] start_time(y j ); xi during[lb1 ,ub1 ][lb2 ,ub2 ] y j can be
defined as start_time(y j ) ≤[lb1 ,ub1 ] start_time(xi ) and end_time(xi ) ≤[lb2 ,ub2 ] end_time(y j ); a contains
relation is its converse: xi contains[lb1 ,ub1 ][lb2 ,ub2 ] y j if and only if y j during[lb1 ,ub1 ][lb2 ,ub2 ] xi . Temporal
relations are also used to state the synchronization rules of the planning domain. Here, it is sufficient
to say that such rules allow the modeler to state requirements of the following form: for every token xi0
where the state variable x0 assumes the value v0 , there exist tokens xi11 , . . . , xinn where the state variables
x1 , . . . , xn hold some given specified values, and all these tokens are related one to another by some given
temporal relations. Unconditioned synchronization rules are also allowed, and useful for stating domain
invariants (initial situation for problems) and planning goals. A flexible plan Π is a pair (FTL, R), where
FTL is a set of timelines and R is a set of temporal relations, involving tokens in some timelines in FTL.
An instance of the flexible plan Π = (FTL, R), is any schedule of FTL that satisfies every relation in R.
Resources have been integrated in the theoretical framework in [22], but entering into details is outside
the scope of the present work.
3 The GHOST Language
ghost is a completely new language influenced by a number of popular programming languages and
DDL (as ghost is supposed to replace it). Its name is given after its feature of being ”transparent”
for engineers, i.e. not influencing the modeling process. This section aims at giving the flavour of the
language, showing its expressivity, generality and compactness. As a matter of fact, an important design
principle of the language is “Name only what it’s meaningful”: unused variables, parameters and default
values can generally be omitted.
A ghost file (specifying either a domain or a specific problem, or both) consists of a collection of
declarations. The most important ones are the definition of types. Beyond usual types such as enumerated
or interval ones, types may represent state variables and resources. The declaration of a state variable type
contains all needed information: values and their allowed durations and transitions, along with possible
synchronization rules governing given values. The following simple example shows the definition of an
interval type (Coord, which is an integer in a given interval), an enumerated type and a state variable
(sv) one:
type coord = int [ -1000 ,+1000];
type room = enum (A , B );
type Robot = sv (
uncontr GoingTo ( coord x , coord y ) [10 , 30] -> At (x , y );
At ( coord x , coord y ) -> GoingTo ;
synchronize :
GoingTo -> during Camera . PointingAt (0 ,0);
variable :
allowed_in : room ;
);
The initial rows of the description of the Robot type define the state variable values and the respective
allowed transitions: GoingTo (which is uncontrollable) and At (controllable, by default), both having a
pair of coord as parameters; GoingTo and At can transition to only one possible state. The GoingTo
value has a duration constraint, expressed by the interval [10, 30], while At has none (default), i.e., its
duration interval is [1, ∞]. The synchronize section (when present) introduces synchronization rules. In
56 A. Cesta, A. Orlandini, A. Umbrico, M. Cialdea Mayer
this case, it is required that every token with a GoingTo value (no need to state its parameters) must
occur while the Camera state variable assumes the value PointingAt(0,0). The temporal operators used
in such rules may be any a-la-Allen [1] constraint like, e.g., meets, during and so on. Like this example
shows, state variable values are allowed to have parameters, on which constraints can be expressed both
in transitions and synchronization rules.
The definition of a state variable type is allowed to have parameters, specified in the variable section
(when present). In the above example, every instance of the type has a corresponding room in which it is
allowed to enter. In other terms, variables must be bound to actual values when defining instances of the
type (see below). It is worth pointing out that variable types can also be state variables. For instance,
one might declare a variable friend: Robot (every Robot has another Robot as a friend).
A state variable type can also be defined as either external (all its values being uncontrollable) or
planned (default).
Instances of a type variable (called components) are the "actual" state variables, as theoretically
defined, i.e., at runtime, timelines for them will be built by the planner. State variables types are useful
when problem instances may have multiple components of the same type. When this is not the case,
a component can also be defined directly (its "fields" obviously excluding variables). For example, an
instance of the state variable type Robot, allowed to enter room A, may be defined as follows:
comp Robot1 = Robot [ allowed_in = A ];
or simply, since Robot has a single parameter:
comp Robot1 = Robot [ A ];
ghost also allows one to define resources, both renewable and consumable ones. Like for the case of
state variables, resource types can be defined. For instance
type tank = r e s o u r c e (0 ,100);
defines a type for the consumable resource tank, whose capacity varies from 0 to 100. Resource declarations
can be more complicated, and may contain also synchronizations and variable binding, but we do not
enter into details here. A resource can be referred to in a state variable synchronize section.
A specific initialization section in a ghost file describes the situation of a specific scenario, and is
usually written in the problem file. It contains the description of known facts about the initial state of
the system and desired goals, along with other problem-specific parameters, such as a start time (the first
available time instant) and the planning horizon (all of them obviously having default values).
Here follows a simple example of a complete ghost specification file (where singleton intervals of the
form [t,t] are abbreviated by t).
domain T r a f f i c L i g h t D o m a i n ;
// State Variable types
type TrafficLight = sv (
Red 30 -> Green ;
Green 20 -> Yellow ;
Yellow 10 -> Red ;
synchronize :
Green -> starts other . Red ;
variable :
other : TrafficLight ;
);
// Components
comp TL1 : TrafficLight [ TL2 ];
comp TL2 : TrafficLight [ TL1 ];
// Facts , goals and temporal parameters
init (
var horizon = 200;
var resolution = 300;
fact TL1 . Green at 0;
fact TL2 . Red at 0;
goal TL2 . Yellow ;
)
57
4 Conclusions
A recent work defines a formal framework for timeline-based planning and scheduling providing a clear
semantics for planning concepts needed to specify timeline-based planning problems. This abstract briefly
presented ghost, a new specification language for timeline-based planning and scheduling based on such
a framework. The main aim of ghost is to provide a concrete and compact specification language for
timeline-based planning and scheduling domains and problems dealing also with uncertainty. The definition
of ghost is part of a more general initiative addressing Knowledge Engineering issues in timeline-based
P&S. Indeed, ghost is defined as supporting language for KEEN, a Knowledge Engineering Environment
for developing Timeline-based Planning applications [18].
References
[1] J. F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM,
26(11):832–843, Nov. 1983.
[2] T. Bedrax-Weiss, C. McGann, A. Bachmann, W. Edgington, and M. Iatauro. EUROPA2: User and
contributor guide. Technical report, Technical report, NASA Ames Research Center, 2005.
[3] A. Cesta, G. Cortellessa, S. Fratini, and A. Oddi. MrSPOCK: Steps in Developing an End-to-End
Space Application. Computational Intelligence, 27(1), 2011.
[4] A. Cesta and S. Fratini. The Timeline Representation Framework as a Planning and Scheduling
Software Development Environment. In 27th Workshop of the UK Planning and Scheduling Special
Interest Group (PlanSIG 2008), 2008.
[5] A. Cesta and A. Oddi. DDL.1: a formal description of a constraint representation language for
physical domains. In M. Ghallab and A. Milani, editors, New directions in AI planning, pages 341–352.
IOS Press, 1996.
[6] M. Cialdea Mayer and A. Orlandini. An executable semantics of flexible plans in terms of timed game
automata. In F. Grandi, M. Lange, and A. Lomuscio, editors, The 22nd International Symposium on
Temporal Representation and Reasoning (TIME). IEEE, 2015.
[7] M. Cialdea Mayer, A. Orlandini, and A. Umbrico. Planning and execution with flexible timelines: a
formal account. Acta Informatica, 53(6):649–680, 2016.
[8] K. Currie and A. Tate. O-Plan: The open planning architecture. Artificial Intelligence, 52(1):49 –
86, 1991.
[9] W. C. David E. Smith, Jeremy Frank. The anml language. In Workshop on Knowledge Engineering
for Planning and Scheduling (KEPS), 2008.
[10] R. E. Fikes and N. J. Nilsson. STRIPS, a retrospective. Artificial Intelligence, 59(1):227 – 232, 1993.
[11] S. Fratini, A. Cesta, R. De Benidictis, A. Orlandini, and R. Rasconi. APSI-based deliberation in Goal
Oriented Autonomous Controllers. In ASTRA 2011, 11th Symposium on Advanced Space Technologies
in Robotics and Automation, 2011.
[12] S. Fratini, G. Cortellessa, A. Oddi, and A. Cesta. Software User Manual – APSI Framework. European
Space Agency, issue 3, revision 2 edition, 2010.
[13] A. Gerevini and D. Long. Preferences and soft constraints in pddl3. In A. Gerevini and D. Long,
editors, ICAPS workshop on Planning with Preferences and Soft Constraints, pages 46–53, 2006.
[14] M. Ghallab and H. Laruelle. Representation and control in ixtet, a temporal planner. In Proceedings
of the Second Intl. Conf. on Artificial Intelligence Planning Systems (AIPS-94), pages 61–67, 1994.
58 A. Cesta, A. Orlandini, A. Umbrico, M. Cialdea Mayer
[15] D. S. N. Kutluhan Erol, James Hendler. UMCP: A sound and complete procedure for hierarchical
task-network planning. In 2nd International Conference on Artificial Intelligence Planning Systems
(AIPS), pages 249–254, 1994.
[16] D. Mcdermott, M. Ghallab, A. Howe, C. Knoblock, A. Ram, M. Veloso, D. Weld, and D. Wilkins.
PDDL - The Planning Domain Definition Language. Technical report, CVC TR-98-003/DCS
TR-1165, Yale Center for Computational Vision and Control, 1998.
[17] N. Muscettola. HSTS: Integrating Planning and Scheduling. In Zweben, M. and Fox, M.S., editor,
Intelligent Scheduling. Morgan Kauffmann, 1994.
[18] A. Orlandini, G. Bernardi, A. Cesta, and A. Finzi. Planning meets verification and validation in a
knowledge engineering environment. 8(1):87–100, 2014.
[19] E. P. D. Pednault. ADL: exploring the middle ground between strips and the situation calculus. In
1st international conference on Principles of knowledge representation and reasoning, pages 324–332,
1989.
[20] R. Reiter. Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical
Systems. The MIT Press, 2001.
[21] S. F. Smith. The opis framework for modeling manufacturing systems. Technical report, The
Robotics Institute, Carnegie Mellon University, Pittsburgh. Tech. Rep. CMU-RI-TR-89-30, 1989.
[22] A. Umbrico, A. Cesta, M. Cialdea Mayer, and A. Orlandini. Integrating resource management and
timeline-based planning. In Twenty-Eighth International Conference on Automated Planning and
Scheduling (ICAPS 2018), pages 264–272, 2018.