Multilevel Monte-Carlo for Solving POMDPs Online

Marcus Hoerger*, Hanna Kurniawati, Alberto Elfes

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Citation (Scopus)

    Abstract

    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 remains 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.

    Original languageEnglish
    Title of host publicationRobotics Research - The 19th International Symposium ISRR
    EditorsTamim Asfour, Eiichi Yoshida, Jaeheung Park, Henrik Christensen, Oussama Khatib
    PublisherSpringer Nature
    Pages174-190
    Number of pages17
    ISBN (Print)9783030954581
    DOIs
    Publication statusPublished - 2022
    Event17th International Symposium of Robotics Research, ISRR 2019 - Hanoi, Viet Nam
    Duration: 6 Oct 201910 Oct 2019

    Publication series

    NameSpringer Proceedings in Advanced Robotics
    Volume20 SPAR
    ISSN (Print)2511-1256
    ISSN (Electronic)2511-1264

    Conference

    Conference17th International Symposium of Robotics Research, ISRR 2019
    Country/TerritoryViet Nam
    CityHanoi
    Period6/10/1910/10/19

    Fingerprint

    Dive into the research topics of 'Multilevel Monte-Carlo for Solving POMDPs Online'. Together they form a unique fingerprint.

    Cite this