The partially observable Markov decision process (POMDP) provides a principled mathematical model for integrating perception and planning, a major challenge in robotics. While there are efficient algorithms for moderately large discrete POMDPs, continuous models are often more natural for robotic tasks, and currently there are no practical algorithms that handle continuous POMDPs at an interesting scale. This paper presents an algorithm for continuous-state, continuous-observation POMDPs. We provide experimental results demonstrating its potential in robot planning and learning under uncertainty and a theoretical analysis of its performance. A direct benefit of the algorithm is to simplify model construction.
BagnellJKakadeSNgA. (2003) Policy search by dynamic programming. In: Advances in Neural Information Processing Systems (NIPS), Vol. 16. Vancouver, Canada, 9–11 December 2003. Cambridge, MA: The MIT Press.
2.
BaiHHsuDKochenderferMJ. (2011) Unmanned aircraft collision avoidance using continuous-state POMDPs. In: Proceedings of Robotics: Science and systems, Los Angeles, CA, USA, 27 June–1 July 2011.
3.
BaiHHsuDLeeW (2013) Planning how to learn. In: Proceedings of the IEEE International conference on robotics and automation, Karlsruhe, Germany, 6–10 May 2013, pp. 2853–2859.
4.
BaiHHsuDLeeW. (2010) Monte Carlo value iteration for continuous-state POMDPs. In: HsuD (eds) Algorithmic Foundations of Robotics IX—Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR). Berlin; Heidelberg: Springer, pp. 175–191.
5.
BrechtelSGindeleTDillmannR (2013) Solving continuous POMDPs: Value iteration with incremental learning of an efficient space representation. In: Proceedings of the 30th International conference on machine learning, Atlanta, GA, USA, 16–21 June 2013, pp. 370–378.
6.
BrooksAMakarendoAWilliamsSDurrant-WhyteH (2006) Parametric POMDPs for planning in continuous state spaces. Robotics and Autonomous Systems54(11): 887–897.
7.
ChosetHLynchKHutchinsonS. (2005) Principles of Robot Motion: Theory, Algorithms, and Implementations. Cambridge, MA: The MIT Press.
8.
DavidsonJHutchinsonS (2008) Hyper-particle filtering for stochastic systems. In: Proceedings of the IEEE International conference on robotics and automation, Pasadena, CA, USA, 19–23 May 2008, pp. 2770–2777.
9.
DuffM (2002) Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes. PhD Thesis, University of Massachusetts Amherst, MA, USA.
10.
ErezTSmartW (2010) A scalable method for solving high-dimensional continuous POMDPs using local approximation. In: Proceedings of the 26th conference on uncertainty in artificial intelligence, Catalina Island, CA, USA, 8–11 July 2010.
11.
HansenE (1998) Solving POMDPs by searching in policy space. In: Proceedings of the fourteenth conference on uncertainty in artificial intelligence, Madison, WI, USA, 24–26 July 1998Madison, WI, pp. 211–219.
12.
HauserK (2010) Randomized belief-space replanning in partially-observable continuous spaces. In: Algorithmic Foundations of Robotics IX—Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR). Berlin; Heidelberg: Springer, pp. 193–209.
13.
HausslerD (1992) Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation100(1): 78–150.
14.
HeRBrunskillERoyN (2011) ‘Efficient planning under uncertainty with macro-actions’. Journal of Artificial Intelligence Research40(1): 523–570.
15.
HoeyJPoupartP (2005) Solving POMDPs with continuous or large discrete observation spaces. In: Proceedings of the International joint conference on artificial intelligence, Edinburgh, UK, 30 July–5 August 2005, pp. 1332–1338.
16.
HsiaoKKaelblingLLozano-PérezT (2007) Grasping POMDPs. In: Proceedings of the IEEE International conference on robotics and automation, Roma, Italy, 10–14 April 2007, pp. 4685–4692.
17.
KurniawatiHHsuDLeeW (2008) SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In: Proceedings of robotics: science and systems, Zurich, Switzerland, 25–28 June 2008.
18.
LagoudakisMParrR (2003) Reinforcement learning as classification: Leveraging modern classifiers. In: Proceedings of the International conference on machine learning, Washington DC, USA, 21–24 August 2003, pp. 424–431.
19.
LeeTKimYJ (2013) GPU-based motion planning under uncertainties using POMDP. In: Proceedings of the IEEE International conference on robotics and automation, Karlsruhe, Germany, 6–10 May 2013, pp. 4576–4581.
20.
MeuleauNPeshkinLKimK. (1999) Learning finite-state controllers for partially observable environments. In: Proceedings of the fifteenth conference on uncertainty in artificial intelligence, Stockholm, Sweden, 30 July–1 August 1999, pp. 427–436.
21.
PineauJGordonGThrunS (2003) Point-based value iteration: An anytime algorithm for POMDPs. In: Proceedings of the International joint conference on artificial intelligence, Acapulco, Mexico, 9–15 August 2003, pp. 477–484.
22.
PlattRJrTedrakeRKaelblingL. (2010) Belief space planning assuming maximum likelihood observations. In: Proceedings of robotics: science and systems, Zaragoza, Spain, 27–30 June 2010.
23.
PortaJVlassisNSpaanM. (2006) Point-based value iteration for continuous POMDPs. Journal of Machine Learning Research7: 2329–2367.
24.
PoupartPBoutilierC (2003) Bounded finite state controllers. In: Advances in Neural Information Processing Systems (NIPS), Vol. 16. Cambridge, MA: The MIT Press, pp. 823–830.
25.
PowellW (2007) Approximate Dynamic Programming: Solving the Curses of Dimensionality. Hoboken, NJ: Wiley-Interscience.
26.
PrenticeSRoyN (2007) The belief roadmap: Efficient planning in linear POMDPs by factoring the covariance. In: Proceedings of the International symposium on robotics research.
27.
RossSPineauJPaquetS. (2008) Online planning algorithms for POMDPs. Journal of Artificial Intelligence Research32(1): 663–704.
28.
RoyNThrunS (1999) Coastal navigation with mobile robots. In: Advances in Neural Information Processing Systems (NIPS), Vol. 12. Cambridge, MA: The MIT Press, pp. 1043–1049.
29.
SmithTSimmonsR (2005) Point-based POMDP algorithms: Improved analysis and implementation. In: Proceedings of the twenty-first conference on uncertainty in artificial intelligence, Edinburgh, UK, 26–29 July 2005, pp. 542–547.
30.
SuttonRSBartoAG (1998) Reinforcement Learning. Cambridge, MA: MIT Press.
31.
ThrunS (2000) Monte Carlo POMDPs. In: Advances in Neural Information Processing Systems (NIPS). Cambridge, MA: The MIT Press.
32.
ThrunSBurgardWFoxD (2005) Probabilistic Robotics. Cambridge, MA: The MIT Press.
33.
Van den BergJAbbeelPGoldbergK (2010) LQG-MP: Optimized path planning for robots with motion uncertainty and imperfect state information. In: Proceedings of robotics: science and systems, Zaragoza, Spain, 27–30 June 2010.
34.
Van den BergJPatilSAlterovitzR (2012) Motion planning under uncertainty using iterative local optimization in belief space. International Journal of Robotics Research31(11): 1263–1278.
35.
WangYWonKHsuD. (2012) Monte Carlo Bayesian reinforcement learning. In: Proceedings of the International conference on machine learning, Edinburgh, UK, 26 June–1 July 2012.
