Perseus: Randomized Point-based Value Iteration for POMDPs

Matthijs T. J. Spaan and Nikos Vlassis. Perseus: Randomized Point-based Value Iteration for POMDPs. Journal of Artificial Intelligence Research, 24:195–220, 2005.


pdf [1.3MB]  ps.gz [488.2kB]  


Partially observable Markov decision processes (POMDPs) form an attractive and principled framework for agent planning under uncertainty. Point-based approximate techniques for POMDPs compute a policy based on a finite set of points collected in advance from the agent's belief space. We present a randomized point-based value iteration algorithm called Perseus. The algorithm performs approximate value backup stages, ensuring that in each backup stage the value of each point in the belief set is improved; the key observation is that a single backup may improve the value of many belief points. Contrary to other point-based methods, Perseus backs up only a (randomly selected) subset of points in the belief set, sufficient for improving the value of each belief point in the set. We show how the same idea can be extended to dealing with continuous action spaces. Experimental results show the potential of Perseus in large scale POMDP problems.

BibTeX Entry

  author =       {Matthijs T. J. Spaan and Nikos Vlassis},
  title =        {Perseus: Randomized Point-based Value Iteration for
  journal =      {Journal of Artificial Intelligence Research},
  year =         2005,
  volume =       24,
  pages =        {195--220}

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Generated by (written by Patrick Riley) on Tue Sep 06, 2011 11:22:28 UTC