PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Planning Algorithms for POMDPs

Stéphane Ross, Joelle Pineau, Sébastien Paquet, Brahim Chaib-draa

arXiv:1401.3436v1cs.AI

TL;DR

POMDPs are difficult to solve because exact and approximate offline methods become costly or limited in large domains. This paper surveys online planning approaches, combines them with offline value approximations, and evaluates their performance across domains and metrics. The experiments show that heuristic search methods can perform well in large POMDPs, while their efficiency depends on directing search toward relevant beliefs and available planning time.

  • Problem

    POMDP solution methods face severe computational complexity, while offline approximations can take substantial time or provide limited-quality policies in large domains.

  • Method

    The paper surveys online POMDP algorithms, combines online search with offline bounds or value approximations, and empirically compares methods across domains and metrics.

  • Results

    State-of-the-art online heuristic search methods achieve good performance in large POMDP domains, including domains with large branching factors and state spaces.

  • Takeaways & Limitations

    Online methods improve POMDP scalability by focusing computation on belief nodes with large error that are likely to be reached by promising actions.

  • Takeaways & Limitations

    Online search can become infeasible when planning time is short or when exhaustive belief-tree expansion grows exponentially with depth.

Abstract

from arXiv · show

Partially Observable Markov Decision Processes (POMDPs) provide a rich framework for sequential decision-making under uncertainty in stochastic domains. However, solving a POMDP is often intractable except for small problems due to their complexity. Here, we focus on online approaches that alleviate the computational complexity by computing good local policies at each decision step during the execution. Online algorithms generally consist of a lookahead search to find the best action to execute at each time step in an environment. Our objectives here are to survey the various existing online POMDP methods, analyze their properties and discuss their advantages and disadvantages; and to thoroughly evaluate these online approaches in different environments under various metrics (return, error bound reduction, lower bound improvement). Our experimental results indicate that state-of-the-art online heuristic search methods can handle large POMDP domains efficiently.

1. Introduction

POMDPs model sequential decisions under partial observability, but exact solution is generally computationally intractable. Online methods address this by planning for the current information state, and the paper surveys and evaluates these approaches.

  • POMDPs provide a general model for sequential decision problems in partially observable environments.
  • Finite-horizon POMDPs are PSPACE-complete, while infinite-horizon POMDPs are undecidable.
  • Offline algorithms specify actions for all possible situations before execution but can take more than an hour to solve large problems.
  • Online approaches plan only for the current information state instead of computing an exponentially large contingency plan.
  • Combining rough offline policies with online search heuristics can shorten planning horizons and reduce total computation time.
  • The paper surveys online methods and evaluates them in large POMDP domains using return, error bound reduction, and lower bound improvement.

2. POMDP Model

A POMDP represents uncertain sequential decision-making through states, actions, transitions, rewards, and observations, with belief states summarizing observation history. Value iteration and α-vector methods provide exact or approximate value representations, but their complexity limits scalability.

  • A POMDP is represented by states, actions, transitions, rewards, observations, and an observation function.
  • States are not directly observable, so the agent selects actions using histories of past actions and observations.
  • A belief state is a probability distribution over states that summarizes the relevant information from previous actions and observations.
  • The belief update function τ(b, a, z) computes the next belief from the previous belief, action, and observation.
  • The policy maximizes expected discounted rewards over a finite or infinite horizon, with γ ∈[0, 1) as the discount factor.
  • Finite-horizon optimal value functions are convex and piecewise linear, represented by α-vectors associated with actions.
  • Exact value-function iteration has exponential growth in α-vectors, whereas approximate methods can be polynomial but may produce loose lower bounds.

3. Online Algorithms for POMDPs

Online POMDP planning constructs a good local policy for the current belief rather than a complete policy over all beliefs. This focuses computation on reachable beliefs and can reduce overall planning and execution time, although real-time constraints remain important.

  • Offline policy construction can require substantial time and is often limited to small or mid-size POMDP domains.
  • Online planning searches for a good local policy at the agent’s current belief state.
  • By considering only beliefs reachable from the current belief, online methods focus computation on a smaller set of beliefs.
  • Online methods compute the maximal value for the current belief instead of constructing a full optimal α-vector.
  • Interleaving policy construction with execution often reduces total time, though local policies may require extra execution and planning steps.

3.1 General Framework for Online Planning

Online POMDP algorithms alternate planning and execution: they expand a reachable belief tree, propagate value estimates, execute the selected action, and update the belief and tree after each observation. Search efficiency is improved by pruning or selectively exploring beliefs, but exhaustive depth-limited search remains exponential.

  • Online planning and execution alternate at each time step, with planning selecting the best action for the current belief.
  • Fringe-node values are propagated to the root using Bellman’s equation, often with an offline approximate value function estimating long-term fringe values.
  • After planning, the algorithm executes the selected action, incorporates the new observation, and makes the resulting belief the tree’s new root.
  • Some methods reuse the subtree below the new belief to continue search from previous computations.
  • A D-step lookahead using an approximate value function has error bounded by |V ∗(b) −ˆV D(b)| ≤γDϵ.
  • Exhaustively evaluating reachable beliefs has complexity O((|A||Z|)D|S|2), which is exponential in search depth and may exceed execution-time limits.
  • Online methods therefore limit explored beliefs through branch-and-bound pruning, Monte Carlo sampling, or heuristic search.

3.2 Branch-and-Bound Pruning

Branch-and-Bound pruning accelerates RTBSS by maintaining lower and upper action-value bounds and eliminating provably suboptimal branches during depth-limited search. Its efficiency depends on informative offline bounds and can degrade with many observations.

  • Pruning principle: Branch-and-Bound prunes an action when its upper bound is below another action’s lower bound, proving the former suboptimal at the current belief.No belief reached through the pruned action is considered.
  • RTBSS procedure: RTBSS expands the current belief with depth-first search to a fixed depth D, evaluating fringe nodes with offline lower bounds propagated upward.The search is rooted at the current belief and uses Branch-and-Bound during expansion.
  • Search ordering: Expanding actions in descending upper-bound order maximizes pruning because once one action is pruned, all remaining actions have no higher upper bound.Depth-first search further sharpens bounds on expanded actions.
  • Efficiency: RTBSS efficiency depends on the precision of offline lower and upper bounds: tighter bounds enable more pruning and more efficient search.When pruning is weak, real-time constraints limit the search to short horizons.
  • Limitation: When observations are numerous, RTBSS explores all observations equally, limiting it to short horizons despite potentially low-probability branches.This motivates sampling observations in alternative online methods.
  • Guarantee and outcome: RTBSS guarantees the same error bound as a D-step lookahead and can improve the precision of offline value bounds by a factor γD.Empirical results reported tremendous policy improvements in some domains.

3.3 Monte Carlo Sampling

Monte Carlo online methods reduce observation branching by sampling future observations or trajectories instead of expanding every possibility. They trade pruning guarantees and sample efficiency against deeper or more scalable online planning.

  • Sampling strategy: Monte Carlo search samples observations at each expansion, reducing the branching factor and allowing deeper search within a fixed planning time.The sampled observations define the beliefs considered below each action.
  • McAllester and Singh: McAllester and Singh’s method performs depth-limited search to horizon D using C sampled observations from a generative model at each action choice.Observation probabilities are approximated by sample frequencies.
  • Sampling limitation: Theoretical guarantees require sample counts that grow exponentially with desired accuracy, making the required number infeasible under realistic online time constraints.Returns are usually good in practice with many fewer samples.
  • McAllester and Singh: Monte Carlo estimation cannot guarantee propagation of lower and upper bound properties, so action pruning is unavailable in this method.The original method estimates fringe values using immediate rewards, though offline value estimates could replace them.
  • Rollout: Rollout estimates each root action by averaging discounted returns over M sampled trajectories of depth D that follow an initial policy after the first action.Because only the root branches over actions, Rollout is generally more scalable than McAllester and Singh’s approach.
  • Rollout guarantee: With enough sampling, Rollout is guaranteed with high probability to perform at least as well as its initial policy.Parallel Rollout extends the method by evaluating a set of initial policies and taking the maximum estimated value.

3.4 Heuristic Search

Online heuristic search focuses expansion on fringe beliefs expected to improve the current decision most, using bounds, reachability, and action promise to prioritize nodes. AEMS combines these signals and has a finite-time ε-optimality guarantee under stated conditions.

  • Heuristic-search framework: Heuristic search selects the most relevant reachable fringe beliefs instead of reducing branching through exhaustive Branch-and-Bound or Monte Carlo sampling.Relevance is defined by the potential to improve decisions while expanding few nodes.
  • Search cycle: Heuristic algorithms repeatedly choose a fringe node, expand it, and update ancestor bounds and heuristic references before selecting the next node.The anytime search continues until an ε-optimal action is found or planning time expires.
  • Satia and Lave: Satia and Lave’s heuristic prioritizes likely future beliefs with large value uncertainty, while relying on sufficiently informative offline bounds for efficient pruning.It is most effective when observation probabilities are concentrated on a few outcomes.
  • BI-POMDP: BI-POMDP favors fringe nodes reached by promising actions and loose bounds, but ignores observation probabilities and discounting, potentially exploring low-impact nodes.Its suitability depends on offline upper bounds ranking high-value actions reliably.
  • AEMS: AEMS combines uncertainty, future reachability, and estimated action promise to focus search on nodes that affect the current value and may support computation reuse.It can address large observation or action sets when observations are concentrated and promising actions are identified.
  • AEMS guarantee: AEMS is guaranteed to find an ε-optimal action within finite time when every belief with bound gap above ε assigns positive probability to an upper-bound-maximizing action.This is a sufficient condition rather than an unconditional guarantee.

3.5 Alternatives to Tree Search

Alternatives to tree search address the lack of learning across repeated beliefs by updating value estimates during execution. RTDP-BEL discretizes beliefs and learns tabular values, while SOVI prioritizes encountered beliefs for online value iteration.

  • Motivation: The reviewed alternatives address a limitation of repeated online search: encountering the same belief otherwise requires recomputing its policy from the same offline bounds.Their distinguishing feature is updating initial value functions or learned values over time.
  • RTDP-BEL: RTDP-BEL learns approximate values for visited belief states across successive trials, updating each state from the best action’s estimated Q-value.It initializes unseen beliefs with heuristic values, selects the action with greatest Q(b, a), and updates the visited belief after execution.
  • RTDP-BEL: RTDP-BEL discretizes the belief space so values can be stored in a finite hashtable and generalized to unseen beliefs.The discretization resolution k produces O((k + 1)^|S|) possible discretized beliefs.
  • RTDP-BEL: The discretization required by RTDP-BEL can be difficult to choose and may require substantial memory, exceeding 1GB in some cases.The method’s practical cost grows with the number of possible discretized beliefs.
  • SOVI: SOVI extends HSVI into online value iteration by maintaining a priority queue of encountered beliefs and updating the current belief plus the highest-priority states.Priority reflects how much the value function changed at successor belief states.

3.6 Summary of Online POMDP Algorithms

Most online POMDP algorithms use lookahead search, with pruning, heuristics, and Monte Carlo sampling reducing complexity in different parts of the search.

  • Summary: Most online POMDP approaches use lookahead search and improve scalability through branch-and-bound pruning, search heuristics, or Monte Carlo sampling.These techniques reduce complexity from different angles rather than through a single common mechanism.
  • Summary: Branch-and-bound pruning targets action-space complexity, while Monte Carlo sampling targets observation-space complexity and can also sample actions.Search heuristics reduce complexity by guiding the search toward more promising regions.

4. Empirical Study

