Timeline-based Planning has been successfully applied in several contexts to solve Planning and Scheduling (P&S) problems. A key enabling feature of the timeline-based approach to planning is its capability of dealing with temporal flexibility. Temporal flexibility is an important feature in real world scenarios. Indeed, it can be exploited by an executive system for robust on-line execution of flexible plans in order to absorb possible delays during the execution. In this regard, it is useful to define quality metrics to evaluate the robustness of flexible timeline-based plans. In this paper, a set of quality metrics for flexible timelinebased plans are defined and discussed when applied to a specific timeline-based framework. In fact, we consider the framework EPSL, developed to support the design of P&S applications, that allows the definition of different planners endowed with specific heuristics. Then, an experimental analysis is presented exploiting the planners to solve planning problem instances related to a real-world manufacturing case study. And, finally, an evaluation of planners performance is presented and discussed comparing results also considering robustness of generated plans.
The Timeline-based approach to planning has been successfully applied in several real
world scenarios, especially in space like contexts [
Analogously, the robustness of a timeline-based plan can be evaluated by means of
similar measures, which are to be defined without relying on the underlying temporal
network (TN). This is particularly important when time flexibility is taken into account.
In fact, representing a flexible timeline-based plan as a TN (or a schedule) entails a sort
of simplification of the associated plan structure causing a lost of information on the
“dependencies” among its components which can usefully be taken into account. Such
information is useful both to generate the plan, as described in [
This paper represents a first step towards the characterization of temporal qualities
of flexible timeline-based plans. After a brief presentation of the basic concepts
underlying flexible timeline-based planning, some of such metrics are introduced. Their
concrete application is shown by using planners implemented in the EPSL
(Extensible Planning and Scheduling Library) framework [
This section briefly introduces the main concepts to define flexible timeline-based plans,
along the lines of [
The evolution of a single temporal feature over a temporal horizon is called the
timeline of that feature. In general, plans synthesized by temporal P&S systems may be
temporally flexible. They are made up of flexible timelines, describing transition events
that are associated with temporal intervals (with given lower and upper bounds), instead
of exact temporal occurrences. In other words, a flexible plan describes an envelope of
possible solutions aimed at facing uncertainty during actual execution. In this regard,
they can be exploited by an executive system for robust execution. Some formalizations
have been recently proposed to describe timelines and timeline-based plans [
Broadly speaking a timeline consists of a sequence of values that are temporally
qualified by means of tokens. A token specifies the temporal interval (start and end
times) assigned to a specific value over a timeline. Flexible tokens specify a flexible
interval for values over timelines (i.e. values have a start interval and end interval, instead
of time points) and, as proposed in [
(xi; v; (b; b0); (e; e0); (d; d0)) where i 2 N; b; b0; e; e0; d 2 T; d0 2 T1; v 2 V; b < e0 and dmin where (dmin; dmax) = D(v). The element xj is the token identifier. d < d0 dmax, Definition 2 A flexible timeline for x is a finite sequence of flexible tokens for x, whose identifiers are x0; x1; :::; xk:
F T Lx = (x0; v0; (b0; b00); (e0; e00); (d0; d00))
:::(xk; vk; (bk; b0k); (ek; e0k); (dk; d0k)) 1, ei = bi+1; e0i = b0i+1 and vi+1 2 T (vi). where b0 = b00 = 0, ek = e0k = H is the temporal horizon of the timeline and for all i = 0; :::; k
A flexible token represents the set of its instances, i.e. the set of all non-flexible tokens that satisfy the value duration constraints. Similarly a flexible timeline F T Lx represents the set of its instances. Namely, an instance of a flexible timeline F T Lx is made up of a sequence of instances of the tokens of F T Lx and an instance of a set FTL of timelines is a set of instances of the timelines in FTL.
However the representation of flexible plans must include also information about the relations that have to hold between tokens in order to satisfy the synchronization rules of the planning domain. Thus, the representation of flexible plans must include also a set of temporal relations on tokens, guaranteeing that such rules are satisfied.
Let us consider two flexible tokens, with token identifiers xi and yk, belonging respectively to the state variables x and y. A synchronization rule of the domain may require that the flexible token xi precedes the flexible token yk. In such a case the set of temporal relations of included in the flexible plan must contain the relations xi before yk (i.e. e0x < by) in order to satisfy the synchronization rule of the domain.
Like in [
Definition 3 A flexible plan over the horizon H is a pair (FTL, R), where FTL is a set of flexible timelines over the same horizon H and R is a set of relations on tokens, involving token identifiers in some timelines in FTL.
A flexible plan represents the set of its instances. An instance of a plan =(FTL, R) is an instance of FTL that respects the relations in R. When there are different ways how a synchronization rule can be satisfied by the same set of flexible timelines FTL, each flexible plan represents a choice among them, and different plans with the same set FLT and different sets of relations R represent different ways to satisfy synchronization rules.
A planner like those described in the following can leave timelines open on the right, i.e. they can leave an undefined temporal interval at the end of a timeline. This means that the planner does not decide which is the temporal evolution of the timeline after its last meaningful token. 3
Given a flexible timeline-based planner it is important to define some metrics that allow to characterize the capacity of the generated plans to absorb temporal deviations, i.e. their robustness. In this section, some quality metrics concerning temporal features of plans are introduced.
There are several works in the literature that define quality metrics for evaluating
plans and planning algorithms [
The timeline fluidity metric is an estimate of the capacity of the timeline to absorb temporal deviations w.r.t. other timelines. It is defined as follows: Definition 4 If F T Lx is a flexible timeline for the state variable x, the fluidity of the timeline w.r.t. the other timelines F T Ly of the plan is (xi;yj) (F T Lx) = Pxi2F T Lx;yj2F T Ly H n (n 1) 100 where xi is a token in the timeline F T Lx, yj is a token in a timeline F T Ly 6= F T Lx, H is the temporal horizon of the plan, and n is the number of tokens involved in the computation.
Fluidity is computed by taking into account the temporal slack between tokens, that is a measure of the temporal flexibility between the end time of a token and the start time of another one: (xi; yj ) = jdmax(xiend; ysjtart) dmin(xiend; ysjtart)j where dmax and dmin are respectively the maximum and minimum allowed temporal distances between the end time of xi and the start time of yj .
The higher is the value of the fluidity of a timeline F T Lx, the higher is the capacity of other timelines of the plan to absorb its temporal deviations. Namely the higher is the value, the lower is the risk of cascading changes on other timelines of the plan. This metric provides a measure of temporal dependencies among the timelines of the plan.
The timeline disruptibility metric measures the amount of changes in a plan caused by the introduction of a delay in a timeline and is defined as follows: Definition 5 If F T Lx is a flexible timeline for the state variable x, the disruptibility of the timeline w.r.t. other timelines F T Ly of the plan is (0;xi) (F T Lx) = n1 Pxi2F T Lx;yj2F T Ly jfyj:yj2 (xi; )gj where xi and yj are token of the timelines F T Lx and F T Ly, respectively. (xi; ) is the set of tokens in the plan that change after the introduction of a delay on the token xi 2 F T Lx.
Disruptibility is computed by taking into account the slack (0; xi) of tokens, which is a measure of the temporal flexibility between the temporal origin of the timeline and the start time of the token.
(0; xi) = jdmax(0; xistart) dmin(0; xistart)j It is a measure of the flexible temporal allocation of the token over the timeline.
The disruptibility metric (F T Lx) counts the number of changes (temporal deviations) in the plan due to a temporal delay on tokens xi of the timeline F T Lx.
Finally the makespan metric of a timeline is a measure of the temporal flexibility between the last (meaningful) token of a timeline and the temporal horizon, when the timeline leaves an undefined temporal interval at its end.
Definition 6 Given a flexible timeline F T Lx for the state variable x with k tokens, the makespan of the timeline is (x) = (xk;H)
H 100 where (xk; H) is the slack between the last token of the timeline xk 2 F T Lx and the horizon H (xi; H) = jdmax(xiend; H) dmin(xiend; H)j It is a measure of the portion of timeline left to be used.
The higher is the value of (F T Lx), the larger is the width of the flexible distance between the last token of F T Lx and the horizon.
In the next section we consider a case study in order to make an experimental evaluations of the different planners we have defined by means of our timeline-based planning framework EPSL. In particular we aim at characterizing qualities of plans generated using different planner configurations. It is also interesting to evaluate relations among the defined metrics as, in some cases, metrics may be in contrast. This means that it is not possible to obtain a plan with the maximum level of all desired qualities but that the planner must be carefully configured in order to obtain the desired balance among all desired qualities 4
EPSL [
EPSL framework
1 APSI-TRF is a software framework developed for the European Space Agency by the Planning and Scheduling Technology Laboratory at CNR (in Rome, Italy).
The Engine layer is the element responsible for managing the portfolio of algorithms, called resolvers, available to EPSL-based planners. Resolver encapsulate the logic for refining timeline-based plans. Each resolver, solves some specific conditions (called flaws) that threat the completeness or correctness of a plan. The set of available resolvers characterizes the expressiveness of the framework. Namely they determine what EPSL-based planners can actually do to solve problems.
Finally the Application layer is the top-most element which carries out the solving process and finds a solution if any. EPSL architecture allows to define modular planner instances which can be configured in different ways according to the particular feature of the problem to address. An EPSL-user configure planners by selecting the elements (e.g. heuristics, strategies and resolvers) that compose the application instance. Similarly the user can also extend EPSL capabilities by integrating domain-specific elements.
EPSL solving approach is a standard plan refinement search procedure which can be adapted to the particular problem to solve by changing the the planner configuration. As a matter of fact the particular strategy or heuristic applied can strongly affect planner behaviour and performances. In particular, the planner has two important choice points during a the search: (i) node selection choice concerning the selection of the search space node to expand next and (ii) flaw selection choice concerning the selection of the flaw to solve next in order to refine the current plan (i.e. node expansion).
We focused our attention on the flaw selection choice which is not a backtracking
point of the search but, in our experience, a crucial aspect to enhance planner
performances. Indeed, a careful selection of the next flaw to solve can prune the search space
by cutting off branches that would not lead to solutions. Flaws can have dependencies,
indeed, and the resolution of a flaw can simplify the resolution of other flaws in the
plan. In this regard, EPSL allows to define heuristics that support the search in selecting
the most promising flaws to solve. Typically these heuristics encapsulate some
evaluation criteria that allow to rate plan flaws by taking into account one or more feature.
In [
A timeline-based domain specifies relations between different timelines by means of synchronization rules. Thus, given a timeline A and a timeline B, a synchronization rule SA;B from a token x 2 A to a token y 2 B implies a dependency between these timelines. Namely, tokens on timeline B are subject to tokens on timeline A.
Therefore, it is possible to build a Dependency Graph (DG) among timelines by
looking at synchronization rules. Figure 2(a) shows a set of timelines with
synchronization rules and Figure 2(b) shows the resulting dependency graph (note that the
dependency graph defined here is different from the graph used in EUROPA2 [
The DG encodes dependencies among timelines, and a hierarchy can be extracted by analysing the graph. An edge from a node A to a node B in the DG represents a dependency between timeline A and timeline B (i.e. tokens of timeline B depend on tokens of timeline A). Consequently the hierarchy level of timeline A is not lower than the hierarchy level of B. If no path in the DG connects B to A, then A is at a higher level in the hierarchy than B (i.e. timeline A is more independent than timeline B). Conversely if A is connected to B and vice-versa in the DG (i.e. a cycle is detected) then timelines A and B have the same hierarchical level, and they are said to be hierarchically equivalent. For instance the hierarchy extracted from the DG in Figure 2 is A C B D.
Usually planning domain specifications that follow a hierarchical modeling
approach (like the approach described in [
SA,C
SA,B A B
SC,B C
SC,D D (a)
SB,D
A
SA,B SA,C
B
SB,D (b)
SC,B C
SC,D
D
The HFS exploits this hierarchy to define a flaw hierarchy feature and characterize the independency degree of plan flaws. The idea is to solve first “independent” flaws, i.e. flaws belonging to the top most timeline in the hierarchy (e.g. flaws on timeline A w.r.t. Figure 2), in order to simplify the resolution of “dependent” flaws. In addition to the hierarchy feature, HFS uses a flaw type feature to define a structure for the solving process and the flaw degree feature to characterize the criticality of a flaw (similarly to the fail first principle in constraint satisfaction problems).
The HFS selects the best flaw to solve next by combining together all the features described above as a pipeline of filters: 0( ) f!h 1( ) f!t 2( ) f!d 3( ) ! 2 3( ) where fh filters plan flaws according to the flaw hierarchy feature (i.e. it returns only the subset of flaws belonging to the most independent timeline of the hierarchy), ft filters flaws according to the flaw type feature and fd filters flaws according to the flaw degree feature. Then, given a set of flaws of a plan 0( ) every filter extracts the subset of the relevant flaws according to the related feature. The pipeline resulting set 3( ) 0( ) is composed by flaws representing equivalent choices from the heuristic point of view, so HFS randomly select the “best” one to solve next 2 3( ).
The objective of the experimental analysis is to evaluate flexible timeline-based plans generated by EPSL-based planners with different configurations. In particular we evaluate plans by considering the fluidity and makespan metrics3 as well as the planners time performances. In this regards, we use two configurations of EPSL-based planners by selecting two different heuristic functions: (i) the HFS planner, using the HFS heuristic; (ii) the TFS planner (Type Flaw Selection planner), which uses a heuristic function based only on the flaw type feature to select flaws (configuration used before the introduction of the HFS heuristc). 5.1
Here, we consider a pilot plant involved in an on-going research project called Generic
Evolutionary Control Knowledge-based mOdule (GECKO): a manufacturing system for
Printed Circuit Boards (PCB) recycling [
The pilot plant contains 6 working machines (M1,..., M6) that are connected by means of a Reconfigurable Transportation System (RTS), composed of mechatronic components, i.e., transport modules. Figure 3(a) provides a picture of a transport module. Each module combines three transportation units. The units might be either unidirectional or bidirectional; specifically the bidirectional units enable the lateral movement (i.e., cross-transfers) between two transportation modules. Thus, each transport module can support two main (straight) transfer services and one to many cross-transfer services. Figure 3(b) depicts two possible configurations.
Configuration 1 supports the forward (F) and backward (B) transfer capabilities as well as the left (LC1) and right (RC1) cross transfer capabilities. Configuration 2 extends Configuration 1 by integrating a further bidirectional transportation unit with cross transfer capabilities LC2 and RC2. The maximum number of bidirectional units within a module is limited just by its straight length (three, in this particular case). The transport modules can be connected back to back to form a set of different conveyor layouts. The manufacturing process requires PCBs to be loaded on a fixturing system (pallet) in order to be transported and processed by the machines. The transportation system is to move one or more pallets and each pallet can be either empty or loaded with a PCB to be processed.
Such an RTS generally allows for a number of possible routing solutions for each single pallet which is associated to a given destination. Transport modules control systems have to cooperate in order to define the paths the pallets have to follow to reach their destinations. These paths are to be computed at runtime, according to the actual status and the overall conditions of the shop floor (i.e., no static routes are used to move pallets).
3 In this preliminary experimental analysis, disruptibility metric does not provide relevant data ! C B 2 C R 2 C R 2CR2 B R 2CL2C B L2C BB !! L 2 C L 2 R C L2 F ARU
IIFT1CARUGOONNIIFT1CARUGOONNIIFT1CARUGOONNIIFT2CARUGOONNIIFT1CARUGOONNIIFT2CARUOONNIIFT2CARUGOONNIIFT2CARUGOONNIIFT2CARUGOON FFFFFFFFF 1CL1CRL11CCRL11CCRL11CCRL11CRL11CCRL11CCRL11CCRL11CCR (a) IFCGON (bL1C)
ITO R
Fig. 3. (a) A transport module; (b) The1Nir transfer s1Cervices
The description of the distributed architecture and some experimental results
regarding the feasibility of the distributed approach w.r.t. the part routing problem can be
found in [
Figure 4 shows the timeline-based model of a generic transportation module (TM) of the GECKO case study extended with energy consumption resource to estimate energy consumption profile of transportation tasks. The Channel state variable models the high-level transporting tasks the TM is able to perform. Each value of the Channel state variable models a particular transportation task indicating the ports of the module involved in the execution of the task. For instance Channel F B models the task of transporting a pallet form port F to port B w.r.t. Figure 3(b).
The Change-Over state variable models the set of internal configuration the transportation module can assume in order to actually exchange pallets with other modules.
Namely configurations identify the internal paths a pallet can follows to traverse the module. For instance, CO F B in Figure 4 represents the configuration needed to transport a pallet from port F to port B.
The Energy-Consumption resource models the energy consumption policy o the TM. It estimates the energy consumption of transportation tasks of the module, i.e. the energy requirements for channel activities of the module. Activities such as moving conveyors or cross transfers require energy to be performed and we model a system requirement which entails that the instant energy consumption of TMs cannot exceed a predefined limit for safety and optimization reasons of the physical device. In this way, the planner must organize activities in order to not violate the energy consumption constraint of the module.
B B B B ! ! Idle
Available Neighbor-‐B
Channel_F_B
...
Channel_B_F
Channel_R1_L3 Neighbor-F
Neighbor-‐R
Not Available
Neighbor-‐L
A set of external state variables complete the domain by modeling possible states of TM’s neighbor modules. Neighbors are modeled by means of external state variables because they are not under the control of the module. Namely, the TM cannot decide the state of its neighbors. However it is important to monitor their status because a TM must cooperate with them in order to successfully carry out its tasks. For instance the TM must cooperate with Neighbor F and Neighbor B to successfully perform a Channel F B task. Therefore Neighbor F and Neighbor B must be Available during task “execution”.
Finally a set of synchronization rules specify how a TM implements its channel tasks. Figure 4 groups these rules in the dotted arrows between state variables for readability reasons. These rules specify operative constraints (causal and temporal constraints) describing the sequence of internal configurations and “external” conditions needed to safely perform Channel tasks. For instance, a synchronization rule for the Channel F B task require that the module must be set in configuration CO F B and that neighbor F and neighbor B must be Available during the “execution” of the task. 5.2
In the GECKO case study we have defined four planning domain variants by considering different physical configurations of a TM of the manufacturing plant, i.e., by varying the number of cross-transfer units composing the module and under the assumption that module’s neighbors are always available for cooperation. Namely, the tests were run on the following planning domains: (i) simple, the configuration with no cross transfer; (ii) single, the configuration with only one cross transfer unit; (iii) double, the configuration with two cross transfer units; (iv) full, the configuration with three cross transfer units (the maximum allowed in the case study we considered). The higher is the number of available cross transfers, the higher is the number of elements and constraints the planner has to deal with at solving time. 70"
The charts in Figure 5 show the solving time trends of the EPSL-based planners (within a timeout of 180 seconds) w.r.t. the growing dimension of the planning problem (i.e. a growing number of goals) and the growing complexity of the module to control (i.e. the number of available cross transfers). The results show that the HFS planner dominates TFS planner on the considered planning domains. The introduction of the HFS heuristic in the solving process entails a general improvement of the performances in terms of both solving time and scalability of framework.
Let us consider the subset of problems solved by both HFS and TFS planners in Figure 5 and make a comparison of generated plans. Figure 6 compares the generated plans by considering the fluidity metric previously introduced.
The chart in Figure 6(a) shows the trend of the fluidity of the plans w.r.t. the growing complexity of the addressed problems in terms of number of goals and constraints to manage. Results show that the higher is the complexity of the problems the lower is the amount of fluidity of the generated plans. Thus, as expected, the higher is the number of tokens on timelines the higher is the probability that a temporal deviation on a token causes temporal deviations on tokens of other timelines.
The charts in Figure 6(b) and (c) compare respectively the total fluidity and the average makespan of the generated plans. Results show that TFS planner generates plans more robust than HFS planner w.r.t. fluidity metric. The total fluidity of the plans generated by TFS planner, indeed, is higher than the total fluidity of the plans generated by HFS planner. Thus, the introduction of HFS heuristic in the solving process seems to 70 60 50 40 30 20 10 0 70" lead to a loss of the robustness of the generated plans despite a significant improvement of the solving capabilities as shown in Figure 5.
This can be explained by considering that the TFS planner maintains a “complete” view of the plan during the solving process. The planner reasons about the overall plan by taking into account all the timelines of the domain, so that it can organize the tokens on timelines as best as it can. Conversely, the HFS planner maintains a “local” view of the plan which is related to single timelines of the domain. Namely, the HFS planner builds one timeline at a time. Therefore, when the planner must manage “intermediate” timelines, its choices are partially constrained by the choices made before.
This behavior of HFS heuristic can lead also to a loss of performances in some specific cases such as the simple domain in Figure 5(a). The chart shows that, despite the general trend, the TFS planner performs better than HFS planner in the simple domain. Because of its “local” approach, the HFS planner is not able to effectively organize tokens on timelines as TFS planner does. In particular TFS planner is able to efficiently group tokens of channel timeline requiring the same configuration of the module, i.e. the same type of token on the change-over timeline. Conversely the HFS reasons on one timeline at a time, so it is not able to group tokens requiring the same configuration on channel timelines. As a consequence the planner must manage much more tokens on the change-over timeline increasing the complexity of the problem resolution. change-‐over fluidity HFS TFS (a) change-‐over makespan HFS TFS (b) channel energy channel energy Fig. 7. Comparison of plans generated for the simple domain on: (a) the total fluidity, (b) the average makespan HFS$overall$fluidity$
As a matter of fact the chart of Figure 7(a) shows that the fluidity of the change-over timeline in the TFS generated plans is quite higher than the fluidity of the same timeline in the HFS generated plans.
Finally the introduction and analysis of temporal metrics allow also to extract useful information about planning domains. Let us consider the contribution of single timelines to the total fluidity of the generated plans shown in Figure 8.
channel' change)over'
energy' HFS overall fluidity
TFS overall fluidity (a) (b)
It is possible to see that, regardless the heuristic applied during the solving process, the relationships among domain timelines remain constant. The charts in Figure 8, show that, in general, the energy timeline is the one with the highest value of fluidity while the channel timeline is the one with the lowest value of fluidity. Thus, the channel timeline is the most critical one w.r.t. the robustness of the plan. Namely a temporal deviation on a token of the channel timeline is more likely to produce side effects on other timelines of the domain than tokens on other timelines. This sort of information is very interesting since they can be used to classify planning domains and introduce some learning mechanism to adapt the solving process to the specific features of a planning domain.
In this paper we have presented our preliminary work about the introduction of quality metrics to evaluate the robustness of flexible timeline-based plans. In particular, we have adapted some temporal metrics defined in scheduling to timelines. Then we have introduced EPSL, a timeline-based planning framework we use to design and develop P&S applications. Finally we made an experimental evaluation of two EPSL-based planners on a manufacturing case study.
Experimental results have shown how temporal metrics allow to make an assessment of the heuristics applied during the solving process. In particular, temporal metrics let us able to evaluate EPSL-based planners both from the solving performance and the plan quality point of views. An important issue to be addressed in future works is the introduction of a “dynamic” measure of flexibility in order to make a deeper analysis and assessment of the robustness of a plan. In particular we believe that an analysis of this sort is especially needed to provide a valid estimate of the disruptibility metric. Another objective is to develop some parametrized search heuristics heuristcs allowing to exploit temporal features of (partial-)plans during the solving process.
Moreover the experimental results have shown that these metrics charaterize information about the structure and relationships among domain timelines. Thus, another interesting future goal is to introduce some learning mechanism for dynamically adapting heuristics to the specific features of the problem to address.
Acknowledgments. Andrea Orlandini is partially supported by the Italian Ministry for University and Research (MIUR) and CNR under the GECKO Project (Progetto Bandiera “La Fabbrica del Futuro”).