Introduction
Classical planning—the task of finding a sequence of actions to reach a goal in a deterministic, fully observable environment—is a fundamental challenge in AI. Traditionally, solving these PSPACE-complete problems efficiently has required significant manual effort in feature engineering or the use of formal logical representations like PDDL. This research introduces a deep learning approach that bypasses these requirements by training Deep Neural Networks (DNNs) to learn Generalized Reactive Policies (GRPs) directly from raw state observations, such as grid images or graph structures.
Methodology
The authors frame the problem as Imitation Learning (IL). They use an off-the-shelf planner to generate expert trajectories on small problem instances and train a DNN to predict the next action given the current state and the goal state.
Key methodological innovations include:
- Data Bootstrapping: Every intermediate state in a successful plan is treated as a "goal" for the sub-trajectory leading to it, massively augmenting the training data.
- Specialized Architectures: The model uses CNNs for grid problems and GCNs for graph problems. Skip connections feed the raw input into every layer to simulate the iterative nature of planning algorithms.
- Size-Invariant Design: By applying a fixed-size window around the agent, the network can operate on grids larger than those it was trained on.
- Leapfrogging: This iterative algorithm uses a network trained on small problems as a heuristic to solve medium problems; these new solutions then serve as training data for even larger instances.
Evaluation Domains
The approach was evaluated on two distinct domains:
- Sokoban: A grid-based puzzle where an agent pushes boxes to targets. Training was conducted on 45,000 trajectories from 9x9 grids.
- Traveling Salesperson Problem (TSP): A graph-based routing problem. Training used 1,000 trajectories on graphs ranging from 4 to 12 nodes.
Key Results and Insights
The learned GRPs demonstrated high success rates and significant search speedups. In Sokoban, the policy achieved a 97% success rate on 1-object levels. When used as a heuristic for A search, the GRP explored an order of magnitude fewer states* than the standard Manhattan distance heuristic while maintaining near-optimal plan quality.
Key insights include:
- Auxiliary Tasks: Forcing the network to predict total plan length improves its accuracy in predicting the immediate next action.
- Skip Connections: These were found to be essential for simulating planning-like computations within the network.
- Heuristic Superiority: The learned heuristics successfully internalized domain structure, outperforming hand-crafted alternatives in both Sokoban and TSP.
Limitations and Future Work
Despite its success, the deterministic policy can occasionally fall into infinite loops when encountering unfamiliar scenarios. It also struggles with very long-term dependencies requiring lookahead beyond 20 steps. Future research will explore transitioning from imitation learning to reinforcement learning and applying these techniques to other planning modalities, such as logical expressions.
Summary updated