Learning Efficiency Meets Symmetry Breaking

2025/04/28 by Bai, Yingbin, Sylvie Thiébaux, Thiebaux, Sylvie +2
Computer Science · #Multimodal Machine Learning Applications #AI-based Problem Solving and Planning #Advanced Graph Neural Networks

paper · pdf · doi:10.48550/arxiv.2504.19738

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.

Citations

• Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal
• Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits
• Learning Domain-Independent Planning Heuristics with Hypergraph Networks
• Fast Graph Representation Learning with PyTorch Geometric
• How Powerful are Graph Neural Networks?
• Modeling Relational Data with Graph Convolutional Networks
• SGDR: Stochastic Gradient Descent with Warm Restarts
• Practical graph isomorphism, II
• The FF Planning System: Fast Plan Generation Through Heuristic Search
• The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks
• The Fast Downward Planning System

Related

• Symmetries and Expressive Requirements for Learning General Policies
• Learning Search-Space Specific Heuristics Using Neural Networks
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions
• Leveraging Action Relational Structures for Integrated Learning and Planning
• Graph Value Iteration