The empirical study compares online POMDP approaches across domains using real-time return, error-bound reduction, lower-bound improvement, and search-efficiency metrics. It evaluates methods under common time and bound conditions to assess heuristic efficiency and solution-quality improvement.

  • Environments: The study compares online approaches in Tag and FieldVisionRockSample, the latter chosen for its larger observation space.FieldVisionRockSample is a modified RockSample environment designed to test algorithms under large observation spaces.
  • Experimental setup: Each heuristic is given 1 second per action and the same lower and upper bounds, enabling comparison of real-time search efficiency.The evaluation includes Satia and Lave, BI-POMDP, HSVI-BFS, and AEMS variants.
  • Metrics: Average discounted return is the primary execution metric, while error-bound reduction measures improvement in bounds before versus after online search.The error-bound reduction percentage is defined from the initial and post-search upper and lower bounds at the current belief.
  • Metrics: Lower-bound improvement is included because error-bound reduction does not necessarily reflect true error reduction.The lower bound supplied by the computed policy directly indicates improvement relative to the initial offline lower bound.
  • Efficiency metrics: The study also measures belief nodes, reused nodes, and online planning time to assess complexity and search-tree reuse.Lower complexity can permit larger trees, but tree size does not always correspond to higher error-bound reduction or return.

4.2 Tag

Tag is a large POMDP requiring approximate methods, and its heuristic comparison favors HSVI-BFS, BI-POMDP, and AEMS2. However, the domain’s observation structure limits how strongly the heuristics can differ, motivating evaluation in RockSample.

  • Environment: Tag contains 870 states, 5 actions, and 30 observations, making an approximate POMDP algorithm necessary.The environment is used widely in prior POMDP research.
  • Experimental setup: The Tag evaluation runs each algorithm five times from each of 841 nonterminal starting configurations using a uniform initial belief.The 29 terminal states are excluded from the starting configurations.
  • Metrics: Table 2 reports return, EBR, LBI, belief nodes, reused nodes, and online planning time using FIB as the upper bound and Blind as the lower bound.Results are presented as 95% confidence intervals on the averages.
  • Results: HSVI-BFS, BI-POMDP, and AEMS2 outperform RTBSS, Satia and Lave, and AEMS1 in the Tag environment.The latter methods explore irrelevant nodes because they do not restrict search to the best solution graph, producing lower EBR, LBI, and node reuse.
  • Domain limitation: Tag offers limited heuristic differentiation because only two observations are possible after the first action and observation, with one leading directly to a terminal belief state.The authors therefore move to the larger and more complex RockSample domain.

4.3 RockSample

RockSample evaluates online search heuristics in a partially observable grid where agents use noisy sensing, lower and upper bounds, and real-time planning to select actions. AEMS2 and HSVI-BFS generally achieve the strongest combination of return, bound improvement, node reuse, and online efficiency, although their similarity depends on the observation structure and time constraint.

  • RockSample domain: RockSample[n, k] uses an n × n grid with k binary-valued rocks, and the agent must sample good rocks before exiting.The robot position and rock qualities define the state, while rewards come from sampling rocks and leaving the environment.
  • RockSample domain: Each Checki action produces a noisy Good/Bad observation, while motion is deterministic and the factored belief tracks the robot position plus each rock’s probability of being good.Observation probabilities depend on sensor accuracy, which varies with the robot’s distance from the checked rock.
  • Real-time performance: AEMS2 and HSVI-BFS obtain the highest or near-highest return, whereas Satia and Lave and AEMS1 perform considerably worse with either the Blind or PBVI lower bound.BI-POMDP is similar to the strongest methods with PBVI but performs much worse with the Blind lower bound.
  • Real-time performance: AEMS2 achieves the best error bound reduction and lower bound improvement with both lower bounds, with HSVI-BFS a close second.Higher bound improvement usually corresponds to higher average discounted return; Satia and Lave cannot increase the Blind lower bound.
  • Real-time performance: AEMS2 and HSVI-BFS generally reuse the most nodes, while RTBSS reuses none because it does not store its search tree in memory.Node reuse may partly explain the stronger return and bound results of AEMS2 and HSVI-BFS.
  • Real-time performance: AEMS2 and HSVI-BFS perform similarly overall, but AEMS2 provides slightly better error guarantees within a shorter period; their difference may shrink with few observations.The paper attributes their similarity in this environment partly to the small number of observations, which leads them to expand similar trees.
  • Long-term error reduction: AEMS2 outperforms HSVI-BFS and BI-POMDP under short time constraints, but AEMS2 and HSVI-BFS become statistically similar as available time increases.BI-POMDP stops improving after 1 second because its heuristic omits observation probabilities and the discount factor.

