PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Generalized Reactive Policies using Deep Neural Networks

Edward Groshev, Maxwell Goldstein, Aviv Tamar, Siddharth Srivastava, Pieter Abbeel

arXiv:1708.07280v3cs.AI

TL;DR

Planning is computationally challenging, and reusing knowledge across related instances can help plan faster. The paper trains deep neural networks from successful planner traces to produce reactive policies and heuristics; the reported policies achieve 97% success in one-object and 87% in two-object Sokoban, and the networks can support larger instances and heuristic-guided search.

  • Problem

    Planning is computationally challenging, and prior approaches to reusing knowledge have relied on handcrafted domain representations or features.

    Source: Introduction · p. 1

  • Method

    The approach trains deep neural networks on successful planner-generated execution traces to map problem observations and states to actions, and to generate heuristics for directed search.

    Source: Introduction · p. 1

  • Results

    97% success in one-object Sokoban and 87% in two-object Sokoban; learned policies generalize to unseen instances, including larger state spaces, and learned heuristics improve over standard heuristics.

    Source: Introduction · pp. 1–2, Conclusion · p. 8

  • Takeaways & Limitations

    The approach learns policies and heuristics from successful executions with less dependence on handcrafted domain representations, including for image- and graph-structured planning problems.

    Source: Introduction · p. 1

    In Sokoban, policy failures include cycles and difficulty foreseeing long-term dependencies between objects; stochastic policies reduce cycles but can still choose dead-end actions.

    Source: Analysis of Failure Modes · p. 11

Abstract

