A point-based POMDP algorithm for robot planning

Spaan, Matthijs T. J.; VLASSIS, Nikos

Download

Paper published in a book (Scientific congresses, symposiums and conference proceedings)

A point-based POMDP algorithm for robot planning

Spaan, Matthijs T. J.; VLASSIS, Nikos

2004 • In Proc. IEEE Int. Conf. on Robotics and Automation, New Orleans, Louisiana

Peer reviewed

Permalink
https://hdl.handle.net/10993/11057

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

download.pdf

Author postprint (500.06 kB)

Download

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Abstract :

[en] We present an approximate POMDP solution method for robot planning in partially observable environments. Our algorithm belongs to the family of point-based value iteration solution techniques for POMDPs, in which planning is performed only on a sampled set of reachable belief points. We describe a simple, randomized procedure that performs value update steps that strictly improve the value of all belief points in each step. We demonstrate our algorithm on a robotic delivery task in an office environment and on several benchmark problems, for which we compute solutions that are very competitive to those of state-ofthe -art methods in terms of speed and solution quality.

Disciplines :

Computer science

Identifiers :

UNILU:UL-ARTICLE-2011-732

Author, co-author :

Spaan, Matthijs T. J.

VLASSIS, Nikos ; University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)

Language :

English

Title :

A point-based POMDP algorithm for robot planning

Publication date :

2004

Event name :

IEEE Int. Conf. on Robotics and Automation, New Orleans, Louisiana

Event date :

2004

Main work title :

Proc. IEEE Int. Conf. on Robotics and Automation, New Orleans, Louisiana

Pages :

2399-2404

Peer reviewed :

Peer reviewed

Available on ORBilu :

since 17 November 2013

Statistics

Number of views

52 (0 by Unilu)

Number of downloads

640 (0 by Unilu)

More statistics

Scopus citations^®

114

Scopus citations^®
without self-citations

110

Bibliography

J. Latombe, Robot Motion Planning. Kluwer Academic Publishers, 1991.
E. J. Sondik, "The optimal control of partially observable Markov decision processes," Ph.D. dissertation, Stanford University, 1971.
L. P. Kaelbling, M. L. Littman, and A. R. Cassandra, "Planning and acting in partially observable stochastic domains," Artificial Intelligence, vol. 101, pp. 99-134, 1998.
R. Simmons and S. Koenig, "Probabilistic robot navigation in partially observable environments," in Proceedings of the International Joint Conference on Artificial Intelligence, 1995, pp. 1080-1087.
A. R. Cassandra, L. P. Kaelbling, and J. A. Kurien, "Acting under uncertainty: Discrete bayesian models for mobile robot navigation," in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, 1996.
G. Theocharous and S. Mahadevan, "Approximate planning with hierarchical partially observable Markov decision processes for robot navigation," in Proc. IEEE Int. Conf. on Robotics and Automation, Washington D.C., 2002.
C. H. Papadimitriou and J. N. Tsitsiklis, "The complexity of Markov decision processes," Mathematics of operations research, vol. 12, no. 3, pp. 441-450, 1987.
O. Madani, S. Hanks, and A. Condon, "On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems," in Proc. 16th National Conf. on Artificial Intelligence, Orlando, Florida, July 1999.
M. L. Littman, A. R. Cassandra, and L. P. Kaelbling, "Learning policies for partially observable environments: Scaling up," in Proc. 12th Int. Conf. on Machine Learning, San Francisco, CA, 1995.
M. Hauskrecht, "Value function approximations for partially observable Markov decision processes," Journal of Artificial Intelligence Research, vol. 13, pp. 33-95, 2000.
K.-M. Poon, "A fast heuristic algorithm for decision-theoretic planning," Master's thesis, The Hong-Kong University of Science and Technology, 2001.
N. Roy and G. Gordon, "Exponential family PCA for belief compression in POMDPs," in Advances in Neural Information Processing Systems 15. Cambridge, MA: MIT Press, 2003.
J. Pineau, G. Gordon, and S. Thrun, "Point-based value iteration: An anytime algorithm for POMDPs," in Proc. Int. Joint Conf. on Artificial Intelligence, Acapulco, Mexico, Aug. 2003.
N. Vlassis and M. T. J. Spaan, "A fast point-based algorithm for POMDPs," in Benelearn 2004: Proceedings of the Annual Machine Learning Conference of Belgium and the Netherlands, Brussels, Belgium, Jan. 2004, pp. 170-176, (Also presented at the NIPS 16 workshop 'Planning for the Real-world', Whistler, Canada, Dec 2003).
N. Vlassis and M. T. J. Spaan, "A fast point-based algorithm for POMDPs," in Benelearn 2004: Proceedings of the Annual Machine Learning Conference of Belgium and the Netherlands, Brussels, Belgium, Jan. 2004, pp. 170-176, (Also presented at the NIPS 16 workshop 'Planning for the Real-World', Whistler, Canada, Dec 2003).
S. Thrun, "Monte carlo POMDPs," in Advances in Neural Information Processing Systems 12, S. Solla, T. Leen, and K.-R. Müller, Eds. MIT Press, 2000, pp. 1064-1070.
_, "Probabilistic algorithms in robotics," AI Magazine, vol. 21, no. 4, pp. 93-109, Win 2000.
H. T. Cheng, "Algorithms for partially observable Markov decision processes," Ph.D. dissertation, University of British Columbia, 1988.
R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. Cambridge, MA: MIT Press, 1998.
A. Likas, N. Vlassis, and J. J. Verbeek, "The global k-means clustering algorithm," Pattern Recognition, vol. 36, no. 2, pp. 451-461, Feb. 2003.
N. Vlassis, B. Terwijn, and B. Kröse, "Auxiliary particle filter robot localization from high-dimensional sensor observations," in Proc. IEEE Int. Conf. on Robotics and Automation, Washington D.C., May 2002, pp. 7-12.
P. Poupart and C. Boutilier, "Bounded finite state controllers," in Advances in Neural Information Processing Systems 16, S. Thrun, L. Saul, and B. Schölkopf, Eds., 2004.