PaperlayerView exact revision on arXiv

Source-linked AI summary

QMDP-Net: Deep Learning for Planning under Partial Observability

Peter Karkus, David Hsu, Wee Sun Lee

arXiv:1703.06692v3cs.AIcs.LGcs.NEstat.ML

TL;DR

Planning under partial observability is computationally hard, while constructing or learning POMDP models remains difficult. QMDP-net embeds a parameterized POMDP model and QMDP planning in a differentiable recurrent policy network, and experiments show generalization, transfer, and higher success than QMDP in nearly all tasks.

  • Problem

    Planning under partial observability is computationally hard, and manually constructing POMDP models or learning them from data remains difficult.

  • Method

    QMDP-net is a fully differentiable recurrent policy network that connects a parameterized POMDP model with QMDP to embed planning structure and support end-to-end training.

  • Results

    QMDP-net generalizes to new environments, transfers policies to larger environments, and achieves higher success rates than QMDP in nearly all tasks.

  • Takeaways & Limitations

    End-to-end learning can produce useful models that compensate for limitations of the approximate QMDP algorithm.

  • Takeaways & Limitations

    The experiments rely on task-parameter representations isomorphic to the chosen state space, leaving more general problem classes for future work.

Abstract

from arXiv · show

This paper introduces the QMDP-net, a neural network architecture for planning under partial observability. The QMDP-net combines the strengths of model-free learning and model-based planning. It is a recurrent policy network, but it represents a policy for a parameterized set of tasks by connecting a model with a planning algorithm that solves the model, thus embedding the solution structure of planning in a network learning architecture. The QMDP-net is fully differentiable and allows for end-to-end training. We train a QMDP-net on different tasks so that it can generalize to new ones in the parameterized task set and "transfer" to other similar tasks beyond the set. In preliminary experiments, QMDP-net showed strong performance on several robotic tasks in simulation. Interestingly, while QMDP-net encodes the QMDP algorithm, it sometimes outperforms the QMDP algorithm in the experiments, as a result of end-to-end learning.

1 Introduction

Planning under partial observability requires integrating action-observation history, but exact POMDP solutions are computationally intractable and model construction is difficult. QMDP-net addresses this by embedding approximate planning in a differentiable recurrent network, enabling generalization and strong simulated-robot performance.

  • Motivation: Partial observability prevents agents from determining the exact state from current observations, requiring plans based on histories of actions and observations.POMDPs formalize this setting, but exact solution is computationally intractable and constructing models remains difficult.
  • Approach: QMDP-net combines model-free learning with model-based planning by connecting a POMDP model to an algorithm that solves it inside a recurrent policy network.The approach uses QMDP, a simple and fast approximate POMDP algorithm.
  • Architecture: A Bayesian filter integrates action-observation history into a belief, while a differentiable QMDP module selects actions from that belief.Both modules are differentiable, so the complete network can be trained end-to-end.
  • Results: Training on expert demonstrations in randomly generated environments produces policies that generalize to new environments and transfer to more complex environments.The figure illustrates transfer from generated grid worlds to a much larger real-life environment represented by a LIDAR map.
  • Results: Preliminary simulation experiments found that QMDP-net outperformed state-of-the-art network architectures on several robotic tasks and sometimes exceeded QMDP itself.It also solved difficult long-horizon POMDPs such as Hallway2.

2 Background

POMDPs represent uncertainty with beliefs over latent states and update those beliefs from action-observation histories. The paper positions QMDP-net as an end-to-end alternative that embeds both model learning and approximate planning in an RNN.

  • POMDP formulation: A POMDP is defined by state, action, observation, transition, observation, and reward components, with transitions and observations represented probabilistically.The transition function gives the probability of a next state, while the observation function gives the probability of an observation after an action.
  • Belief state: Under partial observability, the agent maintains a belief distribution over states and updates it recursively with a Bayesian filter.The belief summarizes information accumulated from prior actions and observations.
  • Planning objective: POMDP planning seeks a policy that maximizes expected total discounted reward over future states and actions.The discount factor γ lies between 0 and 1.
  • Learning paradigms: Model-based methods learn or specify models and solve them through planning, whereas direct policy learning is end-to-end but does not exploit model information for generalization.The paper frames these as complementary approaches rather than equivalent procedures.
  • QMDP-net: QMDP-net combines both paradigms by embedding a model and planning algorithm in an RNN and training the resulting policy end-to-end.This architecture aims to retain model-based structure while learning a policy directly.
  • Related work: Earlier recurrent approaches handled partial observability, but the cited generic LSTM approach did not embed planning-specific algorithmic structure.The related navigation work generalized over goals in a fixed environment.

