• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Ambush games in discrete and continuous environments

    Thumbnail
    View/Open
    BOIDOT-DISSERTATION-2017.pdf (4.899Mb)
    Date
    2017-11-22
    Author
    Boidot, Emmanuel
    Metadata
    Show full item record
    Abstract
    We consider an autonomous navigation problem, whereby a traveler aims at traversing an environment in which an adversary sets an ambush. A two players zero- sum game is introduced, describing the initial strategy of the traveler and the ambusher based on a description of the environment and the traveler initial location and desired goal. The process is single-step in the sense that agents do not reevaluate their strategy after the traveler has started moving. Players’ strategies are computed as probabilistic path distributions, a realization of which is the path chosen by the traveler and the ambush location chosen by the ambusher. A parallel is drawn between the discrete problem, where the traveler moves on a network, and the continuous problem, where the traveler moves in a compact subset of R2. Analytical optimal policies are derived. 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 sub-classes of games where the reward function for the ambusher is uniform. This proof is detailed in the discrete and continuous setups. In order to relax the assumptions for the computation of the players’ optimal strategies, a sampling-based approach is proposed, inspired by re- cent sampling-based motion planning techniques. Given a uniform reward function for the ambusher, optimal strategies of the sampled ambush game are proven to converge to the optimal strategy of the continuous ambush game under some sampling and connectivity constraints. 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 non-uniform reward functions for the ambusher. The sampling-based game is used to create example applications for situ- ations where no analytic solution of the Continuous Ambush Game have been identified.This leads to more interesting games, applicable to real-world robots using modern motion planning algorithms. Examples of such games are setups where the traveler’s motion satis- fies Dubins’ kinematic constraints and setups where the reach of the ambusher is dependent on the speed of the traveler.
    URI
    http://hdl.handle.net/1853/59244
    Collections
    • Georgia Tech Theses and Dissertations [23877]
    • School of Aerospace Engineering Theses and Dissertations [1440]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology