Files in this item

FilesDescriptionFormat

application/pdf

application/pdfTHAKOOR-THESIS-2017.pdf (519kB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:A game theoretic approach to UAV routing and information collection
Author(s):Thakoor, Omkar P
Advisor(s):Garg, Jugal
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):UAV
routing
Game theory
Nash equilibrium
Price of Anarchy
Abstract:In recent times, the use of Unmanned aerial vehicles (UAVs) for tasks which involve high endurance or perilous environments, has become increasingly vital. A typical problem is that of information collection, in particular when multiple UAVs are involved, which prompts an important problem of routing these UAVs through the search environment with the goal of maximizing the collected information. Most of the previous line of work assumes a centralized control and full communication among the UAVs, thus posing this as an optimization problem solved via centralized solutions. However, in applications where communication is infeasible, each UAV must individually solve the problem. Assuming a natural scenario of UAVs being compensated for the collected information makes them self-interested agents trying to maximize their payoffs. Consequently, our game-theoretic approach is a natural fit. While our game model is primarily based on the game model used in a previous work, it is also significantly generalized, incorporating interesting facets of information fusion and multi-modality-composed information. This game is closely related to the well-studied classes of congestion-type and resource selection games, but cannot be cast into these classes unless certain critical constraints are relaxed. Our contribution to this literature, is a result on existence of pure Nash equilibria via existence of the Finite Improvement Property, which applies to any singleton congestion-type games having a certain class of payoff functions. Finally, to our best knowledge, our results providing theoretically guaranteed tight bounds on the Price of anarchy and Price of stability, are the first such results in the literature involving a game theoretic approach to UAV routing.
Issue Date:2017-04-26
Type:Thesis
URI:http://hdl.handle.net/2142/97785
Rights Information:Copyright 2017 Omkar Thakoor
Date Available in IDEALS:2017-08-10
Date Deposited:2017-05


This item appears in the following Collection(s)

Item Statistics