Quality Metrics to Evaluate Flexible Timeline-based Plans Alessandro Umbrico1 , Andrea Orlandini2 , Marta Cialdea Mayer1 1 Dipartimento di Ingegneria Università degli Studi Roma Tre 2 Istituto di Scienze e Tecnologie della Cognizione Consiglio Nazionale delle Ricerche, Roma Abstract. Timeline-based Planning has been successfully applied in several con- texts 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 tempo- ral 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 timeline- based 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 en- dowed with specific heuristics. Then, an experimental analysis is presented ex- ploiting 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 gener- ated plans. 1 Introduction The Timeline-based approach to planning has been successfully applied in several real world scenarios, especially in space like contexts [1,2,3,4]. Besides these applications, several timeline-based Planning and Scheduling (P&S) systems have been deployed to define domain specific applications, see for example E UROPA [5], I X T E T [6], A PSI - T RF [7]. Like in classical planning [8], it is important to consider different aspects of the plans generated by timeline-based P&S systems, in order to evaluate their quality. Some temporal metrics have been defined in the literature for temporal networks (often used to represent timeline-based plans) and scheduling [9,10]. In general these met- rics characterize the robustness of a schedule by considering the temporal constraints between its activities. 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 [11], and to make a more detailed analysis of the temporal features which are relevant to evaluate the overall plan robustness. For instance, some timeline in the plan can “dominate” the behavior of other timelines, since its temporal deviations are most likely to propagate to the others. 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 un- derlying flexible timeline-based planning, some of such metrics are introduced. Their concrete application is shown by using planners implemented in the E PSL (Extensi- ble Planning and Scheduling Library) framework [12]. E PSL is a domain independent, modular and extensible software environment supporting the development of timeline- based applications. Recently, some improvements concerning the representation and solving capabilities of E PSL have been presented in [11]. Specifically, the framework is enriched with the capability to model and reason on renewable resources and domain independent heuristics supporting the planning process. The general structure of E PSL allows for preserving “past experiences” by providing a set of ready-to-use algorithms, strategies and heuristics that can be combined together. In this way, it is possible to develop and evaluate different solving configurations in order to find the one which better addresses the features of the particular planning problem to be solved. This paper resorts to the E PSL framework and its application to a real-world manufacturing case study, in order to evaluate and compare the performances of planners using different heuristics and the robustness of the generated plans. 2 Flexible Timeline-based Planning This section briefly introduces the main concepts to define flexible timeline-based plans, along the lines of [13]. The timeline-based approach to P&S aims at controlling a com- plex system by synthesizing temporal behaviors of its features in terms of timelines. A planning domain is modeled as a set of features, represented by multi-valued state vari- ables, that must be controlled over time. Causal and temporal constraints specify, for each feature, the set V of the values the variable may assume, the allowed value transi- tions (by means of a function T : V → 2V ), and the allowed minimum and maximum duration of each valued interval (by means of a function D associating to each value v ∈ V a pair of time values). Moreover, the values of different state variables may be linked by (so-called) synchronization rules, requiring that, for every time interval where a given state variable x has the value v, there exist other time intervals where either the same or other state variables assume some given values, which are related by some temporal relation. All these constraints are specified in the domain specification. The planning process aims at synthesizing temporal flexible plans that satisfy the domain constraints and fulfill some given goals. 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 [13,14]. 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 in- terval for values over timelines (i.e. values have a start interval and end interval, instead of time points) and, as proposed in [13], they can be defined as follows (where T is the set of “time points” and T∞ denotes T ∪ {∞}): Definition 1 Let x = (V, T, D) be a state variable describing the set of allowed values V , the value transition function T and the value duration function D for a domain feature. A flexible token for the state variable x is a tuple of the form (xi , v, (b, b0 ), (e, e0 ), (d, d0 )) where i ∈ N, b, b0 , e, e0 , d ∈ T, d0 ∈ T∞ , v ∈ V, b < e0 and dmin ≤ d < d0 ≤ dmax , where (dmin , dmax ) = D(v). The element xj is the token identifier. 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 )) where b0 = b00 = 0, ek = e0k = H is the temporal horizon of the timeline and for all i = 0, ..., k − 1, ei = bi+1 , e0i = b0i+1 and vi+1 ∈ T (vi ). 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 y k , belonging re- spectively to the state variables x and y. A synchronization rule of the domain may require that the flexible token xi precedes the flexible token y k . In such a case the set of temporal relations of included in the flexible plan must contain the relations 0 xi before y k (i.e. ex < by ) in order to satisfy the synchronization rule of the domain. Like in [15], a small set of primitive temporal relations can be considered, in terms of which all the usual quantitative constraints can be defined, such as, for instance, the relations xi contains[lb1 ,ub1 ][lb2 ,ub2 ] y k and xi overlaps[lb1 ,ub1 ][lb2 ,ub2 ] y k (where lbj ∈ T and ubj ∈ T∞ , for j = 1, 2) . 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 Characterizing Robustness for Timeline-based Plans 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 [8,16,17,18]. In this regards we consider temporal met- rics such as fluidity and disruptibility (introduced by [9] to characterize the robustness of schedules on temporal networks), in order to check temporal flexibility and provide an assessment of the robustness of timeline-based plans. In particular we adapt fluid- ity and disruptibility metrics to timelines and define the notion of the makespan of a timeline to indicate the “useful” portion of a timeline. Note that the term “makespan” is typically used in scheduling problems to express the maximum duration of a schedule. Here, we are using the same term with a slightly different meaning. 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 P ρ(xi ,y j ) ξ(F T Lx ) = xi ∈F T Lx ,y j ∈F T Ly H×n×(n−1) × 100 where xi is a token in the timeline F T Lx , y j 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: j j ρ(xi , y j ) = |dmax (xiend , ystart ) − dmin (xiend , ystart )| where dmax and dmin are respectively the maximum and minimum allowed temporal distances between the end time of xi and the start time of y j . 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 P xi ∈F T Lx ,y j ∈F T Ly |{y j :y j ∈∆(xi ,δ)}| where xi and y j 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 ∈ 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 ) = |dmax (0, xistart ) − dmin (0, xistart )| 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 devia- tions) 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 k µ(x) = ρ(xH,H) × 100 where ρ(xk , H) is the slack between the last token of the timeline xk ∈ F T Lx and the horizon H ρ(xi , H) = |dmax (xiend , H) − dmin (xiend , H)| 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 evalua- tions of the different planners we have defined by means of our timeline-based planning framework E PSL. In particular we aim at characterizing qualities of plans generated us- ing 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 Extensible Planning and Scheduling Library E PSL [12] is a layered framework built on top of A PSI -T RF1 [7]. It aims at defining a flexible software environment for supporting the design and development of timeline- based applications. The key point of E PSL flexibility is its interpretation of a planner as a “modular” solver which combines together several elements to carry out its solving process. EPSL  framework   Applica>on   Search   Engine   Heuris>cs   Microkernel   Modeling  Layer  -­‐  APSI-­‐TRF   Fig. 1. E PSL Architectural Overview Figure 1 describes the main architectural elements of the architecture of E PSL. The Modeling layer provides E PSL with timeline-based representation capabilities to model a planning domain in terms of timelines, state variables, synchronizations and manage flexible plans. The Microkernel layer is the key element which provides the framework with the needed flexibility to “dynamically” integrate new elements into the framework. It is responsible to manage the lifecycle of the solving process and the elements com- posing the application instances (i.e. the planners). The Search layer and the Heuristics layer are the elements responsible for managing strategies and heuristics that can be used during the solving process. 1 A PSI -T RF 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 algo- rithms, called resolvers, available to E PSL-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 E PSL-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. E PSL architecture allows to define modular plan- ner instances which can be configured in different ways according to the particular feature of the problem to address. An E PSL-user configure planners by selecting the el- ements (e.g. heuristics, strategies and resolvers) that compose the application instance. Similarly the user can also extend E PSL capabilities by integrating domain-specific el- ements. E PSL 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 perfor- mances. 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, E PSL allows to define heuristics that support the search in selecting the most promising flaws to solve. Typically these heuristics encapsulate some evalu- ation criteria that allow to rate plan flaws by taking into account one or more feature. In [11], we developed a domain independent heuristic, called Hierarchical Flaw Se- lection heuristic (H FS), which rate flaws by analyzing the hierarchical structure of a timeline-based domain. 4.1 Hierarchical Flaw Selection heuristic 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 ∈ A to a token y ∈ 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 synchro- nization 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 [19]). 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 ap- proach (like the approach described in [11]), generate a non-flat hierarchy of timelines (and sometimes even an acyclic DG). A   SA,C   SA,B   SA,B   B SB,D B   SC,B   SB,D   D A SC,B   C   SC,D   SA,C   SC,D   D   C (a) (b) Fig. 2. From Synchronization rules to Dependecy Graph: (a) domain timelines and synchroniza- tion rules; (b) the dependency graph resulting from synchronization rules between timelines The H FS 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, H FS 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 H FS selects the best flaw to solve next by combining together all the features described above as a pipeline of filters: fh ft fd Φ0 (π) −→ Φ1 (π) −→ Φ2 (π) −→ Φ3 (π) → φ∗ ∈ Φ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 H FS randomly select the “best” one to solve next φ∗ ∈ Φ3 (π). 5 Experimental Evaluation The objective of the experimental analysis is to evaluate flexible timeline-based plans generated by E PSL-based planners with different configurations. In particular we evalu- ate plans by considering the fluidity and makespan metrics3 as well as the planners time performances. In this regards, we use two configurations of E PSL-based planners by selecting two different heuristic functions: (i) the HFS planner, using the H FS heuris- tic; (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 intro- duction of the H FS heuristc). 5.1 A pilot plant Here, we consider a pilot plant involved in an on-going research project called Generic Evolutionary Control Knowledge-based mOdule (G ECKO): a manufacturing system for Printed Circuit Boards (PCB) recycling [20]. The objective of the system is to analyze defective PCBs, automatically diagnose their faults and, depending on the gravity of the malfunctions, attempt an automatic repair of the PCBs or send them directly to shredding. 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 mod- ule. Each module combines three transportation units. The units might be either uni- directional or bidirectional; specifically the bidirectional units enable the lateral move- ment (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 sys- tems 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 1 1 1 1 RC1RC1 RC1RC1 CONFIGURATION CONFIGURATION F B 2 CONFIGURATION F B 2 2 CONFIGURATION F B LC1 LC1LC1 F B 2 2CL RC2RC2 RC2RC2 LC1RC1 UGICONFIGURATION CR LC1 LC1LC11CL RC1RC1 RC1 ITARCONFIGURATION F B NOCONFIGURATION F B ! 2CONFIGURATION FNOC F B R LC2 LC2LC2 F B ! F B ! ! 2CLC2 1LC1 ! 1CL 1 NOITARUGIFNOC (a) (b) F B 1CR Fig. 3. (a) A transport module; (b) Their transfer services The description of the distributed architecture and some experimental results re- garding the feasibility of the distributed approach w.r.t. the part routing problem can be found in [21]. Transportation Modules (TMs) rely on P&S technology to synthesize activities for supporting the work flow within the shop floor. As a matter of fact TM agents are endowed with Timeline-based planners (build on top of E PSL framework) that assess modules’ internal capabilities during the part routing computation process and build modules’ plans for coordination and transportation task. Figure 4 shows the timeline-based model of a generic transportation module (TM) of the G ECKO case study extended with energy consumption resource to estimate en- ergy 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 mod- ule 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 trans- portation 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 trans- port 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. Channel_F_B   Channel Energy-Consumption Channel_R1_L3   MAX Idle   ... Channel_B_F   CO_R1L1   CO_R3L3   Available   Not   ... Available   CO_FB   Neighbor-F Neighbor-­‐B   Neighbor-­‐L   Change-Over Changing   Neighbor-­‐R   Fig. 4. Timeline-based model for a full instantiated TM 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 read- ability reasons. These rules specify operative constraints (causal and temporal con- straints) 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 Evaluating Plan Robustness In the G ECKO 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. HFS" TFS" TLFS" DFS" RFS" 180   70" 180   Solving  )me  (in  seconds)   Solving  )me  (in  seconds)   160   160   solving()me((in(seconds)( 140   140   120   60" 120   100   100   80   60   50" 80   60   40   40   20   40" 20   0   0   1   2   3   4   5   6   7   8   9   10   1   2   3   4   5   6   7   8   9   10   30" number  of  goals   number  of  goals   20" (a) (b) 180   10" 180   Solving  )me  (in  seconds)   Solving  )me  (in  seconds)   160   160   140   120   0" 140   120   100   80   1" 2" 3" 100   80   4" 5" 6" 7" 9" 9" 10" number(of(goals( 60   60   40   40   20   20   0   0   1   2   3   4   5   6   7   8   9   10   1   2   3   4   5   6   7   8   9   10   number  of  goals   number  of  goals   (c) (d) Fig. 5. HFS and TFS planners performances on: (a) simple configuration; (b) single configuration; (c) double configuration; (d) full configuration The charts in Figure 5 show the solving time trends of the E PSL-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 H FS 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 H FS heuristic in the solving process seems to HFS" TFS" TLFS" DFS" RFS" 70   70" solving()me((in(seconds)( 60   60" 50   50" 40   40" 30   20   30" 10   20" 0   10" g1   g2   g3   g4   g1   g2   g3   g4   g1   g2   g3   g4   g1   g2   g3   g4   0" simple   single   double   full   1" 2" (a) 3" 4" 5" 6" 7" 9" 9" 10" number(of(goals( 200   100   198   90   80   196   70   194   60   192   50   190   40   30   188   20   186   10   184   0   fluidity   makespan   (b) (c) Fig. 6. Comparison of HFS and TFS planners on: (a) plan fluidity trend; (b) total plan fluidity; (c) average plan makespan 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 H FS 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. 40   100   35   90   80   30   70   25   60   20   50   15   40   30   10   20   5   10   0   0   channel   change-­‐over   energy   channel   change-­‐over   energy   fluidity   makespan   HFS   TFS   HFS   TFS   (a) (b) HFS$overall$fluidity$ Fig. 7. Comparison of plans generated for the simple domain on: (a) the total fluidity, (b) the average makespan 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 time- lines to the total fluidity of the generated plans shown in Figure 8. channel' change)over' energy' HFS  overall  fluidity   TFS  overall  fluidity   (a) (b) Fig. 8. Contribution of the single timelines to the overall plan fluidity for (a) HFS generated plans and (b) TFS generated plans 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. 6 Conclusions and Future works 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 intro- duced E PSL, a timeline-based planning framework we use to design and develop P&S applications. Finally we made an experimental evaluation of two E PSL-based planners on a manufacturing case study. Experimental results have shown how temporal metrics allow to make an assess- ment of the heuristics applied during the solving process. In particular, temporal metrics let us able to evaluate E PSL-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 infor- mation about the structure and relationships among domain timelines. Thus, another interesting future goal is to introduce some learning mechanism for dynamically adapt- ing 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”). References 1. Muscettola, N.: HSTS: Integrating Planning and Scheduling. In Zweben, M. and Fox, M.S., ed.: Intelligent Scheduling. Morgan Kauffmann (1994) 2. Jonsson, A., Morris, P., Muscettola, N., Rajan, K., Smith, B.: Planning in Interplanetary Space: Theory and Practice. In: Proceedings of the 5th International Conference on AI Planning and Scheduling (AIPS). (2000) 3. Cesta, A., Cortellessa, G., Denis, M., Donati, A., Fratini, S., Oddi, A., Policella, N., Rabenau, E., Schulster, J.: MEXAR2: AI Solves Mission Planner Problems. IEEE Intelligent Systems 22(4) (2007) 12–19 4. Ceballos, A., Bensalem, S., Cesta, A., de Silva, L., Fratini, S., Ingrand, F., Ocón, J., Orlan- dini, A., Py, F., Rajan, K., Rasconi, R., van Winnendael, M.: A Goal-Oriented Autonomous Controller for space exploration. In: Proceedings of the 11th Symposium on Advanced Space Technologies in Robotics and Automation (ASTRA). (2011) 5. Barreiro, J., Boyce, M., Do, M., Frank, J., Iatauro, M., Kichkaylo, T., Morris, P., Ong, J., Remolina, E., Smith, T., Smith, D.: EUROPA: A Platform for AI Planning, Scheduling, Constraint Programming, and Optimization. In: ICKEPS 2012: the 4th Int. Competition on Knowledge Engineering for Planning and Scheduling. (2012) 6. Ghallab, M., Laruelle, H.: Representation and control in ixtet, a temporal planner. In: AIPS. Volume 1994. (1994) 61–67 7. Cesta, A., Fratini, S.: The Timeline Representation Framework as a Planning and Scheduling Software Development Environment. In: PlanSIG-08. Proc. of the 27th Workshop of the UK Planning and Scheduling Special Interest Group, Edinburgh, UK, December 11-12. (2008) 8. Roberts, M., Howe, A., Ray, I.: Evaluating diversity in classical planning. In: Proceedings of the 24th International Conference on Planning and Scheduling (ICAPS). (2014) 9. Policella, N., Smith, S.F., Cesta, A., Oddi, A.: Generating robust schedules through temporal flexibility. In: ICAPS. Volume 4. (2004) 209–218 10. Cesta, A., Oddi, A., Smith, S.F.: Profile-based algorithms to solve multiple capacitated metric scheduling problems. In: AIPS. (1998) 214–223 11. Umbrico, A., Orlandini, A., Cialdea Mayer, M.: Enriching a timeline-based planner with resources and hierarchical reasoning. In: Proceedings of the 14th Conference of the Italian Association for Artificial Intelligence (AIxIA). (2015) To appear. 12. Cesta, A., Orlandini, A., Umbrico, A.: Toward a general purpose software environment for timeline-based planning. In: 20th RCRA International Workshop on” Experimental Evalua- tion of Algorithms for solving problems with combinatorial explosion. (2013) 13. Cialdea Mayer, M., Orlandini, A., Umbrico, A.: A formal account of planning with flexible timelines. In: The 21st International Symposium on Temporal Representation and Reasoning (TIME), IEEE (2014) 37–46 14. Cimatti, A., Micheli, A., Roveri, M.: Timelines with temporal uncertainty. In: AAAI. (2013) 15. Cialdea Mayer, M., Orlandini, A.: An executable semantics of flexible plans in terms of timed game automata. In: The 22st International Symposium on Temporal Representation and Reasoning (TIME). (2015) To appear. 16. Benton, J., Coles, A.J., Coles, A.: Temporal planning with preferences and time-dependent continuous costs. In: Proceedings of the 22nd International Conference on Automated Plan- ning and Scheduling (ICAPS). Volume 77. (2012) 78 17. Smith, D.E.: Choosing objectives in over-subscription planning. In: Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS). Volume 4. (2004) 393 18. Nau, D., Ghallab, M.: Measuring the performance of automated planning systems. Technical report, DTIC Document (2004) 19. Bernardini, S., Smith, D.E.: Towards search control via dependency graphs in europa2 (2010) 20. Borgo, S., Cesta, A., Orlandini, A., Rasconi, R., Suriano, M., Umbrico, A.: Towards a coop- erative -based control architecture for a reconfigurable manufacturing plant. In: 19th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA 2014), IEEE (2014) 21. Carpanzano, E., Cesta, A., Orlandini, A., Rasconi, R., Valente, A.: Intelligent dynamic part routing policies in plug&produce reconfigurable transportation systems. CIRP Annals - Manufacturing Technology 63(1) (2014) 425 – 428