A game theoretic approach to UAV routing and information collection

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2017

Author dc:creator

• Thakoor, Omkar P

Contributors dc:contributor

• Garg, Jugal

• Unmanned aerial vehicle (UAV)
• Routing
• Game theory
• Nash equilibrium
• Price of anarchy

Statement dc:rights

• Copyright 2017 Omkar Thakoor

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/97785

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/97785