Learning Generalized Reactive Policies using Deep Neural Networks

Edward Groshev, Aviv Tamar, Siddharth Srivastava, Pieter Abbeel

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.

Execution of a learned reactive policy (Steps 1-16) in a grid-based planning task.

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:

  1. Sokoban: A grid-based puzzle where an agent pushes boxes to targets. Training was conducted on 45,000 trajectories from 9x9 grids.
  2. 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.

The final goal state achieved by the policy, demonstrating successful long-horizon planning.

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

Abstract

We present a new approach to learning for planning, where knowledge acquired while solving a given set of planning problems is used to plan faster in related, but new problem instances. We show that a deep neural network can be used to learn and represent a generalized reactive policy (GRP) that maps a problem instance and a state to an action, and that the learned GRPs efficiently solve large classes of challenging problem instances. In contrast to prior efforts in this direction, our approach significantly reduces the dependence of learning on handcrafted domain knowledge or feature selection. Instead, the GRP is trained from scratch using a set of successful execution traces. We show that our approach can also be used to automatically learn a heuristic function that can be used in directed search algorithms. We evaluate our approach using an extensive suite of experiments on two challenging planning problem domains and show that our approach facilitates learning complex decision making policies and powerful heuristic functions with minimal human input.
BibTeX
@inproceedings{groshev2017learning,
  author = {Edward Groshev and Aviv Tamar and Siddharth Srivastava and Pieter Abbeel},
  title = {{Learning Generalized Reactive Policies using Deep Neural Networks}},
  booktitle = {ICAPS},
  year = {2017},
  url = {https://openreview.net/forum?id=uWu44LKKu-},
}
Figure