Learning Efficiency Meets Symmetry Breaking

Yingbin Bai, Sylvie Thiébaux, Felipe Trevizan · 2025

Read Learning Efficiency Meets Symmetry Breaking by Yingbin Bai, Sylvie Thiébaux, Felipe Trevizan (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-2504-19738.txt.

Introduction

Yingbin Bai, Sylvie Thiébaux, and Felipe Trevizan teach planning systems to spot and exploit symmetry in a 2025 paper. Automated planners search huge spaces for action sequences that reach a goal. Graph neural networks can learn search guidance, but their power against symmetric problems, where many states are mirror copies, was largely unexplored.

The authors give planning problems a graph form that is both learnable and symmetry-aware. Two pruning methods, one cutting actions and one cutting states, then trim symmetric duplicates during search. Built into a leading planner, the system solved problems that had beaten it before. Planners for logistics and robotics gain speed by not re-solving the same problem in mirror form.

Catalog record

CREATORYingbin Bai, Sylvie Thiébaux, Felipe Trevizan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-19738

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Efficiency Meets Symmetry Breaking Yingbin Bai, Sylvie Thiébaux, Felipe Trevizan Abstract Learning-based planners leveraging Graph Neural Networks can learn search guidance applicable to large search spaces, yet their potential to address symmetries remains largely unexplored. In this paper, we introduce a graph representation of planning problems allying learning efficiency with the ability to detect symmetries, along with two pruning methods, action pruning and state pruning, designed to manage symmetries during search. The integration of these techniques into Fast Downward achieves a first-time success over LAMA on the latest IPC learning track dataset. Code is released at: https://github.com/bybeye/Distincter . 1 School of Computing, The Australian National University 2 LAAS-CNRS, Université de Toulouse [email protected], [email protected], [email protected] Introduction Over the past two decades, heuristic search has achieved significant success across a variety of planning problems, and has become the standard approach in the field ( Richter and Westphal 2010 ; Höller et al. 2020 ; Corrêa et al. 2022 ; Geißer et al. 2022 ; Klößner, Seipp, and Steinmetz 2023 ) . Nevertheless, even in classical planning, scalability remains a significant challenge for these methods. This has led a growing number of researchers to turn to learning-based methods, particularly using Graph Neural Networks (GNNs) ( Toyer et al. 2020 ; Shen, Trevizan, and Thiébaux 2020 ; Ståhlberg, Bonet, and Geffner 2022 ; Chen, Trevizan, and Thiébaux 2024 ; Horcík and Sír 2024 ; Hao et al. 2024 ; Drexler et al. 2024b ) . Unlike traditional model-based methods, which are reliant solely on analysing planning domain and problem definitions, GNNs are capable of learning patterns and strategies from existing plans to enhance search efficiency and adaptability. However, learning efficiency alone is insufficient to address the challenges inherent in large-scale planning, which often involves a substantial number of symmetrical states ( Wehrle et al. 2015 ; Sievers et al. 2019b ) . Although these states do not affect plan quality, they consume significant computational resources and can considerably slow down the search process. In this paper, we use NNs and GNNs with permutation invariant activation functions to learn a permutation invariant function allowing them to produce consistent outputs for symmetrical inputs. Despite this advantage, the full potential of this feature has not yet been effectively harnessed to detect and break symmetries during the search process. In this paper, we remedy this by introducing a graph representation designed to achieve two key objectives: learning efficiency and symmetry reduction. Leveraging the strengths of this representation, we propose two pruning methodologies: action pruning and state pruning. Action pruning infers symmetries by analyzing object involvement in action parameters, without generating child states nor computing their heuristic value. Additionally, since GNNs can retain invariant outputs for symmetrical inputs, state pruning exploits this property to efficiently identify symmetries between states. To evaluate the proposed techniques, we implemented them on top of Fast Downward ( Helmert 2006 ) in a planner called Distincter and carried out experiments on the 2023 International Planning Competition Learning Track. The overall coverage of Distincter surpasses that of the traditional SOTA method, LAMA ( Richter and Westphal 2010 ) , for the first time in the recent literature on learning planning heuristics, marking a significant milestone for learning-based methods. In terms of related work, recent independent work by ( Drexler et al. 2024b ) removes symmetries in the training set in offline mode, thereby improving training effectiveness. In contrast, our approach focuses on removing symmetries during the search process, so as to enhance search efficiency and scale to large planning problems. Background and notation A lifted planning problem is defined as a tuple \Pi=\langle\mathcal{O},\mathcal{T},\mathcal{P},\mathcal{A},\mathcal{I},\mathcal{G}\rangle , where \mathcal{O} denotes a set of objects, \mathcal{T} is a set of object types, \mathcal{P} consists of first-order predicates, \mathcal{A} comprises action schemas, \mathcal{I} specifies the current (or initial) state, and \mathcal{G} delineates the goal. A predicate p\in\mathcal{P} has parameters x_{p_{1}},\ldots,x_{p_{n}} for p_{n}\in\mathbb{N} , where each parameter requires a specific type of object. A predicate can be instantiated by assigning each x_{i} to an object from \mathcal{O} , resulting in a proposition \rho . A state is an assignment of truth value to the propositions. An action schema a=\langle X_{a},\textit{pre}(a),\textit{add}(a),\textit{del}(a)\rangle is defined as a tuple comprising a list of typed parameters X_{a}=(x_{a_{1}},\ldots x_{a_{n}}) , along with sets of preconditions, add effects, and delete effects, all of which are predicates in \mathcal{P} with parameters from X_{a} . When all parameters of an action schema are instantiated with objects of the required types, the action is referred to as a ground action. A ground action a is applicable in a state s if \textit{pre}(a)\subseteq s . When a is applied to s , the resulting state s^{\prime} is given by (s\setminus\textit{del}(a))\cup\textit{add}(a) . In this context, the state s is referred to as the parent state, and s^{\prime} is known as the child state. Since the set of applicable actions for a parent state is typically not a singleton, expanding a parent state usually generates a set of child states. A sequence of actions a_{1},\ldots,a_{n} is applicable in a state s if there exists a sequence of states s_{0},\ldots,s_{n} such that s_{0}=s , and for each i\in\{1,\ldots,n\} , the state s_{i} is the result of applying a_{i} in s_{i-1} . The aim is to find a plan for a given planning problem \Pi , which is a sequence of ground actions that is applicable in the initial state \mathcal{I} and results in a state s_{n} such that \mathcal{G}\subseteq s_{n} . A colored (or labelled) graph is a tuple G=\langle V,E,c,l\rangle where V is the set of vertices, E is the set of edges, and c (resp. l ) maps vertices (resp. edges) to their color. Two graphs G=\langle V,E,c,l\rangle and G^{\prime}=\langle V^{\prime},E^{\prime},c^{\prime},l^{\prime}\rangle are isomorphic, denoted by G\cong G^{\prime} , if there exists a bijection \tau:V\rightarrow V^{\prime} such that (u,v)\in E iff (\tau(u),\tau(v))\in E^{\prime} , c^{\prime}(\tau(v))=c(v) for all v\in V , and l^{\prime}((\tau(u),\tau(v)))=l((u,v)) for all (u,v)\in E . An automorphism of G is defined as an equivalence relation \sigma representing an isomorphism between G and itself. The set of all automorphisms of G forms a group under the operation of composition, known as the automorphism group \text{Aut}(G) of the graph. The orbit of a vertex v in a graph consists of all vertices that can be transformed into v by any automorphism in \text{Aut}(G) . This implies that any two vertices within the same orbit are structurally equivalent in the graph, maintaining the same connections and roles relative to other vertices and edges. Distincter Typed Instance Learning Graph (TILG) Our graph representation extends the Instance Learning Graph (ILG) ( Chen, Trevizan, and Thiébaux 2024 ) , maintaining similar structures but offering additional information for learning and symmetry detection. The graph’s vertices represent objects and propositions in the initial (current) state and the goal, and edges exist between propositions and the objects in their parameter list. 1 1 1 In the following, we will use the word symmetric to refer to states represented by isomorphic TILG and to objects or propositions that are related via \tau (or \sigma depending on the context). Vertex features capture the object types, the predicates instanciated by the propositions, and whether goal propositions have been achieved. Edge features capture the

Read the complete text