Abstract
Computing goal-directed behavior is essential to designing efficient AI systems. Due to the computational complexity of planning, current approaches rely primarily upon hand-coded symbolic action models and hand-coded heuristic-function generators for efficiency. Learned heuristics for such problems have been of limited utility as they are difficult to apply to problems with objects and object quantities that are significantly different from those in the training data. This paper develops a new approach for learning generalized heuristics in the absence of symbolic action models using deep neural networks that utilize an input predicate vocabulary but are agnostic to object names and quantities. It uses an abstract state representation to facilitate data efficient, generalizable learning. Empirical evaluation on a range of benchmark domains show that in contrast to prior approaches, generalized heuristics computed by this method can be transferred easily to problems with different objects and with object quantities much larger than those in the training data.
Introduction
Automated planning—the process of finding a sequence of actions to reach a goal—is a cornerstone of intelligent behavior but remains computationally expensive. Traditionally, planners rely on heuristics to navigate vast search spaces. However, these heuristics often require hand-coded symbolic action models (like PDDL) or are "brittle," failing to generalize when the number of objects in a problem changes. This research introduces Generalized Relational Heuristic Networks (GHNs), a deep learning approach designed to learn heuristics without requiring symbolic action models while maintaining high generalizability across varying object quantities.
Methodology
The core innovation of GHNs lies in their ability to represent the state of the world through "canonical abstractions." Instead of processing raw object names, which vary between problems, the system groups objects into roles based on the unary predicates they satisfy. For instance, in a robotics domain, all "empty grippers" are treated as a single role. To manage the uncertainty inherent in abstraction, the framework employs three-valued logic (0, 1, and 0.5 for "maybe") to represent relationships between these roles.
As shown in the architecture above, GHNs utilize two sub-networks: an Action Network ($NN_A$) to predict the most likely next action and its parameters, and a Plan Length Network ($NN_{len}$) to estimate the remaining steps to the goal. To train these networks without massive expert datasets, the authors use a "leapfrogging" bootstrapping technique. This involves solving small problems with blind search, training a GHN on those solutions, and then using that GHN to solve progressively larger problems.
Experimental Evaluation
The approach was evaluated on 13 benchmark domains from the International Planning Competition (IPC), including classic puzzles like Blocksworld and Sokoban, as well as logistics tasks like Miconic and Ferry. Generalization was specifically tested by training on small instances (bins $B_0, B_1, B_2$) and testing on significantly larger instances (bin $B_+$).
Key Results and Insights
The empirical evaluation highlights several strengths of the GHN approach:
- Superior Generalization: In domains such as Visitall and Spanner, GHNs significantly outperformed standard planners on large $B_+$ test cases, solving problems with object quantities far beyond their training data.
- Competitive Performance: GHNs were competitive with state-of-the-art planners (like FD LAMA) in 8 out of 13 domains, often expanding a similar number of nodes despite having no access to the action models those planners rely on.
- Data Efficiency: The leapfrogging technique allowed the model to reach peak performance with as few as 400 training problems, demonstrating that complex relational logic can be learned without "Big Data."
Limitations and Future Work
Despite its successes, the abstraction method can sometimes be too "blurry." In the Logistics domain, high object interdependence led to performance drops. Additionally, the current goal-encoding scheme struggles to capture "landmarks" (essential intermediate steps), which affected performance in Goldminer. Future work will explore incorporating first-order logic with transitive closure to better capture long-distance spatial relationships and optimizing the computational overhead of state-to-role conversion.
Summary updated