Heuristic Search Value Iteration for POMDPs

By Trey Smith, Reid G. Simmons. 2004

578 citations recorded by the source corpus.

We present a novel POMDP planning algorithm called heuristic search value iteration (HSVI). HSVI is an anytime algorithm that returns a policy and a provable bound on its regret with respect to the optimal policy. HSVI gets its power by combining two well-known techniques: attention-focusing search heuristics and piecewise linear convex representations of the value function. HSVI's soundness and convergence have been proven. On some bench-mark problems from the literature, HSVI displays speedups of greater than 100 with respect to other state-of-the-art POMDP value iteration algorithms. We also apply HSVI to a new rover exploration problem 10 times larger than most POMDP problems in the literature.

Subfields: Industrial and Manufacturing Engineering, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Industrial and Manufacturing Engineering

In Numerical Analysis

Citations in the corpus

Hilbert Space Embeddings of POMDPs (2012, background): “…that take advantage of the piece-wise linear and convex (PWLC) property (PBVI [Pineau et al., 2003], Perseus [Spaan and Vlassis, 2005], HSVI [Smith and Simmons, 2004]), where these last approaches use the fact that value functions computed by finite-step value iteration algorithms are PWLC…”
Anytime Point-Based Approximations for Large POMDPs (2006, methodology): “HSVI seems to offer good control performance on the full range of tasks, but requires bigger controllers, and is therefore probably slower, especially on domains with high stochasticity (e.g., Tiger-grid Tiger-grid”
Point-Based POMDP Algorithms: Improved Analysis and Implementation (2005, methodology): “This idea, which is not used in the sample spacing argument, is the basis of a second type of convergence result [Zhang and Zhang, 2001, Smith and Simmons, 2004], in which the error bound is derived from the fact that B samples enough of the search tree to some depth.”
Perseus: Randomized Point-based Value Iteration for POMDPs (2005, methodology): “…and Tiger-grid problems (introduced by Littman et al., 1995) are maze domains that have been commonly used to test scalable POMDP solution techniques (Littman et al., 1995; Brafman, 1997; Zhou & Hansen, 2001; Pineau et al., 2003; Smith & Simmons, 2004; Spaan & Vlassis, 2004; Poupart, 2005).”
Black-Box Policy Search with Probabilistic Programs (2015, unknown): “These three domains are examples of deterministic POMDPs, in which the initial state of the world is not known, and observations may be noisy, but the state transitions are deterministic.”
A Bayesian Approach for Learning and Planning in Partially Observable Markov Decision Processes (2011, methodology): “…(Paquet et al., 2005; Ross et al., 2008c) have a clear advantage over offline finite POMDP solvers (Pineau et al., 2003; Spaan and Vlassis, 2005; Smith and Simmons, 2004) in the context of the BAPOMDP as they can be applied directly in infinite POMDPs, provided we have an efficient way to…”
Decentralized planning under uncertainty for teams of communicating agents (2006, methodology): “In recent years a number of approximate algorithms including PBVI [19], BPI [20], HSVI [23], and Perseus [24] have been proposed, which allow for solving larger POMDP domains by, e.”
Planning under Uncertainty for Robotic Tasks with Mixed Observability (2010, methodology): “The Rock Sample problem [25] has frequently been used to test the scalability of new POMDP algorithms.”
Online Planning Algorithms for POMDPs (2008, methodology): “A heuristic similar to AEMS2 was also used by Smith and Simmons (2004) for their offline value iteration algorithm HSVI as a way to pick the next belief point at which to perform α-vector backups.”
Learning to plan with uncertain topological maps (2020, unknown): “Approaches for finding optimal solutions have been intensively investigated in the 2000s, ranging from dynamic programming [26] to heuristic search methods [51,30].”
POMDP-Based Statistical Spoken Dialog Systems: A Review (2013, methodology): “Optimization by planning under uncertainty is attractive in that optimization methods are principled, and in some cases provide well-defined optimality bounds [17], [19].”
Point-Based Value Iteration for Continuous POMDPs (2006, background): “, 2001) and one must resort to the exploitation of model-specific structural properties to obtain approximate scalable algorithms for POMDPs with large state spaces (Boutilier and Poole, 1996; Roy and Gordon, 2003; Poupart and Boutilier, 2003, 2005) and complex policy spaces (Pineau et al., 2003a; S”
Monte-Carlo Planning in Large POMDPs (2010, methodology): “The rocksample (n, k) problem [14] simulates a Mars explorer robot in an n × n grid containing k rocks.”
DESPOT: Online POMDP Planning with Regularization (2013, methodology): “The simplest default policy is a fixed-action policy with the highest expected total discounted reward (Smith & Simmons, 2004).”
Solving Partially Observable Stochastic Games with Public Observations (2019, methodology): “…and concave in the belief of the minimizing player; (3) We introduce a novel algo-rithm based on Heuristic Value Iteration Search (HSVI) for One-Sided POSGs (Horak, Bosansky, and Pechoucek 2017; Smith and Simmons 2004) and show that this algorithm converges to the (approximate) optimal values.”
The Actor Search Tree Critic (ASTC) for Off-Policy POMDP Learning in Medical Decision Making (2018, background): “Tree-search based solutions usually prunes away less likely observations or actions [20, 21, 22], or expanding fringe nodes according to a predefined heuristic [23, 24, 25].”
Potential-based reward shaping for finite horizon online POMDP planning (2016, methodology): “To evaluate the performance of using PBRS to improve online POMDP planning, we conducted an empirical study that compares agent performancewith andwithout PBRS (using the potential functions summarized in Table 2) in three benchmark POMDP planning problems described below: (1) Tag [16], (2) RockSamp”