3 Overview

QMDP-net represents policies for parameterized partially observable tasks by embedding a parameterized POMDP model and an approximate planner in a differentiable recurrent network. Its learned model may be useful rather than physically correct, and training evaluates generalization across task parameters.

  • Task setting: The target is a policy that acts effectively across diverse partially observable stochastic environments sharing underlying reasoning despite differing task parameters.In robot navigation, parameters can include maps, goals, and beliefs over initial states.
  • Overview: QMDP-net represents a parameterized task family by connecting a parameterized POMDP model with an approximate POMDP algorithm in one differentiable recurrent network.Embedding the model supports generalization, while embedding the algorithm permits end-to-end training.
  • Model representation: The embedded model uses manually chosen abstract state, action, and observation spaces, while transition, observation, and reward functions are learned from data.Abstraction can reduce representational and computational complexity, such as representing continuous navigation with a finite grid.
  • Learned models: Because QMDP is approximate, end-to-end learning may produce an alternative model that compensates for its limitations and improves the resulting policy.The paper explicitly distinguishes optimizing policy quality from recovering a correct underlying model.
  • Planning modules: The architecture combines a Bayesian filter for belief estimation with QMDP, which selects actions using one-step look-ahead over fully observable MDP values weighted by belief.These are the two principal computational modules of QMDP-net.
  • Evaluation: The evaluation trains on expert trajectories with sampled task parameters and tests on new parameters without access to ground-truth states or beliefs.Training uses demonstrated action-observation sequences and cross-entropy loss.

4 QMDP-Net

QMDP-Net is a recurrent policy network that embeds a parameterized POMDP model and the QMDP planning algorithm in a fully differentiable architecture. Its Bayesian filter updates beliefs from actions and observations, while its planner performs approximate value iteration and selects actions from the current belief.

  • Architecture: The network receives the previous action, current observation, and task parameter, then outputs the next action for the task.This recurrent policy is conditioned on θ and is intended for a parameterized task set.
  • Architecture: QMDP-Net encodes a parameterized POMDP model and the QMDP algorithm, with model states, actions, and observations potentially abstracting real-world task variables.The model is conditioned on task parameters and is manually specified over shared state, action, and observation spaces.
  • Differentiable learning: Both modules are differentiable, enabling end-to-end training and extension from discrete planning models to continuous tasks through learned mappings.Learned functions can map real-world states, actions, and observations to the discrete model used for planning.
  • Bayesian filter: The filter module integrates actions and observations into a probabilistic belief over the agent’s state.It first accounts for actions, then incorporates observations and normalizes the updated belief.
  • QMDP planner: The planner performs K tied Bellman-update iterations to compute approximate Q values, weights them by the belief, and maps the resulting action values to the output action.Value iteration is implemented with convolutional and max-pooling layers, while a low-level policy function produces the final action.

5 Experiments

