An autonomous navigation problem is considered, whereby a traveler aims at traversing an environment in which an adversary sets an ambush. A two-player zero-sum game is introduced describing the players’ initial strategy based on the traveler’s initial location and desired goal, and the description of the environment. The process is single step in the sense that agents do not reevaluate their strategy after the traveler has started moving. The players’ strategies are computed as probabilistic distributions, a realization of which is the path chosen by the traveler and the ambush location chosen by the ambusher. Assumptions from the minimal cut–maximal flow literature for continuous domains are used. The optimal value of the game is shown to be related to the maximum flow on the environment for subclasses of games in which the reward function for the ambusher is uniform over the environment. To relax the assumptions for the computation of the players’ optimal strategies, a sampling-based approach is proposed, inspired by sampling-based motion-planning techniques. Given a uniform reward function for the ambusher, optimal strategies of the sampling-based ambush game are proven to converge to the optimal strategy of the continuous ambush game. A linear program is introduced that allows for the computation of optimal policies. The sampling-based approach is more general in the sense that it is compatible with constrained motion primitives for the traveler and nonuniform reward functions for the ambusher.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Optimal Player Policies for Continuous Ambush Games


    Beteiligte:
    Boidot, Emmanuel (Autor:in) / Marzuoli, Aude (Autor:in) / Feron, Eric (Autor:in)

    Erschienen in:

    Erscheinungsdatum :

    01.09.2018




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    An Attempted Amateur Ambush of Supersports 200

    British Library Online Contents | 1997


    Ambush avoidance in vehicle routing for valuable delivery

    Salani, Matteo / Duyckaerts, Gaëtan / Swartz, Peter Goodings | Springer Verlag | 2010


    Explosion-proof engine cover of landmine-proof ambush-proof vehicle

    FENG SIYONG / MA SHENGJIE / WANG FUJUN et al. | Europäisches Patentamt | 2024

    Freier Zugriff

    The Mechanics of n-Player Differentiable Games

    Balduzzi, D / Racaniere, S / Martens, J et al. | BASE | 2018

    Freier Zugriff