A Heuristic Variable Grid Solution Method for POMDPs

AAAI 1997

TL;DR

This paper introduces a novel heuristic method for solving Partially Observable Markov Decision Processes (POMDPs), a class of problems notoriously difficult to solve exactly. Their "variable grid" approach iteratively refines a discrete approximation of the belief space, focusing computational effort on more informative regions, leading to good performance on larger problems with modest computational cost.

What Problem Does This Paper Address?

Planning under uncertainty is a fundamental challenge in AI. Markov Decision Processes (MDPs) model problems with stochastic actions, but they assume full state observability. Partially Observable Markov Decision Processes (POMDPs) extend this by incorporating noisy sensors, making them more realistic for many real-world scenarios like robotics or medical diagnosis. However, solving POMDPs is computationally intractable. Exact methods can only handle problems with about 10 states. This limitation necessitates approximate methods. The core challenge this paper addresses is developing an efficient and effective approximate solution method for POMDPs that can scale to larger problems than exact methods allow.

Methods

The paper proposes a heuristic, iterative method for solving infinite-horizon POMDPs. The core idea is to approximate the value function over the belief space (which is a continuous space) by discretizing it with a grid. Unlike fixed-grid methods, their approach uses a variable grid that adapts during the solution process.

Here's a breakdown of their method:

  • Initial Grid: The process starts with an initial grid consisting of the "perfect information" belief states, which correspond to the states of the underlying MDP. The value function for these points is initialized using the solution of the underlying MDP (similar to the QMDP method).
  • Iterative Refinement: The algorithm then iteratively refines this grid and the value function.
  • Adding New Grid Points: New belief states are added to the grid based on two criteria:
  • Importance of Information: How much the estimated value function or optimal policy is likely to change within a region of the belief space. This is heuristically assessed by looking at differences in Q-values for actions between pairs of existing grid points.
  • Reachability: How likely it is that the agent will actually reach these new belief states. This is approximated by checking if the agent is likely to receive the same sensor message from the states forming the new belief state.
  • Value Function Update: The value function is updated on the grid points using standard dynamic programming updates, similar to value iteration in MDPs. This process is repeated until the value function stabilizes.
  • Interpolation: To estimate the value function at non-grid points (needed for action selection), they use an interpolation method. This method constructs a belief state as a linear combination of grid states and uses their values. They prioritize grid states where the agent has less information.
  • Policy Generation: The final value function on the grid is used to determine the optimal action for any given belief state by selecting the action that maximizes the estimated Q-value.

Datasets

The paper evaluates their method on two benchmark POMDP domains previously introduced by Littman, Cassandra, and Kaelbling (1995a):

  1. 89-state maze: A robot navigation task where the goal is to reach a target position. The robot has noisy sensors that detect walls.
  2. 33-state maze with negative rewards: A smaller domain designed to highlight the need for actively seeking information, featuring negative rewards for certain states.

Key Insights and Ideas

  • Variable Grids for Efficiency: The core insight is that a dynamically adapting grid, focusing on "interesting" or "likely" belief states, can achieve good approximations with significantly fewer grid points than fixed-grid methods. This is crucial for scalability.
  • Heuristics for Grid Construction: The paper demonstrates that simple, heuristic criteria for adding new grid points (based on value differences and message similarity) can effectively guide the refinement process without excessive computational overhead.
  • Iterative Improvement: The iterative nature of the algorithm, where rough solutions inform the generation of better grids, is a key to its success. This suggests a general paradigm for approximate dynamic programming.
  • Interpolation Matters: The choice of interpolation method is critical, especially for variable grids. Their approach of prioritizing less informative grid states for interpolation is a novel heuristic.
  • "Free" Information Assumption: The paper acknowledges that their current method assumes sensing is instantaneous and "free." Relaxing this assumption would likely require more complex grid generation, as information gathering itself becomes a strategic choice.

Key Results

The paper reports promising results on the tested domains:

  • 89-state maze:
    • Their method with a 337-point grid achieved a 98% success rate and a median of 24 steps to the goal.
  • This significantly outperformed the QMDP method (27% success, >251 steps) and was comparable to or better than other methods like MLS (97% success, 40 steps).
  • Crucially, their 337-point grid is much smaller than the 3916 points required by a fixed-grid method (Lovejoy, 1991a) for comparable performance.
  • 33-state maze with negative rewards:
    • When combined with a "lookahead" step (estimating the value of immediate successor states), their method achieved an average discounted reward (ADR) of 2.35 with a 82-point grid and 2.27 with a 174-point grid.
  • This significantly outperformed QMDP (0.07 ADR) and even the nearest neighbor method (0.45 ADR for 82 points) in this challenging domain.

Limitations and Future Work

  • Computational Cost of Reachability: While they explored reachability analysis for grid construction, it can be computationally expensive for large POMDPs. They suggest that for very large domains, a larger, easily generated grid might be more practical than complex reachability analysis.
  • "Free" Information Assumption: The current method assumes sensing is instantaneous and free. Future work could explore iterative methods that gradually relax this assumption, leading to more complex grid generation as information gathering becomes a strategic element.
  • Domain Specificity: The tested domains are robot navigation tasks with certain symmetries and goal-oriented properties. The authors acknowledge that their method's applicability to more diverse domains needs further investigation.
  • Interpolation Refinements: They suggest further refinements to the grid construction and interpolation methods, potentially incorporating more informed heuristics or better use of current information.
  • General Heuristics: Incorporating general heuristics like loop elimination could further improve policy generation.

Summary updated

BibTeX
@inproceedings{1997heuristic,
  title = {{A Heuristic Variable Grid Solution Method for POMDPs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1997},
}
Figure