Exploiting Symbolic Heuristics for the Synthesis of Domain-Specific Temporal Planning Guidance using Reinforcement Learning
Irene Brugnara, Alessandro Valentini, Andrea Micheli · 2025
Read Exploiting Symbolic Heuristics for the Synthesis of Domain-Specific Temporal Planning Guidance using Reinforcement Learning by Irene Brugnara, Alessandro Valentini, Andrea Micheli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13372.txt.
Introduction
Irene Brugnara, Alessandro Valentini, and Andrea Micheli present a 2025 study on teaching planning software to handle tasks set over time. Their method learns guidance for a fixed domain from a set of practice problems. Past work drew the guidance from a value function learned by trial and error.
Their new version uses classic symbolic heuristics, or rule-based scores, at both the learning and planning stages. It learns a correction to a known score rather than a whole new score from scratch. At plan time it runs learned and classic scores side by side. Tests show clear gains over the prior method for this kind of planning.
Catalog record
| CREATOR | Irene Brugnara, Alessandro Valentini, Andrea Micheli |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13372
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exploiting Symbolic Heuristics for the Synthesis of Domain-Specific Temporal Planning Guidance using Reinforcement Learning Irene Brugnara, Alessandro Valentini, Andrea Micheli Abstract Recent work investigated the use of Reinforcement Learning (RL) for the synthesis of heuristic guidance to improve the performance of temporal planners when a domain is fixed and a set of training problems (not plans) is given. The idea is to extract a heuristic from the value function of a particular (possibly infinite-state) MDP constructed over the training problems. In this paper, we propose an evolution of this learning and planning framework that focuses on exploiting the information provided by symbolic heuristics during both the RL and planning phases. First, we formalize different reward schemata for the synthesis and use symbolic heuristics to mitigate the problems caused by the truncation of episodes needed to deal with the potentially infinite MDP. Second, we propose learning a residual of an existing symbolic heuristic, which is a “correction” of the heuristic value, instead of eagerly learning the whole heuristic from scratch. Finally, we use the learned heuristic in combination with a symbolic heuristic using a multiple-queue planning approach to balance systematic search with imperfect learned information. We experimentally compare all the approaches, highlighting their strengths and weaknesses and significantly advancing the state of the art for this planning and learning schema. † † paperid: 4770 1 Introduction Automated temporal planning is the problem of synthesizing a course of action to achieve a desired goal condition, given a formal description of a timed system [ Ghallab et al.(2004)Ghallab, Nau, and Traverso ] . Temporal planning finds natural applications in many domains such as robotics, logistic and process automation because time and temporal constraints are commonplace in real-world applications. Despite a long history of research and improvements, scalability is the key issue for automated temporal planners: depending on the modeling assumptions the computational complexity ranges from PSPACE-completeness to undecidability [ Gigante et al.(2022)Gigante, Micheli, Montanari, and Scala ] . Using machine learning to specialize a temporal planner for a domain is a promising way to mitigate the scalability issue and automatically devise effective solvers. An approach to tackle this specialization of temporal planning solvers consists of codifying a set of training problems as a specifically designed Markov Decision Process (MDP) and using Reinforcement Learning [ Sutton and Barto(2018) ] to estimate its value function; in turn, it is possible to extract a temporal planning heuristic biased on the distribution of training problems for a search-based temporal planner from the estimated value function [ Micheli and Valentini(2021) ] . The workflow consists of two phases: an offline phase in which the temporal planner is specialized on the given training dataset in a fully automated way, and then an online phase in which the specialized planner is tasked to solve multiple problems on the same domain. More in detail, this approach builds on the discretization of the search space used by planners such as Tamer [ Valentini et al.(2020)Valentini, Micheli, and Cimatti ] : the continuous space of the timed system is abstracted by symbolically representing time and timing constraints using Simple Temporal Networks (STN) [ Dechter et al.(1991)Dechter, Meiri, and Pearl ] and the planner searches in the (partial) orderings of events , which are either the beginning or ending of durative actions, or intermediate effects and conditions if they are allowed. The learning framework exploits this discretization of the search space by defining a tree-shaped MDP, where an instance from the training set is randomly selected at the beginning of the episode and then the MDP is isomorphic to the planner search space. An optimal value function for the MDP is shown to be in a functional relation with the optimal heuristic for the training instances, and the authors show that by using neural networks as function approximators and encoding states (including symbolic temporal information and the goal) as feature vectors, the approach can generalize to instances drawn from the same distribution of the training set. Learner Domain Training dataset of planning problems \mathcal{P}_{\mathcal{D}}^{k} (§ 2 ) MDP Value function Planning guidance New planning problem in \tilde{\mathcal{P}}^{k}_{\mathcal{D}}\setminus\mathcal{P}_{\mathcal{D}}^{k} (§ 2 ) Plan Encoding RL algorithm Transform Planner Reward schemata (§ 3 ) Residual learning (§ 4.2 ) Truncation bootstrap (§ 4.1 ) Reward schemata (§ 3 ) Multi-queue (§ 4.3 ) Offline Online Figure 1: Overall learning and planning framework. In green we indicate our major contributions. In this paper, we evolve this framework by leveraging information from existing symbolic temporal planning heuristics as shown in Figure 1 . We start by considering different reward schemata for the framework (all capturing the temporal plan validity) and by defining a “truncation bootstrap” method to cope with the problem of truncation of episodes: since the MDP derived from a temporal planning problem is potentially infinite, we need to truncate episodes after a certain number of steps, and we use the symbolic heuristic to provide a value function estimation in the last state of the episode avoiding learning issues and allowing for better generalization. Then, we propose to reframe the learning problem from the eager synthesis of a heuristic function to the learning of an additive residual over an existing symbolic heuristic: the key intuition is to simplify the learning task by providing a template function to correct instead of eagerly regressing the whole function from scratch, resulting in a more regular target function. Finally, we modify the inference phase employing a multiple-queue planning approach, where one queue is ordered using a standard symbolic heuristic in an A^{*} fashion, while the other is ordered using the learned value function as a ranking function. The intuition is that the second queue exploits the learned information greedily, while the first queue provides a systematic exploration of the search space and compensates for learning imperfections easily compared to a single-queue A^{*} approach where the systematic search is controlled by the cumulative cost ( g ). The overall result is a comprehensive learning and planning framework for temporal planning that leverages existing symbolic heuristics at every step. We empirically evaluate all components of the modified framework in isolation and in combination, showing they dramatically outperform the baseline planner with no learned information and significantly improve the results in [ Micheli and Valentini(2021) ] . In this setting of per-domain learning, we are interested in optimizing the online solving time, and not the offline learning time (provided it remains feasible). 2 Problem Definition In this section, we define the learning problem we tackle in this paper. We borrow most of the basics of our problem definition from [ Micheli and Valentini(2021) ] . We use ANML [ Smith et al.(2008)Smith, Frank, and Cushing ] to specify action-based temporal planning problems: our language allows durative actions (similarly to PDDL 2.1 [ Fox and Long(2003) ] ) and ”Intermediate Conditions and Effects”, allowing actions to check for conditions and apply effects at arbitrary points in time during action execution. For the sake of brevity, we do not report the details of the formal planning language here; the details can be found in [ Valentini et al.(2020)Valentini, Micheli, and Cimatti ] . For this paper, we only need to characterize the set of planning problems we