A POMDP approach to robot motion planning under uncertainty

Motion planning in uncertain and dynamic environments is critical for reliable operation of autonomous robots. Par-tially observable Markov decision processes (POMDPs) pro-vide a principled general framework for such planning tasks and have been successfully applied to several moderately complex robotic tasks, including navigation, manipulation, and target tracking. The challenge now is to scale up POMDP planning algorithms and handle more complex, re-alistic tasks. This paper outlines ideas aimed at overcom-ing two major obstacles to the efficiency of POMDP plan-ning: the “curse of dimensionality ” and the “curse of his-tory”. Our main objective is to show that using these ideas— along with others—POMDP algorithms can be used success-fully for motion planning under uncertainty for robotic tasks with a large number of states or a long time horizon. We im-plemented some of our algorithms as a software package Ap-proximate POMDP Planning Library (APPL), now available for download a