Multilevel Monte-Carlo for Solving POMDPs Online
This work addresses the problem of efficient planning under partial observability for autonomous robots, particularly in systems with complex dynamics, representing an incremental advancement in POMDP solver methods.
The paper tackles the challenge of solving POMDPs with complex dynamics, which are computationally expensive due to costly forward simulations, by proposing MLPP, a new online solver that combines Monte-Carlo Tree Search with Multilevel Monte-Carlo, resulting in substantial performance improvements over state-of-the-art solvers in experiments on torque control, navigation, and grasping problems.
Planning under partial obervability is essential for autonomous robots. A principled way to address such planning problems is the Partially Observable Markov Decision Process (POMDP). Although solving POMDPs is computationally intractable, substantial advancements have been achieved in developing approximate POMDP solvers in the past two decades. However, computing robust solutions for systems with complex dynamics remain challenging. Most on-line solvers rely on a large number of forward-simulations and standard Monte-Carlo methods to compute the expected outcomes of actions the robot can perform. For systems with complex dynamics, e.g., those with non-linear dynamics that admit no closed form solution, even a single forward simulation can be prohibitively expensive. Of course, this issue exacerbates for problems with long planning horizons. This paper aims to alleviate the above difficulty. To this end, we propose a new on-line POMDP solver, called Multilevel POMDP Planner (MLPP), that combines the commonly known Monte-Carlo-Tree-Search with the concept of Multilevel Monte-Carlo to speed-up our capability in generating approximately optimal solutions for POMDPs with complex dynamics. Experiments on four different problems of POMDP-based torque control, navigation and grasping indicate that MLPP substantially outperforms state-of-the-art POMDP solvers.