introduces 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.
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 [
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 [
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 2https://github.com/nasa/europa/wiki/Quick-Start 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 ([
Resources have been integrated in the theoretical framework in [
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) [
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 [
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 = resource (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 TrafficLightDomain ; // 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 ; )
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 [