Experiments evaluate QMDP-net and alternative recurrent architectures on simulated navigation and grasping tasks, emphasizing generalization, structure priors, learned models, and transfer to larger environments.

  • Experimental setup: Experiments compare QMDP-net variants and generic alternatives on simulated robot navigation and manipulation tasks designed to test structure priors.Variants relax planning constraints or replace the Bayesian filter, while CNN+LSTM and related architectures omit POMDP structure priors.
  • Experimental setup: The task suites include uncertain grid-world and maze navigation plus 2-D object grasping with noisy touch sensing and unseen objects.Navigation involves uncertain pose, stochastic actions or observations, and, in mazes, orientation-dependent observations; grasping tests generalization across objects.
  • Scope: The task-parameter representation is isomorphic to the chosen state space in these experiments, limiting the demonstrated scope of the architecture.More general task classes are identified as future work.
  • Results and discussion: QMDP-net generalizes to new environments, achieving higher success rates and faster completion times than alternatives in nearly all domains when success rates are comparable.Completion time is meaningful only when success rates are similar.
  • Results and discussion: POMDP structure priors improve learning complex policies, although overly strong constraints can degrade performance by reducing flexibility between filter and planner transition representations.Untying corresponding transition weights can permit different approximations in the filter and planner.
  • Results and discussion: End-to-end training lets QMDP-net learn useful alternative models that compensate for QMDP’s approximation limits, including on the myopic Hallway2 domain.The network sometimes achieves higher success rates than QMDP despite using the same planning algorithm.
  • Results and discussion: Policies trained in 30×30 grid worlds transfer to larger environments by expanding the planning module to K = 450 recurrent layers.The transferred policy was applied to larger real-life environments, including Intel Lab and Freiburg, using LIDAR maps.

6 Conclusion

QMDP-net embeds POMDP structure and QMDP planning in a differentiable recurrent policy network. Simulated robotic experiments show generalization and transfer, while also revealing limitations in state representation and approximate planning.

  • Contribution: QMDP-net embeds POMDP structure and a planning algorithm in a fully differentiable recurrent network for end-to-end training.It learns how to model and solve planning tasks rather than only mapping inputs directly to outputs.
  • Results: Experiments show that QMDP-net policies generalize to new environments and transfer to larger environments, with structure priors and end-to-end training improving performance.Learned policies sometimes outperform QMDP despite encoding the QMDP algorithm.
  • Limitations: The current approach is limited by value iteration over the entire state space, QMDP’s strong approximations, and reliance on imitation learning.Future directions include abstract or hierarchical representations, more sophisticated POMDP algorithms, and reinforcement learning.

A.1 Navigation on Large LIDAR Maps

Large-map experiments test whether a QMDP-net trained on small random grids can transfer by expanding its planning module. The results also examine how iteration count and model design affect navigation quality.

  • Transfer to large LIDAR maps: The policy is trained on 30×30-D random grids with K = 90 and executed on real LIDAR maps with larger K settings.The maps include Intel Research Lab, Freiburg Building 079, Belgioioso Castle, and the western MIT CSAIL wing.
  • Effect of planning depth: Ktest = 2Ktrain significantly improved success rates in all test cases.Increasing K can improve latent-value estimation and reward propagation, but an excessively high K can degrade performance because the learned model may be overfitted to the training setting.
  • Effect of planning depth: Ktest = 5Ktrain further improved success rates for Intel and Belgioioso but slightly decreased them for Freiburg and MIT.The effect of increasing planning depth therefore varied across environments.
  • Architecture and transfer: Untied QMDP-net performed poorly because its planning layers cannot be expanded during execution.Other alternative architectures were specific to the input size and were therefore not applicable to this transfer setting.
  • Value-function visualization: The learned value function assigns high values to states close to the goal in the 18 × 18 stochastic grid task.The visualization used K = 54 QMDP iterations.
  • Belief propagation: In a noisy 18 × 18 task, the learned filter maintains uncertainty initially, then supports movement toward the goal as the belief distribution becomes concentrated.The robot stays for two steps under a highly uncertain initial belief before moving left and subsequently toward the goal.

B.3 State-Transition Function

The learned transition functions in QMDP-net represent the same underlying dynamics but are allowed to differ between filtering and planning. Learned rewards are task-relevant abstractions rather than direct copies of the underlying rewards.

  • Transition functions: The filter and planner learn separate transition functions even though both represent the same underlying transition dynamics.Untied weights let each module choose its own approximation.
  • Transition functions: Planner action abstractions do not necessarily match the transition probabilities of the corresponding original agent actions.The learned planner transitions therefore need not reproduce the environment’s action-level probabilities exactly.
  • Reward function: Learned rewards assign negative values to obstacles and positive values to the goal, although they do not directly correspond to the underlying task rewards.Because rewards are defined after an action, they should be interpreted together with the planner’s transition probabilities.

C Implementation Details

