We study the two-player zero-sum extension of the partially observable stochastic shortest-path problem where one agent has only partial information about the environment. We formulate this problem as a partially observable stochastic game (POSG): given a set of target states and negative rewards for each transition, the player with imperfect information maximizes the expected undiscounted total reward until a target state is reached. The second player with the perfect information aims for the opposite. We base our formalism on POSGs with one-sided observability (OS-POSGs) and give the following contributions: (1) we introduce a novel heuristic search value iteration algorithm that iteratively solves depth-limited variants of the game, (2) we derive the bound on the depth guaranteeing an arbitrary precision, (3) we propose a novel upper-bound estimation that allows early terminations, and (4) we experimentally evaluate the algorithm on a pursuit-evasion game.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Solving partially observable stochastic shortest-path games


    Beteiligte:

    Erscheinungsdatum :

    01.01.2021


    Anmerkungen:

    Tomášek P, Horák K, Aradhye A, Bošanský B, Chatterjee K. Solving partially observable stochastic shortest-path games. In: 30th International Joint Conference on Artificial Intelligence . International Joint Conferences on Artificial Intelligence; 2021:4182-4189. doi: 10.24963/ijcai.2021/575


    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    629



    Research on Dynamic Stochastic Shortest Path Problem

    Pan, Fanlu / Zhang, Yang | ASCE | 2010


    Some recent results on the control of partially observable stochastic systems

    Christopeit, N. / Kohlmann, M. | Springer Verlag | 1982


    Solving Fuzzy Shortest Path Problem with Decision Maker’s Perspective

    Singh, Vishnu Pratap / Sharma, Kirti / Jain, Udit | Springer Verlag | 2021



    UAV PATH PLANNING FOR WILDFIRE TRACKING USING PARTIALLY OBSERVABLE MARKOV DECISION PROCESS

    Shobeiry, Poorya / Xin, Ming / Hu, Xiaolin et al. | TIBKAT | 2021