IIIT Hyderabad Publications |
|||||||||
|
Agent Strategies for the Hide-and-Seek GameAuthor: Akshat Tandon Date: 2020-01-27 Report no: IIIT/TH/2020/7 Advisor:Kamalakar Karlapalem AbstractWe are given an environment with some objects (park with trees, a city block area) and mobile agents moving in the environment. The agents have a limited field of view and visibility range. An agent (hider) can hide behind an object to be not seen by other agents (seekers) through their line of sight (visibility). These hider agents (that are hiding behind objects) can be found by seekers who explore the environment. A pragmatic example of the problem is a warehouse environment or a cordoned off area of the town, with no drones or cameras, and some culprit agents are hiding from the police agents. The aim of hiders is not to be caught for the longest time, and the aim of the seekers is catch all of them in the shortest period of time. We formulate the problem by using visibility based map abstractions. These abstractions involve the notions of coverage, obstruction and escapability. Using these spatial abstractions as basic building blocks, we formulate two kinds of strategies for the agents. The first kind is based on multi-armed bandits in which the agents maintain reward bounds on obstacle edges which they feel are safe to hide or suitable for searching. The second kind focuses on deterministic capture of hiders, even if they are guided by an oracle which knows the future positions of seekers. We built a simulator to create environments for multiple hiders and multiple seekers to test their strategies in a Hide-and-Seek game. We contrast our strategies, and their variants, by empirically comparing their game completion times. Full thesis: pdf Centre for Data Engineering |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |