Solving Partially Observable Markov Decision Processes (POMDPs) with continuous actions is challenging, particularly for high-dimensional action spaces. To alleviate this difficulty, we propose a new sampling-based online POMDP solver, called AdaptiveDiscretization usingVoronoiTrees (ADVT). It uses Monte Carlo Tree Search in combination with an adaptive discretization of the action space as well as optimistic optimization to efficiently sample high-dimensional continuous action spaces and compute the best action to perform. Specifically, we adaptively discretize the action space for each sampled belief using a hierarchical partition which we call a Voronoi tree. A Voronoi tree is a Binary Space Partitioning (BSP) that implicitly maintains the partition of a cell as the Voronoi diagram of two points sampled from the cell. This partitioning strategy keeps the cost of partitioning and estimating the size of each cell low, even in high-dimensional spaces where many sampled points are required to cover the space well. ADVT uses the estimated sizes of the cells to form an upper-confidence bound of the action values of the cell, and in turn uses the upper-confidence bound to guide the Monte Carlo Tree Search expansion and further discretization of the action space. This strategy enables ADVT to better exploit local information in the action space, leading to an action space discretization that is more adaptive, and hence more efficient in computing good POMDP solutions, compared to existing solvers. Experiments on simulations of four types of benchmark problems indicate that ADVT outperforms and scales substantially better to high-dimensional continuous action spaces, compared to state-of-the-art continuous action POMDP solvers.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Adaptive Discretization Using Voronoi Trees for Continuous-Action POMDPs


    Weitere Titelangaben:

    Springer Proceedings in Advanced Robotics


    Beteiligte:
    LaValle, Steven M. (Herausgeber:in) / O’Kane, Jason M. (Herausgeber:in) / Otte, Michael (Herausgeber:in) / Sadigh, Dorsa (Herausgeber:in) / Tokekar, Pratap (Herausgeber:in) / Hoerger, Marcus (Autor:in) / Kurniawati, Hanna (Autor:in) / Kroese, Dirk (Autor:in) / Ye, Nan (Autor:in)

    Kongress:

    International Workshop on the Algorithmic Foundations of Robotics ; 2022 ; , MD, USA June 22, 2022 - June 24, 2022



    Erscheinungsdatum :

    2022-12-15


    Format / Umfang :

    18 pages





    Medientyp :

    Aufsatz/Kapitel (Buch)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Adaptive Discretization Using Voronoi Trees for Continuous-Action POMDPs

    Hoerger, Marcus / Kurniawati, Hanna / Kroese, Dirk et al. | TIBKAT | 2023


    Strengthening Deterministic Policies for POMDPs

    Winterer, Leonore / Wimmer, Ralf / Jansen, Nils et al. | TIBKAT | 2020



    Real-Time Decision Making for Large POMDPs

    Paquet, S. / Tobin, L. / Chaib-draa, B. et al. | British Library Conference Proceedings | 2005


    A Navigation System for Assistant Robots Using Visually Augmented POMDPs

    López, M. a. / Bergasa, L. M. / Barea, R. et al. | British Library Online Contents | 2005