Abstract
Learning-based planners leveraging Graph Neural Networks (GNNs) 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.
Introduction
In automated planning, the "state space explosion" is a constant enemy. Many problems contain massive amounts of symmetry—for example, in a logistics task, two identical trucks at the same location are functionally interchangeable. Exploring every possible permutation of these identical objects wastes enormous computational resources.
While traditional planners use "symmetry breaking" to prune these redundant branches, and modern learning-based planners use GNNs to learn search heuristics, these two worlds have rarely met. Existing symmetry detection methods are often too computationally heavy to run during an active search. This work introduces Distincter, a planner designed to make symmetry breaking efficient enough to integrate into a high-performance, GNN-guided system.
Methodology
Distincter introduces three core components to bridge the gap between learning and symmetry breaking:
- Typed Instance Learning Graph (TILG): A new graph representation that explicitly includes object types and static propositions. This provides the GNN with essential context, such as map layouts or adjacency, which is often lost in standard pre-processing.
- Action Pruning: Before generating child states, Distincter uses the TILG and the
Nautylibrary to calculate "orbits" of objects. If two available actions are symmetric (e.g., picking up two identical blocks), it prunes one immediately at the parent level, avoiding the creation of redundant child states. - State Pruning: Leveraging the permutation invariance of GNNs, Distincter uses the network's internal embeddings as a "fingerprint." By hashing the second-to-last layer of the network, the planner can identify and prune symmetric states across different branches of the search tree with minimal overhead.
Experimental Results
The researchers evaluated Distincter using the 2023 International Planning Competition (IPC) Learning Track dataset, covering ten diverse domains such as Blocksworld, Sokoban, and Transport.
Coverage Performance
Distincter achieved a major milestone by outperforming the long-standing state-of-the-art planner, LAMA. As shown in the coverage results, Distincter reached a total coverage of 589 solved problems, compared to LAMA's 563 and other learning-based methods like GOOSE (405) and GPR (478).
Plan Quality
Beyond coverage, the learned heuristics proved effective in producing high-quality plans. In Blocksworld, for instance, Distincter's average plan length was 198, significantly shorter than LAMA's 390, suggesting that the learned heuristics are quite effective at finding efficient paths.
Key Insights and Ideas
The integration of GNNs and symmetry breaking offers several unique advantages:
- GNNs as Symmetry Detectors: Using the GNN's own representation as a symmetry hash key makes pruning "nearly free," as the representation is already computed for heuristic estimation.
- Shallow vs. Deep Pruning: Action pruning acts "shallowly" by preventing state creation, while state pruning acts "deeply" by recognizing previously seen states elsewhere in the tree. The combination of both methods yields the highest efficiency.
Limitations and Future Work
Despite its success, Distincter faces challenges in domains requiring complex geometric reasoning, such as Floortile and Sokoban, where standard GNNs struggle with limited receptive fields. Additionally, the action pruning method uses an over-approximation that, while fast, could theoretically compromise search completeness in edge cases. Future work will focus on more expressive GNN architectures and refining pruning techniques to ensure strict completeness while maintaining performance gains.
Summary updated