Automated planning involves devising a sequence of actions or decisions to attain specific goals within defined constraints. Within the realm of automated planning, optimization techniques are employed to enhance plan quality. These techniques target the minimization or maximization of various parameters, such as time, cost, resource utilization, and other relevant criteria, all while ensuring plan feasibility and adherence to problem constraints.
CEUR ceur-ws.org
Preference-based planning is a branch of automated planning and scheduling that emphasizes the generation of plans while considering and attempting to fulfill a maximum number of user-specified preferences. In numerous problem domains, achieving a task can involve multiple sequences of actions, which are commonly referred to as plans. The quality of these plans can vary significantly, with some being more desirable due to factors such as cost-efectiveness, speed, and safety. When generating a plan for a particular problem, preference-based planners IPS-RCRA-SPIRIT 2023: Italian Workshop on Planning and Scheduling, RCRA Workshop on Experimental evaluation of algorithms for solving problems with combinatorial explosion, and SPIRIT Workshop on Strategies, Prediction, Interaction,
CEUR
Workshop
Proceedings
take these user-defined preferences into consideration. Examples of software for
preferencebased planning include PPLAN2[] and HTNPlan-P [
In this context, timeline-based planning7[] has emerged as a promising departure from conventional planning paradigms. By embracing the principles of partial-order plann8]in,g [ timeline-based planning yields plans that exhibit heightened adaptability during execution, in stark contrast to the rigidly ordered plans generated by solvers employing the aforementioned heuristics. While ofering distinct advantages, timeline-based planners grapple with challenges attributed to the rich expressiveness of their formalisms, often resulting in performance bottlenecks.
This paper embarks on an exploration of a relatively uncharted territory: the realm of optimization within the domain of timeline-based planning. The essence of this endeavor lies in our commitment to achieve plan quality optimization without the need for substantial modifications to the underlying planner. Instead, we adopt and adapt existing heuristics, leveraging their strengths to enhance the planning process. Our approach involves the introduction of specific operators into the planning problem domains, strategically guiding the decision-making process towards more efective solutions.
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. This form of planning
was first introduced in [
Theoretical work on timeline-based planning, such a1s8,[
Despite these approaches share similarities, the lack of a common formalization hindered efective comparison and combination of their features. This limitation made it challenging to identify strengths, weaknesses, and develop comprehensive solutions. To provide a reference point, we mainly refer to the formalization proposed2i9n],[which covers a significant portion of problems solvable by existing approaches.
Understanding timeline-based planning requires introducing fundamental concepctosno-f straint networks [30], consisting in a set ofvariables and a set ofconstraints. Variables have names and can take diferent values from theidromain. The domain is initially defined and can evolve over time. Variables can be continuous (with infinite initial domains) or discrete (with a finite number of values). Constraints restrict combinations of values for a set of variables. Assigning values to variables is called an evaluation, which is consistent if it satisfies all constraints. An evaluation is complete when it includes all variables.
In timeline-based planning, constraint networks provide the foundation for modeling and reasoning about the problem. The central concept in this paradigm, however, istitmheeline, which represents a function of time over a specific domain. The timeline can be either discrete or continuous, and its domain can be symbolic or numeric. Numeric domains can further be categorized as discrete or continuous.
To standardize the representation of timelines and make the reasoning process independent of their nature, the concept otofkens is introduced. Tokens are expressions that derive values on timelines through a timeline extraction procedure. They provide a unifying element for consistent representation and reasoning. A to ke(n0, … , ) consists of a predicate nam e, 0, … , parameters (temporal, symbolic, and numerical constants or variables), ancdlaass (fact or goal). The parameters, in particular, can be variables within a constraint network and, as such, can be constrained, thereby narrowing down the range of acceptable values to the desired ones. Constraints can be imposed among the token parameters, as well as between parameters and other variables, encompassing temporal, symbolic, and numerical relationships. Tokens provide a higher-level semantics by grouping variables into structured data, enabling reasoning for planners. A timeline, in these context, igsloabal constraint [30]) over the tokens, preventing undesired temporal overlaps.
The combination of tokens and constraints forms the primary data structure for representing plans in timeline-based planning: thetoken network. The token network serves as the primary representation of plans in timeline-based planning. It is manipulated throughout the reasoning process by adding constraints among token variables for consistency and applying rules to establish causality. Tokens are categorized as facts (inherently true) or goals (to be achieved), with causality defined by rules that outline the necessary conditions for goal achievement. Rules consist of a head (goal) and a body (requirements), which can include slave tokens, constraints, conjunctions, andpriced disjunctions. The selection of disjuncts during the resolution process plays a critical role in determining the cost associated with the resulting plan. Essentially, these costs establish preferences among potential admissible solutions. Consequently, this paper places its primary emphasis on these costs, recognizing them as the key factor within our investigation.
Finally, a timeline-based planninpgroblem consists of a set of typed objects, a set of rules, and a requirement. The typed objects are used to instantiate the initial domains of variables in the constraint network and token parameters. A solution to the problem is a token network that is consistent with the rules and satisfies the requirement. This means that the token network’s variable evaluation is consistent with the constraints, and for each goal in the token network, the corresponding rule’s body is present.
Consider, as an example, the travel planning scenario presented in Fig1u. rIen this scenario, the agent’s starting point is locati on, and its objective is to reach location, which is not directly connected t o . To achieve this, the agent must pass through locatio n, accessible by either metro, with a cost of 7, or bus, with a cost of 10. Once at locatio,nit faces two alternatives: taking a direct train to destinati o,nwith a cost of 5, or embarking on a two-step journey involving a train ride to the airport ,inwith a cost of 5, followed by a flight to reach destination , with a cost of 20. These costs, importantly, do not merely reflect travel times; instead, they represent preferences regarding the user’s choice of transportation modes. In essence, timing constraints might compel the agent to utilize modes of transportation that may not align with their preferences. In this particular problem, we have a defined set of locations ( , , , and ) along with corresponding facts that denote the connections between these locations using diferent modes of transportation, including the associated travel times. Additionally, there is a fact such as( ∶ , ∶ )1 indicating the agent’s initial position, a go al ( ∶ ) representing the desired destination, and a set of rules outlining various routes to reach a specific location. These rules are accompanied by constraints pertaining to the use of vehicles and limitations on travel duration. The rule for reaching a location is (, , ) ← { ( ∶ , ∶ ) }10 ∨ { ( ∶ , ∶ ) }7 ∨ { ( ∶ , ∶ ) }5 ∨ { ( ∶ , ∶ ) }20, indicating a cost of 10, 7, 5 and 20, respectively, for each taken bus, subway, train and plane. The rule for taking, for example, a bus, instead, is ( , , , ) ← ( ∶ , ∶ , ) ∧ [ − ≥ ]. Finally, there is a single state-variable timeline, preventing the agent to be in diferent positions or in diferent means of transport at the same time. As you can see from the rules, these activities have a duration. In the event of a deadline, regardless of preferences, not all plans may be acceptable.
Timeline-based solvers heavily rely on partial-order planning techniqu8]e,se[xtending the definition of threats to include potential inconsistencies arising from timeline constraints. These solvers aim to identifyflaws in the token network and utilizreesolvers to address them. Flaws can be unachieved goals, threats, disjunctions, or unassigned variables. Resolvers are 1We use the notation “var: expr” to indicate the direct assignment of an expression to a variable. In this ca se, the variable indicates the location. mechanisms designed to resolve specific types of flaws. They can involve applying rules, unifying semantically equivalent tokens, introducing ordering constraints, selecting options from disjunctions, or assigning values to unassigned variables. The main resolution principle involves systematically improving the token network by applying appropriate resolvers while maintaining the consistency of constraints until the token network is flaw-frees.olAution to a timeline-based planning problem is a token network without flaws and consistent constraints.
Solving timeline-based planning problems involves non-deterministic resolver selection and deterministic flaw processing. To manage computational complexity, deterministic implementations can use algorithms like A* or IDA* for eficient solution generation. The main challenge lies in accurately defining the current state and measuring the distance to the desired state, which hampers the use of traditional planning heuristics. To address th2i9s], [propose a separation of temporal and causal elements, allowing adaptation of classical planning heuristics to the causal aspects. The proposed approach employs an AND/OR graph to represent causal relationships between flaws and resolvers, enabling eficient exploration of a disjunctive token network. By analyzing the topology of the generated graph, heuristics lℎike andℎ [31] can estimate resolver and flaw costs, guiding the resolution process. Specifically, we have that: ( ) = ∈ ( ) ( ) ( ) = ( ) + ( ) = ( ) + ∈
( ) ∑ ∈ ( ) ( ) ( ) where ( ) represents the estimated cost for a fla w, ( ) represents the estimated cost for a resolve r computed through theℎ heuristic, ( ) represents the estimated cost for a resolver computed through theℎ heuristic, and ( ) is the intrinsic cost of the resolver, i.e., a positive number representing thceost of disjuncts, in case of priced disjunctions, or the value 1, in other cases.
During the resolution process, the solver employs a strategy that prioritizes addressing the most costly flaw with the least expensive resolver. This approach serves the dual purpose of early inconsistency detection and eficient solution attainment. However, it’s crucial to acknowledge that constructing the causal graph has inherent limitations, and in many cases, it cannot be fully realized.
Specifically, the process commences by assigning a zero cost to the problem’s facts, as these facts are considered inherently true. Conversely, both flaws and resolvers are initially assigned an infinite estimated cost. The process then unfolds in a breadth-first manner, moving backward through the graph. It continues in this manner until it encounters facts or other goals that can be associated with a finite estimated cost.
Upon such an encounter, the process proceeds to propagate the estimated costs, taking into account the strategy employed to estimate the goals (i.e., either using tℎh e orℎ heuristic). This iterative process perseveres until the high-level flaws are ultimately attributed a finite estimated cost, marking significant progress in the resolution process.
When pursuing optimal plans, a significant challenge arises during the graph construction process, where the procedure may terminate before incorporating the optimal plan into the graph. An illustrative scenario is exemplified by the concept of “favorite goals”, which represent objectives that one would ideally like to achieve but are not strictly mandatory. Failure to attain a favorite goal incurs a penalty for the planner. For instance, let’s consider the problem illustrated in Figure2. On the right-hand side, there is a requirement represented as the disjunctionℎ () ∨ {}50. This disjunction is designed to generate a plan that includes a physical workout, provided that the constraints permit it. The workout should encompass exercises targeting both the upper and lower parts of the body.
The complexity arises when, during the graph construction phase, the cost associated with an empty option (i.e., no plan for the goal) seems preferable compared to the initially infinite cost assigned to the preferred goal. This situation can prematurely conclude the graph construction procedure, suggesting to the planner that an empty plan is the best choice. In the example represented in Figure2, in particular, the graph building procedure would not introduce the 3 resolver, it would keep an infinite estimated cost for th e1 flaw since there already is a possible better (compared to the current infinite one) solution thoward th2e resolver. In essence, concerning preferable goals, this strategy can result in plans that, while technically valid, exhibit very poor quality. Such plans may not align with the planner’s actual preferences and objectives, emphasizing the importance of refining the resolution process for optimizing the quality of the generated plans.
The solution we propose involves the incorporation of “jamming operations” when necessary, aiming to prevent the premature termination of the graph construction procedure. Specifically, we introduce a type of goal denoted a s , equipped with an ID parameter, ensuring that diferent “jamming goals” do not interfere with each other, and a positive integer parameter known as “look-ahead”. The corresponding rule for these goals is structured as follows: (, ℎ ) ← ( ∶ , ℎ ∶ ℎ − 1 ) ∨ [ℎ = 0 ].
As an example, consider the prior disjunction, which could be modified to ℎ () ∨ { ( ∶ 1, ℎ ∶ 42 ) }50. This modification ensures that a depth of 42 is guaranteed for the empty (and more costly) branch. The estimated cost for this branch remains infinite until the lookahead parameter reaches zero. In the meantime, this (a) A comparison of plan costs without and with(b) A comparison of execution times without and the utilization of jamming actions. with the utilization of jamming actions. approach encourages exploration of the branch containing the physical activity, thus mitigating the issues related to prematurely favoring empty plans.
We have conducted some experiments to demonstrate the efectiveness of the proposed approach. Since we are working on a Active Assisted Living project, we focused on planning problems similar to those described in the previous section, in which the user has to carry out some physical and cognitive rehabilitation exercises to keep active and prolong his/her health wellbeing. In particular, series of physical exercises chosen from 14 diferent types (e.g., Chest press, Biceps curl, etc.) are planned in order to guarantee the training of all parts of the body. The exercises are repeated several times and with diferent characteristics depending on the profile of the user. Some constraints, however (e.g., lack of time on some days), might prevent the user from carrying out all the activities, so the planner must optimize by putting in as many workout sessions as possible.
In our experimental study, we performed a comparative analysis by introducing the proposed jamming actions in scenarios with an escalating number of physical training activities. We carefully assessed the time needed to find a solution for each case. Our expectation was that, despite the additional computational load imposed by the jamming actions, their incorporation would lead to the creation of notably superior plans. We remained hopeful that the introduction of these actions would not unduly compromise the eficiency of the resolution process.
As depicted in Figure3b, the execution times remain comparable to those observed in scenarios without the presence of jamming actions. However, a noteworthy improvement is observed in the quality of solutions, as illustrated in Figu3rae. These improvements entail a shift from plans that accumulate penalties to plans in which costs align with the intrinsic costs of the activities, efectively reflecting optimal 2 plans.
Nevertheless, a crucial caveat must be considered. The heuristic guiding the resolution algorithm encourages the pursuit of optimal solutions. In the tested cases, optimal solutions are readily attainable. With the incorporation of jamming actions, the planner introduces all the necessary activities into the graph to discover the optimal plan. The heuristic then guides 2We know the solutions are optimal because the generated plans contain all the preferred goals. the resolution towards this solution. Attempts were made to introduce constraints preventing the planner from reaching the optimal solution, such as imposing a makespan shorter than the total number of activities. This was intended to compel the planner to add tasks following the heuristic but subsequently trigger backtracking. Regrettably, the performance in such cases proved unsatisfactory. We attribute this issue to the limitations of scheduling algorithms, which could benefit from optimization. For instance, there’s no need to exhaustively explore all possible orderings of ten tasks of unit duration to determine that they cannot be sequenced in a way that achieves a duration of less than ten. In summary, while jamming actions significantly enhance solution quality, there is room for improving the scheduling algorithms to handle more complex scenarios eficiently.
This paper has delved into the realm of timeline-based planning, which ofers a departure from traditional planning paradigms by providing adaptable and dynamic plans. It has explored, to the best of our knowledge, for the first time, the optimization of timeline-based planning, without requiring extensive modifications to the underlying planner. Instead, the paper introduces specific operators strategically into the planning domains, leveraging existing heuristics to guide decision-making efectively.
Timeline-based planning relies on the foundation of constraint networks and tokens, allowing for modeling and reasoning about complex problems. These tokens and constraints are manipulated to construct plans through a resolution process. In particular, this paper places a significant emphasis on the selection of disjuncts during resolution, which determines the cost and, thus, preferences among potential solutions.
The introduction of jamming actions, aimed at preventing premature termination of the graph construction process, has been proposed as a solution to the generation of optimized plans. These actions have been demonstrated through experiments focusing on physical and cognitive rehabilitation exercises, showcasing their ability to improve plan quality without significantly impacting execution times.
While the incorporation of jamming actions has shown promise in generating high-quality plans, there remains room for further improvement in scheduling algorithms to handle more complex scenarios eficiently. This paper marks a step towards enhancing the capabilities of timeline-based planners and paves the way for future research in this field.
Authors’ work is partially supported by FOCAAL - FOg Computing in Ambient Assisted Living. “ACCORDI DI INNOVAZIONE - Bando” Decreto MiSE 05/03/2018 e Decreto Direttoriale 27/09/2018, and CLEVERNESS - “Tecnologie a supporto delle fasce più fragili: giovani e anziani”. FINANZIAMENTO PROGETTUALITA’ STRAORDINARIA - FOE 2020.
Component-Based Perspective, Archives of Control Sciences 18 (2008) 231–271. [15] S. Fratini, A. Cesta, R. De Benedictis, A. Orlandini, R. Rasconi, APSI-based Deliberation in
Goal Oriented Autonomous Controllers, ASTRA 11 (2011). [16] 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. [17] M. Cialdea Mayer, A. Orlandini, A. Umbrico, Planning and execution with flexible timelines: a formal account, Acta Informatica 53 (2016) 649–680. URhLtt:p://dx.doi.org/10.1007/ s00236-015-0252-z. doi:10.1007/s00236-015-0252-z. [18] J. Frank, A. K. Jónsson, Constraint-Based Attribute and Interval Planning, Constraints 8 (2003) 339–364. [19] M. Fox, D. Long, PDDL2.1: An Extension to PDDL for Expressing Temporal Planning
Domains, Journal of Artificial Intelligence Research 20 (2003) 61–124. [20] P. Laborie, Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results, Artificial Intelligence 143 (2003) 151–188. [21] 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. [22] S. Stock, M. Mansouri, F. Pecora, J. Hertzberg, Hierarchical hybrid planning in a mobile service robot, in: KI 2015 Proceedings, 2015, pp. 309–315. [23] 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. URL:https://hal.archives-ouvertes. fr/hal-01138105. [24] D. E. Smith, J. Frank, W. Cushing, The ANML language, in: ICAPS Workshop on Knowledge
Engineering for Planning and Scheduling (KEPS), 2008. [25] 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. [26] 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. [27] D. E. Smith, J. Frank, A. K. Jónsson, Bridging the Gap Between Planning and Scheduling,
Knowledge Engineering Review (2000). [28] 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. [29] R. De Benedictis, A. Cesta, Lifted Heuristics for Timeline-based Planning, in: ECAI-2020, 24th European Conference on Artificial Intelligence, Santiago de Compostela, Spain, 2020, pp. 498–2337. [30] R. Dechter, Constraint Processing, Elsevier Morgan Kaufmann, 2003. [31] B. Bonet, H. Gefner, Planning as Heuristic Search, Artificial Intelligence 129 (2001) 5–33.