One of the features that allowed classical planners to eficiently solve large problems is the ability their heuristics to prune large portions of the search space. These heuristics, however, by addressing classical approaches, do little to support the resolution of problems in which the temporal components are relevant and, even more so, they are not directly suitable for timeline-based approaches to automated planning. This paper takes advantage of some pruning techniques to increase the eficiency of timeline-based planning problems resolution. The elimination of some choices estimated as not very advantageous, in particular, allows the use of inference techniques to reduce the number of decisions to be made, reducing the risk of running into dead ends and, consequently, increasing the resolution eficiency of the solvers.
The introduction of domain independheenutristics within the Automated
Plannin1]gc[ommunity immediately allowed solvers to eficiently solve large instances of complex problems. The
ℎ
diferent approaches that make up a solver’s paraphernalia, range from the seℎminaanl d
[
While the above heuristics are significantly heterogeneous among them (although, often,
they share some commonalities), they have in common the fact that they have been developed
specifically for the resolution of a particular type of problem, characterized by a specific modeling
language called PDDL1[
CEUR Workshop Proceedings the development of heuristics for reasoning with these more expressive formal systems has remained relatively limited to a few cases (e1.9g,.,2[0]).
Timeline-based planning2[
Timeline-based planning constitutes a form of deliberative reasoning which, in an integrated way,
allows to carry out diferent forms of semantic and causal reasoning. Although this approach
to planning has mostly been relegated to forms of causal reasoning in the space domain, many
solvers have been proposed over the time like, for examXpTleET,I[25], Europa [26], Aspen
[27], theTrf [28, 29] on which the APSI framework30[] relies and, more recently, PLATINUm
[31]. Some theoretical works on timeline-based planning 3li2k,e26[] were mostly dedicated
to identifying connections with classical planning a-la P1D5]D. LT[he work onXITET andTrf
has tried to clarify some keys underlying principles but mostly succeeded in underscoring the
role of time and resource reasoni3n3g, 3[
Given the mentioned link with the heuristics we will refer, in this paper, to the timeline-based planning formalization as defined in24[]. According to this formalization, specifically, the basic building block of timeline-based planning is ttohkeen which, intuitively, is used to represent the single unit of information. Through their introduction and their constraining during the planning process, in particular, tokens allow to represent the diferent components of the high-level plans. In its most general form, a token is formally described by an expression like ( 0, … , ) . In particular, is apredicate symbol, 0, … , are itsparameters (i.e., constants, numeric variables or object variables) a∈nd{ , } is a constant representing the class of the (a) An inconsistent state-variable timeline. The ifrst token and th e token are temporally overlapping. The inconsistency can be (b) A consistent reusable-resource timeline. The croemnsotvreadi,nfotr. example, by introducing1a≤ 2 soivmeurllatapnoefotuoskuesnesoifstahlelorweesoduarsceloins glesasstthhaen its capacity. token (i.e., eitherfaact or agoal).
The token’s parameters are constituted, in general, by the variabcolensstorafiant network
(refer to4[
Similarly to CLP, through the application of the rules it is hence possible to establish and generate relationships among tokens. Compared to CLP, however, timelines introduce an added value: some tokens may be equipped with a special object var iatbhleat identifies thetimeline afected by the token. Diferent tokens with the same value for tphaerameter, in particular, afect the same timeline and, depending on the nature of the timeline, might interact with each other. There can, indeed, be diferent types of timelines. In casteaotef-variable timelines (see Figure1a), for example, diferent tokens on the same state-variable cannot temporally overlap. In case ofreusable-resource timelines (see Figur1eb), on the contrary, tokens represent resource usages and can, hence, overlap as long as the concurrent uses remain below the resource’s capacity.
Given the ingredients mentioned above we can now formally introduce the addressed planning problem. Atimeline-based planning problem, specifically, is a triple = (O, ℛ, r), whereO is a set of typed objects, needed for instantiating the initial domains of the constraint network variables and, consequently, the tokens’ parameℛteriss,a set of rules anrdis a requirement. Intuitively, a solution to such a problem should be described by a set of tokens whose parameters assume values so as to guarantee the satisfaction of all the constraints imposed by the problem’s requirement, by the application of the rules, as well as by the cumulative constraints imposed by the timelines. Unfortunately, the previous definition, although intuitive, is not easily translatable into a reasoning process which guarantees its achievement starting from the definition of the planning problem. For this reason, just like common partial-order planners, timeline-based planners often rely on the concepts oflafw andresolver. The planner, in particular, internally maintains a data structure, catolkleedn network, which represents a partial pla=n ( , ), where is a set of tokens whose parameters are constrained by the constraint n.etwork During the resolution process, the reasoner incrementally refines the current token network by identifying its flaws and by solving them through the application of resolvers, while maintaining consistent the constraint.s of
There can be, in general, diferent types of flaws, each resolvable by applying the corresponding resolvers. The achievement of a goal, for example, can take place either through the application of a rule or througuhnaification with either a fact or another already achieved goal with the same predicate (i.e., the parameters of the current goal and the token with which is unifying are constrained to be pairwise equal). In case of disjunctions, introduced either in the initial problem or by the application of a rule, a disjunct must be chosen. The domain of all the variables that make up the token parameters must be reduced to a single allowed value. Finally, timelines must be consistent, possibly requiring the introduction of constraints which prevent not allowed overlaps. Thanks to the introduction of the flaw and resolver concepts, it is therefore possible to provide an implementable definition of solution. Specificaslloyl,uation to a timeline-based planning problem is a flawless token network whose constraint network is consistent.
Finding a solution to a timeline-based planning problem is far from simple. Choosing the right flaw and the right resolver, in particular, constitutes a crucial aspect for coping with the computational complexity and hence eficiently generating solutions. Taking a cue from classical planning heuristic2s4,][ describes how, by building caausal graph and by analyzing its topology, it is possible to estimate the costs for the resolution of the flaws and for the application of the resolvers. Flaws and resolvers, in particular, are seen as if they are, respectively, classical planning propositions and actions. Similarly to a proposition added by the positive efect of an action, in particular, the efect of applying a resolver is the resolution of a flaw. Additionally, just like the preconditions in a classical action, further flaws can be introduced in the case of the application of a rule or the choice of a disjunct in a disjunction. Starting from the initial facts, with a zero estimated resolution cost, the cost of applying a resolver can be estimated as an intrinsic cost of the resolver plus the maximumℎc osth(euristic). The cost of resolving a flaw, on the other hand, is given by the minimum cost of its resolvers. Starting from the top-level goals present in the planning problem, initially estimated with infinite cost, a graph is constructed by proceeding backwards, considering all the possible resolvers for all the possible lfaws. The estimated costs are updated every time a unification is found or in those cases in which the resolver does not introduce further flaws. Finally, the graph building procedure proceeds until a finite estimate cost for the top-level goals is reached.
Compared to other state-of-the-art timeline-based solvers, the above heuristics allow solving problems up to one order of magnitude fas2t4e]r. T[he most interesting aspect for the current topic, however, concerns the management of the causal constraints in the causal graph. Similar to planning models based on satisfabili4t9y],[indeed, a set of propositional variables is assigned to flaws and to resolvers. For the sake of brevity we will use subscripts to indicate flaws (e.g., 0, 1, etc.), resolvers (e.g.,0, 1, etc.) as well as their associated propositional variables. Additionally, given a flaw , we refer to the set of its possible resolvers by means o( f) and, by means of ( ), to the set of resolvers (possibly empty, in case of the flaws of the problem’s requirement) which are responsible for introducing it. Moreover, given a re,swoelvreerfer to the set of its preconditions (e.g., the set of tokens introduced by the application of a rule) by means of ( ) and to the flaw solved through its application by mean s of( ). Using the above notation we can estimate the cost of a genericaflas w ( ) = ∈ ( ) ( ) (1) and the cost of a generic resol vears ( ) = ( ) + ∈ ( ) ( ) (2), in which ( ) represents the intrinsic cost of the resolv.er
The introduction of such variables allows to constrain them so as to guarantee the satisfaction of the causal relations. Specifically, for each flaw , we guarantee that the preconditions of all the applied resolvers are satisfied (= ⋀ ∈ ( ) (3)) and that at least one resolver is active whenever the flaw becomes activ e (⇒ ⋁ ∈ ( ) (4)). Additionally, we need a gimmick to link the presence of the tokens with the causality constraint. A further variable ∈ {, , }, in this regard, is associated to each token. A partial solution will hence consist solely of those tokens of the token network whiacchtiavre.eMoreover, in case such tokens are goals, the bodies of the associated rules must also be present within the solution. Later on, we refer to tokens by means of tvhaeriables (we will use subscripts to describe specific tokens, e.g., 0, 1, etc.) and to the flaws introduced by tokens by means of t(h)e function.
The last aspect to consider concerns the update of such variables as a consequence of the activation of a rule application resolver and of a unification resolver. Specifically, each rule application resolve r binds the variable of the goal token, whose rule has been applied, to assume the value (formally, = [ ( ) = ]). Finally, for each unification resolver representing the unification of a tok e nwith a target toke n, the constraints = [ = ] and ⇒ [ = ] guarantee the update of thveariables while adding( ) to the preconditions ofguarantees the operation of the heuristic.
In order to better understand how the heuristics and the causality constraints work, we introduce in this section a running example of an explanatory planning problem, whose objective is to plan a physical rehabilitation session for an hypothetical user.2Fsihgouwres the causal graph which is generated for the problem, whose problem requirement is constituted by the sole goal 0. Estimated costs for flaws (boxes) and resolvers (circles) are on their upper right. The propositional variables that participate in the causal constraints are on their upper left. Solid (True) and dashedU( nassigned) contour lines are used to distinguish flaws’ and resolvers’ associated propositional variables’ values. In the figure, in particul ar0, vtahreiable, representing a flaw which is present in the problem requirement and therefore must necessarily be solved, assumes theTrue value.
It is worth noting that, in the example, 0thflaew, for achieving the 0 goal, can only be solved through the0 resolver, which is hence directly applied (notice the solid line) as a consequence of the propagation of the causal constraints. Si(n0c)e = { 0}, indeed, the expression(4) translates in to0 ⇒ 0. This, in turn, forces t he0 goal to assume the value as a consequence of0 = [ ( 0) = ]. The 0 resolver, furthermore, represents the application of a rule havingℎa () in the head and, in the body, a conjunction of the two 1 and 2 goals. The application of this resolver, in particular, introduc1es=the( 1) and the 2 = ( 2) flaws, each of which must necessarily be resolved as a consequence of the 1 = 0 and 2 = 0 causal constraints, from the express(3io).nThese flaws, in turn, can be solved through the application of t1heand of th e 2 resolvers which introduce, respectively, the disjunctions represented by t3heand 4 flaws.
Proceeding backwards, the propagation of the causal constraints no longer allows to infer what is present in the current partial plan (notice the dashed lines). The resolution of the3 and 4 flaws, in particular, constitute two choices that the planner must make during the resolution process. The3 flaw, for example, can be solved either by applying the 0 disjunct, represented by the 3 resolver, or by applying Figure 2: An example of causal graph for the planning of a the 1 disjunct, represented by physical rehabilitation session. Tokens’ paramethe 4 resolver. The graph construc- ters are omitted to avoid burdening the notation. tion process, however, which proceeds following a breadth-first approach, has identified, in the example, a possible solution for the 3 flaw by applying first the 3 resolver and then the7 resolver (the latter corresponding, in this simple example, to a rule with an empty body). The heuristics’ estimated costs propagation procedure, hence, makes t he3 resolver, with an estimated cost of 2, much more attractive than th e 4 resolver, with an estimated cos∞t.oFfor a similar reason, th5e resolver will be preferred over t he6 resolver, leading to a (possible) solution of the planning problem.
It is worth noting that, for the sake of simplicity, the tokens’ parameters are not represented in the example figure. All tokens, however, are endowed with numerical variables that represent the start and the end of the associated activities, appropriately constrained according to common sense. Upper and lower body exercises, for example, represented respectively by1 tahned by the 2 tokens, will take place as part of the more general physical exercise represented by the 0 token. The 3 and by the 5 tokens, additionally, are endowed with thveairiables which will avoid their temporal overlapping if they will assume the same value.
The construction of the causal graph is, inevitably, a partial task that cannot be carried out in an exhaustive manner. Consider, for example, the case of a not so smart robotic arm which, in order to move an object from one point to another, considers an infinite number of tasks in which it takes the object and puts it back where it initially was. The graph building procedure, in particular, starts by queuing the high-level flaws, defined in the planning problem, in an expansion queue. At each step, a flaw is extracted from the queue and expanded, possibly queuing further sub-flaws, proceeding backwards in a breadth-first manner until the high-level lfaws do assume a finite estimated cost. It is worth noticing that, exception made for very simple cases, when the graph building procedure halts, the queue might still contain some flaws. These lfaws, however, have an estimated infinite cost. Once given way to the resolution algorithm, in particular, these flaws would be avoided as much as possible by the search algorithm. In other words, for these flaws, the graph is not able to provide any indication for their resolution.
Can we, before the resolution process starts, remove them from the graph or, somehow, forbid their choice? As we will see, the answer is yes, but we can do even more. Some of the flaws in the graph expansion queue, indeed, might constitute the preconditions for the resolution of already expanded flaws which, within the causal graph, do already have a finite estimated cost. Such flaws, which we call deferrable, can easily be identified by traversing the causal graph following the direction of the arrows, until a flaw with a finite estimated cost is found (hence the flaw is classified as deferrable) or a sink node is reached (hence the flaw is classified as non-deferrable). Once removed from the graph’s expansion queue, in particular, these flaws can immediately be re-queued for subsequent further processing.
When the graph expansion procedure halts, in particular, there will be, in the graph’s expansion queue, a set of flaws, either deferrable or not expanded yet. Instead of discouraging the search algorithm from choosing such flaws, we can forcibly prevent it by imposing constraints on the corresponding causal variables (the causal variables are forced to false). It is worth noting that these flaws, having an infinite estimated cost, would not be chosen by the search anyway. The introduction of the constraints, however, causally propagates within the causal graph leading to some benefits in terms of performance.
Consider, for example, the graph presented in Fig2u.rBeefore the expansion of the5 flaw all the estimated costs are infinite. The expansion of t5hflaew, however, introduces a resolve r7, , that has no preconditions. The cost of such a resolver, in line wiℎt h theuristic, can easily be estimated as the sole intrinsic cost of the resolve2r). (BEyq.applying the cost estimation formula, the cost update is propagated forward by assigning an estimated cost of51 to the lfaw (Eq. 1), an estimated cost of 2 to t3heresolver, an estimated cost of 2 to t3 hflaew, an estimated cost of 3 to th1eresolver and an estimated cost of 3 t o1tflahwe. All the other lfaws and resolvers maintain, at this point, an infinite estimated cost.
The 6 flaw is then removed from the graph’s expansion queue and checked for deferrability. Since the 3 lfaw has a finite estimated cost, the flow is recognized as deferrable and is re-queued into the graph expansion queue. It’s now the turn of7tflahwe, having a term similar to that of the 5 flaw. The cost update propagation, however, reaches, this time, the updating the cost of the high-level 0 lfaw, determining the halting of the graph building procedure wit h6 the and the 8 lfaws in the graph expansion queue.
The resulting graph, depicted in Figu2r,sehows that the only two choices that the resolution algorithm should eventually make are the resolution o3f tahned of th e 4 lfaws. In solving such flaws, specifically, the heuristic-driven algorithm would choose the resolvers with the lowest estimated cost, respectively t3haend of th e 5 resolvers, strictly avoiding the choice of the 4 and of th e 6 resolvers, whose estimated cost is infinite. If, however, the causal variables of the queued flaws (i.e., the 6 and the 8 lfaws) are forced to false, the causal constraints (i.e., (4) and(3)) force th e 4 and of th e 6 resolvers at false false and, consequently, t3haend of the 5 resolvers at true, together wit h 5thaend the 7 lfaws and the 7 and of th e 8 resolvers, solving the problem without the slightest need, at least from a causal point of view (a search may in fact still be required for scheduling the activities), to do any search.
In order to test the efectiveness of the proposed pruning techniques we have implemented both the procedures for pruning and for recognizing the deferrable flaws witohRinattihoe2 planner, testing its performance on diferent instances of increasing complexityGoancthe domain. Specifically, the Goal Oriented Autonomous ControGlloerac() was an ESA initiative aimed at defining a new generation of software autonomous controllers to support increasing levels of autonomy for robotic task achievement. In particular, the domain, initially defined in [30] and more recently cited i5n0][, aims at controlling a rover to take a set of pictures, store them on board and dump the pictures when a given communication channel was available. The interesting aspect of this domain is that communication can only take place within specific visibility windows that take into account the astronomical motions of the planets/satellites which, in some cases, may stand between the transmitting and receiving stations. The presence of these visibility windows, in particular, requires an explicit modeling of temporal aspects in order to adequately plan the transmission of information and can hence easily be modeled through, and solved by, timeline-based planners. The problem is made more interesting by the presence of constraints which include the available resources (e.g., memory and battery) as well as by having a distance matrix, among the possible locations, which might be not completely connected.
Figure3 shows the execution times of diferent configurations of otRhaetio solver, allowing 2https://github.com/pstlab/oRatio the comparison of the base solver, without pruning, pruning without recognizing the deferrable lfaws and pruning with the recognition of the deferrable flaws. From the figure it is possible to see how, in general, the resolution times significantly benefit from the application of pruning on the proposed benchmarking problem, reducing by an order of magnitude the computation times in the case of the instance #9 of the problem with two visibility windows, or allowing resolution within the two minute timeout in the case of the instance #7 of the 5 visibility windows. Note how deferrable flaw recognition adds a little overhead in smaller instances, which still leads to a benefit in larger instances.
The eficiency of the planners’ resolution processes is strongly influenced by the heuristics that, in some cases, guide the solution process while, in other cases, can prune the search space so as to favor the propagation of causal constraints and avoid possible dead-ends. The use of pruning techniques is not new in the case of classical planning, however, it is less explored in the case of partial-order planning and, even more so, in the case of high-expressive timeline-based planning. For this reason we have presented a pruning technique based on the construction of a lifted causal graph. The experimental results, although conducted on a single benchmarking problem, show significant benefits and are, therefore, encouraging. A more detailed experimentation on a greater number of benchmarking problems could highlight further benefits or weaknesses of the proposed approach and, therefore, will certainly be carried out in future work. on Automated Planning and Scheduling, 2010, pp. 34–41. [28] S. Fratini, F. Pecora, A. Cesta, Unifying Planning and Scheduling as Timelines in a
Component-Based Perspective, Archives of Control Sciences 18 (2008) 231–271. [29] A. Cesta, G. Cortellessa, S. Fratini, A. Oddi, Developing an End-to-End Planning Application from a Timeline Representation Framework, in: IAAI-09. Proceedings of tIhnen2o1vative Applications of Artificial Intelligence Conference, Pasadena, CA, USA, 2009, pp. 66–71. [30] S. Fratini, A. Cesta, R. De Benedictis, A. Orlandini, R. Rasconi, APSI-based Deliberation in
Goal Oriented Autonomous Controllers, ASTRA 11 (2011). [31] A. Umbrico, A. Cesta, M. Cialdea Mayer, A. Orlandini, Platinum: A new framework for planning and acting, in: AI*IA 2017 Proceedings, 2017, pp. 498–512. [32] J. Frank, A. K. Jónsson, Constraint-Based Attribute and Interval Planning, Constraints 8 (2003) 339–364. [33] A. Cesta, A. Oddi, Gaining Eficiency and Flexibility in the Simple Temporal Problem, in: L. Chittaro, S. Goodwin, H. Hamilton, A. Montanari (Eds.), Proceedings of the Third International Workshop on Temporal Representation and Reasoning (TIME-96), IEEE Computer Society Press: Los Alamitos, CA, 1996, pp. 45–50. [34] P. Laborie, Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results, Artificial Intelligence 143 (2003) 151–188. [35] S. Stock, M. Mansouri, F. Pecora, J. Hertzberg, Hierarchical hybrid planning in a mobile service robot, in: KI 2015 Proceedings, 2015, pp. 309–315. [36] A. Bit-Monnot, M. Ghallab, F. Ingrand, D. E. Smith, FAPE: a Constraint-based Planner for
Generative and Hierarchical Temporal Planning, arXiv preprint arXiv:2010.13121 (2020). [37] F. Dvorák, A. Bit-Monnot, F. Ingrand, M. Ghallab, Plan-Space Hierarchical Planning with the Action Notation Modeling Language, in: IEEE International Conference on Tools with Artificial Intelligence (ICTAI), Limassol, Cyprus, 2014. URLh:ttps://hal.archives-ouvertes. fr/hal-01138105. [38] D. E. Smith, J. Frank, W. Cushing, The ANML language, in: ICAPS Workshop on Knowledge
Engineering for Planning and Scheduling (KEPS), 2008. [39] D. E. Wilkins, Practical planning: extending the classical AI planning paradigm / David E.
Wilkins, Morgan Kaufmann Publishers San Mateo, Calif, 1988. [40] D. S. Nau, T. Au, O. Ilghami, U. Kuter, J. W. Murdock, D. Wu, F. Yaman, SHOP2: an HTN planning system, J. Artif. Intell. Res. 20 (2003) 379–404. [41] L. Castillo, J. Fdez-Olivares, O. García-Pérez, F. Palao, Eficiently handling temporal knowledge in an htn planner, in: Proceedings of the Sixteenth International Conference on International Conference on Automated Planning and Scheduling, ICAPS’06, AAAI Press, 2006, pp. 63––72. [42] P. Laborie, M. Ghallab, Planning with Sharable Resource Constraints, in: Proceedings of the 14th international joint conference on Artificial intelligence - Volume 2, IJCAI’95, Morgan Kaufmann Publishers Inc., 1995, pp. 1643–1649. [43] A. Cesta, A. Oddi, S. F. Smith, A Constraint-Based Method for Project Scheduling with Time Windows, Journal of Heuristics 8 (2002) 109–136. URhLt:tps://doi.org/10.1023/A: 1013617802515. doi:10.1023/A:1013617802515. [44] D. E. Smith, J. Frank, A. K. Jónsson, Bridging the Gap Between Planning and Scheduling,
Knowledge Engineering Review (2000). [45] G. Verfaillie, C. Pralet, M. Lemaître, How to model planning and scheduling problems using constraint networks on timelines, The Knowledge Engineering Review 25 (2010) 319–336. [46] M. Cialdea Mayer, A. Orlandini, A. Umbrico, Planning and execution with flexible timelines: a formal account, Acta Informatica 53 (2016) 649–680. UhRttLp:://dx.doi.org/10.1007/ s00236-015-0252-z. doi:10.1007/s00236-015-0252-z. [47] R. Dechter, Constraint Processing, Elsevier Morgan Kaufmann, 2003. [48] K. R. Apt, M. G. Wallace, Constraint Logic Programming Using PESC,LCambridge
University Press, New York, NY, USA, 2007. [49] H. Kautz, B. Selman, Planning as Satisfiability, in: ECAI, volume 92, 1992, pp. 359–363. [50] A. Coles, A. Coles, M. Martinez Munoz, O. Savas, J. Delfa, T. de la Rosa, Y. E-Martín, A. García Olaya, Eficiently Reasoning with Interval Constraints in Forward Search Planning, in: Proceedings of the Thirty Third AAAI Conference on Artificial Intelligence, AAAI Press, 2019.