from arXiv · show

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 \emph{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. Videos of our results are available at goo.gl/Hpy4e3.

Introduction

Planning is computationally difficult, motivating methods that reuse knowledge across related problem instances. The paper learns neural reactive policies and heuristics from successful executions, aiming to generalize with less handcrafted domain representation.

Introduction

  • A deep neural network learns a generalized reactive policy from planner-generated traces, mapping a problem instance and current state to an action and generalizing to unseen, larger instances.The approach combines imitation learning with generalized planning.Source: Introduction · p. 1
  • Learned, representation-independent heuristics can guide directed search and generate training data for progressively larger instances through leapfrogging.The process can be repeated to train policies for larger and more difficult instances.Source: Introduction · p. 1
  • The approach extends DNN policy learning to both image-based Sokoban and graph-structured TSP, whose valid solutions require a Hamiltonian cycle.TSP execution is not efficiently described as a sequence of images.Source: Introduction · pp. 1–2
  • 97% success in one-object Sokoban and 87% in two-object Sokoban demonstrate learned-policy performance on the reported domains.The introduction also presents a non-trivial test-instance solution produced by the policy.Source: Introduction · p. 2

Related Work

  • Unlike prior approaches that rely on expert-selected representations, the method learns reactive behavior from successful plans and executions without additional representational expressions.The paper frames this as useful when successful executions can be observed, while heuristic use with guided search assumes domain representations are available.Source: Related Work · pp. 2–3

Formal Framework

The framework describes planning domains, problem instances, states, and plans, then defines a generalized reactive policy over observations from multiple instances. It also places imitation learning in this setting as learning actions from observation-action demonstrations.

Formal Framework

  • A planning domain specifies binary relations and parameterized actions, while an instance supplies entities, an initial state, and goal conditions.Grounding the relations and actions with the instance entities defines its fluents and legal action set.Source: Formal Framework · p. 3
  • A plan is a sequence of grounded actions that transforms the initial state into one satisfying the goal conditions.The state space consists of truth assignments to the grounded fluents.Source: Formal Framework · p. 3
  • A generalized reactive policy maps observations from multiple instances of one domain to actions legal for the corresponding instance.Imitation learning supplies observation-action trajectories from which a policy is trained to imitate an expert.Source: Formal Framework · p. 3

Learning Generalized Reactive Policies

The method generates planner demonstrations, trains a policy that uses both current and goal observations, and designs convolutional networks for image and graph inputs. Bootstrapping increases trajectory training pairs, while convolutional designs accommodate changing problem sizes.

Learning Generalized Reactive Policies

  • Planner-generated plans for training instances provide observation-action traces for imitation learning, with training and test instances assumed to come from the same distribution.The paper uses the FF planner in its experiments, though it says other PDDL planners can be used.Source: Learning Generalized Reactive Policies · pp. 3–4

Data Bootstrapping

  • Because a generalized policy must account for different goals, pairs of states along a demonstration trajectory can train the policy with one state treated as the goal.The optimality proposition supports using intermediate trajectory states as endpoints; sampling pairs can expand T samples to as many as (T − 1)^2/2.Source: Data Bootstrapping · p. 4

Network Structure

  • The proposed convolutional network shares representations for action and plan-length prediction and uses skip connections to provide observations at each convolution layer.The authors hypothesize that skip connections can facilitate learning repeated planning computations.Source: Network Structure · p. 4
  • For graph planning, graph convolutions operate on node features and neighbors; the TSP representation encodes visited, current, and terminal nodes, making plan-length prediction unnecessary.A Hamiltonian cycle has length n, and the number of visited cities is encoded in the feature matrix.Source: Network Structure · pp. 4–5

Generalization to Different Problem Sizes

  • Keeping a k × k window around the agent after convolution removes the fully connected layer’s fixed-size input constraint, allowing application across grid dimensions.The corresponding graph design shares convolution weights across graph sizes; k = 1 worked well in the experiments.Source: Generalization to Different Problem… · p. 5

Experiments

The section introduces experiments on learning for planning with deep neural networks and states that they address a set of questions.

Experiments

  • The experiments evaluate DNNs for learning to plan and are organized around a set of research questions.The supplied passage introduces the questions but does not state them.Source: Experiments · p. 5

1. What makes a good DNN architecture for learning a GRP?

The experiments examine GRP architectures and policies across image-based Sokoban and graph-based TSP, then test learned heuristics and leap-frogging on larger instances. Deeper networks, skip connections, and plan-length prediction improve aspects of performance, while learned heuristics support search beyond the training sizes.

1. What makes a good DNN architecture for learning a GRP?

  • The evaluation contrasts image-based Sokoban, with state-property goals, against graph-based TSP, with a plan-wide Hamiltonian-cycle condition.Sokoban training used 45k observation-action trajectories; TSP used 1k trajectories, and its chord-graph results were reported in supplementary material.Source: §1 · p. 5

Evaluation of Learned GRPs

  • On 9×9 Sokoban, the best 14-layer architecture solved one-object instances with 97% success and two-object instances with 87% success.The evaluation used previously unseen test problems.Source: Evaluation of Learned GRPs · p. 6
  • For TSP graphs of sizes 4–11, GRP cost increased approximately linearly with graph size, at roughly half the greedy policy’s rate.Both policies were trained and tested on graphs of the same size.Source: Evaluation of Learned GRPs · p. 6

Investigation of Network Structure

  • Deeper networks and skip connections improve two-object Sokoban success; performance levels off after 14 layers, and plan-length prediction improves action accuracy.The authors attribute the difficulty training a 14-layer network without skip connections to gradient propagation.Source: Investigation of Network Structure · p. 6
  • Bootstrapping with a shared representation produced the best reported combination of execution success and plan-length prediction accuracy.This comparison used 25k trajectories from 5k obstacle configurations.Source: Table 1 · p. 6

GRP as a Heuristic Generator

  • On larger Sokoban instances, A* with the learned heuristic produced nearly optimal plans while exploring an order of magnitude fewer states than conventional alternatives.The GRP heuristic was trained on 9×9 instances; differences in Figure 3(b) were significant at p < 1 × 10^-6.Source: Figure 3 · p. 7, GRP as a Heuristic Generator · p. 8
  • On larger TSP graphs, A* with the GRP heuristic was more efficient than the admissible MST heuristic without losing much plan quality, especially relative to greedy search.The reported comparison uses explored states for planning speed and plan cost for quality.Source: Figure 4 · p. 7, GRP as a Heuristic Generator · p. 8

Leap-Frogging Algorithm

  • Leap-frogging significantly improved TSP heuristic performance over standard GRP training, and came close to retraining with optimal data at each graph size.Leap-frogging used optimal solver data only for the 4-node graph, then used larger-instance solutions as training data.Source: Leap-Frogging Algorithm · p. 8

Conclusion

The paper presents imitation-trained deep networks for generalized policies and learned heuristics, and reports potential in Sokoban plus preliminary promise for leapfrogging. It also says deep-network planning remains an area for further exploration.

Conclusion

  • Imitation-trained deep convolutional networks learn generalized policies across problem sizes and provide effective heuristics that improve over standard non-learning heuristics.The approach learns from planner execution traces.Source: Conclusion · p. 8
  • Sokoban results suggest DNNs can extract powerful features and may learn the visual thinking that helps humans solve difficult planning problems.Leapfrogging uses learned heuristics to help search larger instances and generate training data for successively larger instances; preliminary results are promising.Source: Conclusion · p. 8
  • Deep-network planning still has much to explore, with graph and logical-expression representations identified as active research areas.The paper says its results may motivate further research in representation learning for planning.Source: Conclusion · p. 8

Graph Convolution Network

The graph convolution network propagates learned transformations over graph neighborhoods to form node representations. On grid graphs, a particular choice of its function recovers traditional 2-D convolution.

Graph Convolution Network

  • A graph G has node features and edge features, and its propagation rule uses a parametric function over them with each node’s neighborhood.The passage introduces a graph with adjacency matrix A, weighted edges, and a function mapping node and edge features to an output representation.Source: Graph Convolution Network · p. 10
  • For TSP, propagation generates H with n rows and C′ features per node, using learned weights Θ and bias b with ReLU activation.The graph has n nodes, each with a C-dimensional feature vector; Θ and b are learned parameters.Source: Graph Convolution Network · p. 10
  • On grid graphs, a particular fθ makes the propagation rule reduce to traditional 2-D convolution.The proposition specifies a polynomial fθ of degree 2(N−1) with θ ∈ R^(N²) for a filter of size N.Source: Graph Convolution Network · p. 10
  • The proof centers grid coordinates and constructs degree-2(n−1) g so each location has one surviving θ_i,j term.The construction aims for g to take value θ_i,j at (i,j); the unique surviving polynomial term makes g(i,j)=Cθ_i,j.Source: Graph Convolution Network · p. 10

TSP domain heuristic

A graph convolution network supplies a heuristic for A-star search from its predicted probabilities over possible next nodes.

TSP domain heuristic

  • The heuristic is (N−v)(1−p_i)/2, using the predicted probability p_i of moving to node i and scaling by remaining nodes to match partial-path cost.N is the total node count and v is the number of visited nodes in the partial path.Source: TSP domain heuristic · p. 10

Deep VS Shallow Networks

With equal parameter counts, the tested deeper network outperforms the shallow networks on the reported metrics.

Deep VS Shallow Networks

  • The eight-layer network outperforms the two- and one-layer networks with equal parameter counts on next-action classification error and execution success rate.The deep network uses 8 convolution layers with 64 filters per layer; the shallow networks use 2 layers with 256 filters or 1 layer with 512 filters.Source: Table 2 · p. 10, Deep VS Shallow Networks · p. 10

Evaluation of Bootstrap Performance

Data bootstrapping improves the use of training data and results in the Sokoban evaluation, with larger gains on smaller datasets.

Evaluation of Bootstrap Performance

Analysis of Failure Modes

The Sokoban analysis identifies policy failures tied to cycles and long-term dependencies, while task success relates more to plan length and wall configuration than wall count.

Analysis of Failure Modes

  • Deterministic policies can cycle, while stochastic policies reduce this failure but can still choose actions leading to dead ends.Source: Analysis of Failure Modes · p. 11
  • The policy can miss long-term dependencies between objects when choosing which to move first requires more than 20 steps of look-ahead.The authors suggest these scenarios may be infrequent in training and connect this failure to neural-network depth.Source: Analysis of Failure Modes · p. 11, Figure 7 · p. 12
  • Success decreases with plan length, but open areas can be easy for the learned policy despite planner difficulty; wall count has no visible effect.The configuration of walls, rather than their quantity, matters; large open areas create high branching factors for planners while admitting simple policies.Source: Analysis of Failure Modes · p. 11

Sokoban Reproducibility Details

  • Sokoban experiments used a decaying learning rate, with decay settings varying by training-data amount and experiment.With 45k trajectories, d = 5; Table 1 used d = 50, and window size varied across experiments.Source: Sokoban Reproducibility Details · p. 11

TSP Reproducibility Details

  • TSP experiments used four propagation layers with 26 neurons and first-order graph neighbors; enlarging the neighborhood did not improve performance.Training sets contained 1,000 instances for all training and graph sizes.Source: TSP Reproducibility Details · p. 11
  • Figure 6 reports policy success on chord graphs of sizes 3–9, policy performance on sizes 3–9, and leapfrogging results versus greedy on sizes 7–12.Source: Figure 6 · p. 12
Loading 1708.07280v3…