4.4 FieldVisionRockSample

FieldVisionRockSample evaluates online POMDP search in environments with large observation spaces and branching factors. AEMS2 and HSVI-BFS perform consistently well, while long-term bound reduction favors AEMS2.

  • Environment: FieldVisionRockSample exposes all rocks after each action through noisy sensing, eliminating Check actions and creating large observation spaces.The FVRS instances evaluated have 32 and 128 observations.
  • Environment: The FVRS parameter d0 is redefined so sensing remains partially observable, with approximately 50% accuracy at the specified distance.This avoids the near-complete observability caused by using the original RockSample values.
  • Results: There is no clear return winner: AEMS2 outperforms HSVI-BFS in FVRS[5,5], while their performances are similar in FVRS[5,7].BI-POMDP performs well in FVRS[5,5] but worse than AEMS2 and HSVI-BFS in FVRS[5,7].
  • Results: AEMS2 reduces error bounds much more than HSVI-BFS in FVRS[5,5], but not significantly more in FVRS[5,7].The results suggest AEMS2 remains effective as branching factors increase.
  • Results: HSVI-BFS achieves the highest belief-node reuse, not significantly above AEMS2, and both outperform the other methods.Their reuse patterns indicate search is guided toward the most likely beliefs.
  • Results: Over longer runs, AEMS2 converges slightly faster on the lower bound, whereas HSVI-BFS performs worse partly because it expands fewer belief states.The overall performance difference at the one-second limit remains modest.

5. Discussion

The discussion identifies practical trade-offs governing online POMDP planning, including bound quality, information reuse, branching factor, graph structure, and available planning time. Online methods are flexible and anytime, but may repeat computation or require sampling and substantial search time.

  • Bounds: Monotone lower and upper bounds ensure expansions cannot worsen the root belief state's error bound.Expansion makes lower bounds non-decreasing and upper bounds non-increasing.
  • Bounds: Many online algorithms discard bound improvements, so repeated belief states require the same computations again from the original offline bounds.Storing improved bounds in a large table can incur lookup costs and memory exhaustion.
  • Bounds: Point updates may learn slowly: combined RTBSS and RTDP-Bel often require a few thousand episodes before return improves.Such updates are useful in large domains mainly when tasks repeat.
  • Bounds: Alpha-vector updates can improve the lower bound across the belief space, but they may be infeasible under very short action-time constraints.A targeted subset of beliefs may reduce this cost.
  • Implementation: Factored POMDP representations can reduce the cost of repeatedly computing belief transitions and observation probabilities.These quantities are needed for every belief state in the search tree.
  • Search structure: Tree search duplicates beliefs reached by multiple paths, simplifying ancestor updates and fringe selection while increasing representation costs.Graph-based heuristics account for repeated paths by summing their error contributions, with dynamic programming needed for cyclic graphs.
  • Search structure: Finding the best graph fringe node can be impractical because evaluating its heuristic for every fringe node may require exhaustive search.This limitation prevented experiments with the proposed graph heuristic.
  • Online vs. offline time: Planning-time trade-offs depend on task constraints: short online budgets increase the importance of a strong offline value function, while longer budgets reduce it.Large branching factors or expensive successor computation require more online time.

6. Conclusion

The paper surveys online POMDP algorithms and empirically compares them across returns and bound-improvement metrics. AEMS2 and HSVI-BFS perform well in large, highly branching domains, supporting online methods as part of scalable POMDP solving alongside offline bounds.

  • Conclusion: The paper surveys online POMDP algorithms and compares them empirically using discounted return, error bound reduction, and lower bound improvement.The comparisons use PBVI, Blind, FIB, and QMDP bounds.
  • Conclusion: AEMS2 and HSVI-BFS perform very well in domains with large branching factors and state spaces.They guide search toward likely beliefs with large errors that can improve the approximate value function quickly.
  • Conclusion: Online approaches can improve the scalability of POMDP solution methods, while offline algorithms remain important for obtaining tight value-function bounds.The paper frames the central opportunity as exploiting synergy between online and offline approaches.
Loading 1401.3436v1…