Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, February 2015. / Cataloged from PDF version of thesis. "October 2014." / Includes bibliographical references (pages 143-149). / This thesis investigates search scenarios in which multiple mobile, self-interested agents, cows in our case, compete to capture targets. The problems considered in this thesis address search strategies that reflect (i) the need to efficiently search for targets given a prior on their location, and (ii) an awareness that the environment in which searching takes place contains other self-interested agents. Surprisingly, problems that feature these elements are largely under-represented in the literature. Granted, the scenarios of interest inherit the challenges and complexities of search theory and game theory alike. Undeterred, this thesis makes a contribution by considering competitive search problems that feature a modest number of agents and take place in simple environments. These restrictions permit an in-depth analysis of the decision-making involved, while preserving interesting options for strategic play. In studying these problems, we report a number of fundamental competitive search game results and, in so doing, begin to populate a toolbox of techniques and results useful for tackling more scenarios. The thesis begins by introducing a collection of problems that fit within the competitive search game framework. We use the example of taxi systems, in which drivers compete to find passengers and garner fares, as a motivational example throughout. Owing to connections with a well-known problem, called the Cow-Path Problem, the agents of interest, which could represent taxis or robots depending on the scenario, will be referred to as cows. To begin, we first consider a one-sided search problem in which a hungry cow, left to her own devices, tries to efficiently find a patch of clover located on a ring. Subsequently, we consider a game in which two cows, guided only by limited prior information, compete to capture a target. We begin by considering a version in which each cow can turn at most once and show this game admits an equilibrium. A dynamic-programming-based approach is then used to extend the result to games featuring at most a finite number of turns. Subsequent chapters consider games that add one or more elements to this basic construct. We consider games where one cow has additional information on the target's location, and games where targets arrive dynamically. For a number of these variants, we characterize equilibrium search strategies. In settings where this proves overly difficult, we characterize search strategies that provide performance within a known factor of the utility that would be achieved in an equilibrium. The thesis closes by highlighting the key ideas discussed and outlining directions of future research. / by Kevin Spieser. / Ph. D.
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/97356 |
| Date | January 2015 |
| Creators | Spieser, Kevin, 1982- |
| Contributors | Emilio Frazzoli., Massachusetts Institute of Technology. Department of Aeronautics and Astronautics., Massachusetts Institute of Technology. Department of Aeronautics and Astronautics. |
| Publisher | Massachusetts Institute of Technology |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 149 pages, application/pdf |
| Rights | M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission., http://dspace.mit.edu/handle/1721.1/7582 |
Page generated in 0.0088 seconds