Timeline-based Planning and Scheduling (P&S) usually deals with two main sources of uncertainty: some components may depend on an external environment and cannot be planned; there may be tasks whose duration cannot be exactly foreseen in advance. Such uncertainties are formally defined and consequent controllability issues have been addressed, focusing on dynamic controllability. In this work, we present a new software prototype, tiga2exec, for dynamic controllable execution of timeline-based plans leveraging recent results gathered from the integration of P&S and Model Checking techniques. tiga2exec is deployed in a timeline-based planning system to control plan execution guaranteeing dynamic controllability. A preliminary experimental evaluation is also presented.
approach presented in [
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. 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 end end times will be decided at execution time. Tokens
can be either controllable (the controller can decide both their start and end time), or uncontrollable
(both start and end time depend on the environment’s choices), or partially controllable (the controller
can decide when to start them, but their exact duration is outside the system’s control). Each token is
consequently equipped also with a controllability tag, identifying the class it belongs to. The presented
theoretical background follows the formal framework presented in [
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 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. Other relations between tokens [
A new prototype for robust timeline-based plan execution
tiga2exec is a new software prototype composed by a set of modules for representing a strategy generated
by UPPAAL-TIGA and making it accessible (via a suitable software interface) for timeline-based P&S
systems to provide plan dispatching strategy, i.e., a dynamic decision mechanism for token activation
according to a given system status and execution time. Three main features are considered for prototype
design: strategy representation, creation and access. Strategy representation is based on the format of the
output provided by UPPAAL-TIGA. Namely, a winning strategy generated by the TGA model checker
is a set of rules, each of which is composed by a set of state formulae (a pair timeline-token) associated
to actions to be performed. Each state usually has two possible actions: one associated to an actual
transition (an action leading to a value change on a state variable) with some temporal constraints derived
from guards on transitions in the associated TGA network and one special action that requires the system
to wait. If a transition is uncontrollable, only a wait action is represented as the value change is supposed
to be executed by the environment. In order to enable its actions, each strategy is associated to temporal
guards (temporal constraints) and to clock updates (for checking temporal constraints). The software
structure of tiga2exec replicates this hierarchy and has been deployed within PLATINUm [
tiga2exec workflow is the following: once a plan is generated by PLATINUm, tiga2exec triggers
Plan2Tiga, an encoder capable to translate a flexible plan in a TGA network and provided as input for
UPPAAL-TIGA. The model checker verifies the TGA network in order to check dynamic controllability
and, if possible, generates a winning strategy. tiga2exec then analyzes the output to check whether
the plan is DC or not (i.e., plan either dynamically controllable or not controllable). The strategy is
then encoded as a set of software objects triggered by specific conditions (i.e., states and timings) and
issuing the corresponding actions defined in the winning strategy. Indeed, a P&S system can access the
strategy querying step-by-step tiga2exec about which are the actions to be performed. During each
execution step, tiga2exec will perform a cycle to extract actions from the strategy. For each cycle,
tiga2exec performs a synchronization phase and a dispatching phase. The synchronization phase is
for collecting data from the P&S system and the environment (via external observations) and to check
whether the actual plan execution is coherent with the plan specifications. The dispatching phase is about
tokens selection and dispatching. Some variables representing the status of the execution are added to
the strategy representation as well as some internal clocks for supervising the execution. The last status
of the system is considered to track uncontrollable transitions that may occur and, in case, update the
internal system status with post conditions for these transitions. In general, tiga2exec can return a
list of tokens to be dispatched (dispatching actions until a wait action is found). The internal logic to
implement these steps is the following: a) The actual status perceived by the P&S system is compared
with the expected status by tiga2exec; b) internal plan clocks are updated; c) Each internal state is
compared to the actual status and when they match, an action trigger is searched between the rules in
the strategy; d) once a match is found, the action is added to the list of actions to be dispatched and
post conditions are applied to the internal status. If a match is not found, an action wait is added to
the action list and the list is returned. tiga2exec is fully integrated within PLATINUm and can be
integrated in any timeline-based P&S system implemented according to the framework given in [
We present some preliminary empirical results considering a benchmark domain for planning and
scheduling introduced in [
Domain1
Domain2
Domain3 %DC %WEAK %NO PLAN %TIMEOUT %DC %WEAK %NO PLAN %TIMEOUT %DC %WEAK %NO PLAN %TIMEOUT
Figure 1 depicts for each domain plan generation success rate and, when generated, plan controllability. In Domain1, experiments show a high rate of planning failures (50%). The planner is guided by heuristics to minimize plan makespan and, thus, scheduling science and communication tasks as soon as possible. All science/communications are then scheduled during the first temporal window resulting in a plan with small flexibility to deal with temporal uncertainty. Increasing the number of goals, many tasks are planned in a temporally rigid way and often being unable to achieve all the goals (i.e., no valid plan). The planner is able to generate DC plans for problem instances only with a limited number of goals. In Domain2, the planner is always able to generate a plan but not fully controllable as almost half of the plans were only weakly controllable. In order to achieve the goals within the given planning horizon, the planner is forced to tightly schedule tasks and, again, only when dealing with a small number of goals the planner was able to keep DC. In the other instances, the planner produces weakly controllable plans. In Domain3, a larger planning horizon allows the planner to always generate DC plans and to complete plans execution.
Figure 2 shows the average temporal costs for, respectively, planning, verification (Plan2Tiga + UPPAAL-TIGA) and strategy management when tiga2exec is involved for the problem instances considered in Domain3 varying the number of goals and the temporal uncertainty. First, it is clear that verification and strategy management costs are compatible with planning latencies. Then, an increase of temporal uncertainty does not affect costs as planning and verification systems are effective in managing temporal flexibility. For PLATINUm and tiga2exec, the most important element influencing costs is the number of goals. In fact, increasing the number of goals, generated plans contains more tokens and control strategies are larger (in terms of control rules). This entails larger times for strategy management. 4
This paper presents tiga2exec, a new software prototype, for dynamic controllable execution of timelinebased plans leveraging the integration of P&S and Model Checking techniques. tiga2exec implements a work chain that i) encodes flexible plans as a network of TGA, ii) exploits a verification tool to check dynamic controllability property for flexible plans and, possibly, generate a dynamic execution strategy and iii) implements such strategy as a robust plan execution controller for P&S systems. tiga2exec is deployed in PLATINUm, a timeline-based planning system to control plan execution guaranteeing dynamic controllability. A preliminary experimental evaluation is also presented.
CNR authors are partially supported by the E.C. and ShareWork project (H2020 – Factories of the Future G.A. nr. 820807).