The implementation instantiates QMDP-net across navigation, grasping, Hallway2, and real-map settings with task-specific state, action, observation, and convolutional structures. Training uses expert trajectories from ground-truth POMDPs, while the learned agent does not access those models during learning.

  • Grid-world navigation: Grid navigation uses randomly generated N×N environments with obstacle probability p=0.25, five actions, local binary observations, and deterministic or stochastic dynamics.In the stochastic variant, each action fails with probability Pt = 0.2.
  • Training protocol: Expert trajectories come from QMDP solutions of ground-truth POMDPs, but the learning agent does not access ground-truth models or post-initial true beliefs.Training uses 10,000 random grids with five trajectories per grid.
  • Network implementation: The QMDP-net model uses separate convolutional transition components for filtering and planning, with CNNs for rewards and observations.The transition kernels are 3×3, while the reward and observation modules use two-layer CNNs.
  • Model assumptions: The 3×3 transition and observation convolutions impose local, spatially invariant structure, although spatial invariance does not hold in the underlying obstacle-dependent task.The model’s flexibility can nevertheless learn high-quality policies through reward and observation shaping.
  • Maze navigation: Maze navigation adds four orientations to the N×N state grid and uses four actions for forward motion, turning, and staying.The maze implementation treats the orientation dimension as channels of a 2-D convolutional network.
  • Grasping: The grasping task uses a 14×14 workspace, noisy motion, touch sensors, 20 training objects, and 10 unseen test objects.Policies are trained from expert trajectories generated by solving ground-truth POMDPs.
  • Hallway2: Hallway2 is evaluated as a difficult, noisy maze instance after training on random 8×8 grids with matching transitions.The trial is unsuccessful after 251 steps.
  • Large LIDAR maps: Real-map navigation uses thresholded grayscale SLAM maps in simulation, with a policy trained on 30×30-D grids and executed using K = 450.The maps include Intel, Freiburg, Belgioioso, and MIT environments.

C.6 Architectures for Comparison

QMDP-net is compared with variants that remove embedded POMDP structure and with generic recurrent architectures. The comparisons use tuned alternative networks and reveal the trade-off between structural priors and flexibility.

  • Compared architectures: The comparison includes Untied QMDP-net, LSTM QMDP-net, CNN+LSTM, and a vanilla RNN, with additional GRU and ConvLSTM trials.GRU and ConvLSTM performed worse than CNN+LSTM for most tasks.
  • QMDP-net variants: Untied QMDP-net removes tied transition weights and their softmax normalization, allowing different transition models at each value-iteration step.It can represent the same policy as QMDP-net while adding flexibility.
  • QMDP-net variants: LSTM QMDP-net replaces QMDP-net’s Bayesian filter with a generic LSTM while retaining the value-iteration planner.The LSTM produces a belief estimate that is passed to the planner.
  • Generic recurrent baselines: CNN+LSTM processes image inputs with a CNN and action-observation inputs with a fully connected network before combining them in an LSTM.This architecture is trained with the same expert trajectories as QMDP-net.
  • Generic recurrent baselines: The vanilla RNN uses 512 hidden units with tanh activation and produces actions through a softmax output layer.Inputs are concatenated before recurrent processing.
  • Experimental protocol: Alternative architectures are tuned through hyperparameter search on deterministic grid navigation and then evaluated using the selected parametrization across tasks.The search varies layers, hidden units, learning rate, and batch size.

C.7 Training Technique

The networks are trained end-to-end through imitation learning, using demonstrated actions rather than supervision from ground-truth POMDP models. Training progressively increases trajectory length to handle the difficulty of filtering long observation sequences, with task-specific settings for grid navigation.

  • Training uses cross-entropy between predicted and demonstrated actions, without supervision from ground-truth POMDP models.
  • Networks are optimized with backpropagation through time on mini-batches of 100 using RMSProp.The learning rates are 1 × 10^-3 for QMDP-net and 1 × 10^-4 for alternatives.
  • Training begins on shorter expert-trajectory segments and proceeds to full trajectories after convergence.This schedule addresses increasingly difficult predictions that require filtering information across long observation sequences.
  • For fixed-grid navigation, training varies only the initial state and goal and uses one round with L1 = 100.A low learning rate degraded final performance for the alternative networks in this variant.
Loading 1703.06692v3…