FHHOP: A Factored Hybrid Heuristic Online Planning Algorithm for Large POMDPs

Zongzhang Zhang, Xiaoping Chen

Introduction

Planning in large-scale, uncertain environments is a fundamental challenge in robotics and AI. This paper introduces FHHOP (Factored Hybrid Heuristic Online Planning), an algorithm designed to make online planning significantly faster and more effective. By combining a hybrid heuristic search with a factored state representation, FHHOP achieves order-of-magnitude speedups over previous state-of-the-art methods.

The POMDP Challenge

Agents in the real world often operate under Partially Observable Markov Decision Processes (POMDPs). They must make decisions with imperfect information, such as a robot with noisy sensors. Two primary hurdles exist:

  1. The Curse of Dimensionality: Tracking an agent's "belief" (a probability distribution over states) becomes computationally overwhelming as the state space grows.
  2. The Search Bottleneck: Online planners must act quickly. Traditional algorithms often focus exclusively on "upper bounds" for exploration, potentially ignoring "lower bound" data that could identify high-quality policies faster.

Methodology

FHHOP utilizes a "Hybrid" strategy to expand its search tree. It maintains two distinct heuristics:

  • Upper Bound ($H_U$): Ensures exploration so the optimal path isn't missed.
  • Lower Bound ($H_L$): Guides the search toward promising variations of the current best policy.

The algorithm dynamically balances these using a weight ($C_i$) based on recent performance improvements.

Visualization of upper and lower value bounds for action selection.

Factored State Representation (MOMDP)

The authors observed that many problems have mixed observability—some state variables (like a robot's own coordinates) are fully known, while others are hidden. By adopting a Mixed Observability MDP (MOMDP) model, FHHOP restricts complex belief updates to hidden variables only, reducing complexity by a factor of $O(|X|^2)$, where $|X|$ is the number of fully observable states.

Key Insights: Profiling the Bottleneck

A critical contribution of this work is the computational profiling of existing algorithms. The authors found that over 95% of runtime in standard benchmarks was consumed by three operations: computing belief states, calculating observation probabilities, and value function updates.

Computational profiling of POMDP operations across benchmarks.

This data-driven insight directly motivated the use of the MOMDP framework to streamline the most expensive parts of the planning process.

Key Results

  • 10x+ Speedups: On benchmarks like Tag, RockSample, and AUV Navigation, FHHOP outperformed the AEMS2 algorithm by more than an order of magnitude.
  • Superior Policy Quality: FHHOP consistently found higher expected rewards than competitors within the same computational budget.
  • Scalability: The algorithm successfully handled the RockSample 11_11 domain (over 247,000 states), outperforming the Monte-Carlo based POMCP algorithm.

Limitations and Future Work

While powerful, FHHOP currently requires manual definition of observable state variables. Future research may focus on automated structure learning to identify these variables. Additionally, transitioning from an AND/OR tree to a graph-based search could eliminate redundant computations for duplicate belief states.

Summary updated

BibTeX
@inproceedings{zhang2012fhhop,
  author = {Zongzhang Zhang and Xiaoping Chen},
  title = {{FHHOP: A Factored Hybrid Heuristic Online Planning Algorithm for Large POMDPs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2012},
  url = {https://openreview.net/forum?id=NsT6y5muxOx},
}
Figure