Extending the Applicability of POMDP Solutions to Robotic Tasks
- 23 June 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics
- Vol. 31 (4) , 948-961
Abstract
Partially observable Markov decision processes (POMDPs) are used in many robotic task classes from soccer to household chores. Determining an approximately optimal action policy for POMDPs is PSPACE-complete, and the exponential growth of computation time prohibits solving large tasks. This paper describes two techniques to extend the range of robotic tasks that can be solved using a POMDP. Our first technique reduces the motion constraints of a robot and, then, uses state-of-the-art robotic motion planning techniques to respect the true motion constraints at runtime. We then propose a novel task decomposition that can be applied to some indoor robotic tasks. This decomposition transforms a long time horizon task into a set of shorter tasks. We empirically demonstrate the performance gain provided by these two techniques through simulated execution in a variety of environments. Comparing a direct formulation of a POMDP to solving our proposed reductions, we conclude that the techniques proposed in this paper can provide significant enhancement to current POMDP solution techniques, extending the POMDP instances that can be solved to include large continuous-state robotic tasks.Keywords
Funding Information
- NSF (1139011, IIS 1317849)
- U. S. Army Research Laboratory
- U.S. Army Research Office (W911NF-09-1-0383)
- Data Analysis and Visualization Cyberinfrastructure
- NSF (OCI-0959097)
- NSF Graduate Research Fellowship
This publication has 22 references indexed in Scilit:
- Integrated task and motion planning in belief spaceThe International Journal of Robotics Research, 2013
- Point-Based Policy Transformation: Adapting Policy to Changing POMDP Models2013
- Global motion planning under uncertain motion, sensing, and environment mapAutonomous Robots, 2012
- Motion planning under uncertainty for robotic tasks with long time horizonsThe International Journal of Robotics Research, 2010
- Real-time hierarchical POMDPs for autonomous robot navigationRobotics and Autonomous Systems, 2007
- Field D*: An Interpolation-Based Path Planner and Replanner2007
- Towards robotic assistants in nursing homes: Challenges and resultsRobotics and Autonomous Systems, 2003
- Randomized Kinodynamic PlanningThe International Journal of Robotics Research, 2001
- Optimal paths for a car that goes both forwards and backwardsPacific Journal of Mathematics, 1990
- The Complexity of Markov Decision ProcessesMathematics of Operations Research, 1987