{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97785"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97785","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A game theoretic approach to UAV routing and information collection","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Thakoor, Omkar P"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Garg, Jugal"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T20:33:25Z","date_published":"2017-08-10T20:33:25Z","updated_at":"2026-07-22T22:24:34Z","subjects":["Unmanned aerial vehicle (UAV)","Routing","Game theory","Nash equilibrium","Price of anarchy"],"languages":["en"],"rights":["Copyright 2017 Omkar Thakoor"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97785","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Garg, Jugal"]},{"key":"dc:creator","label":"Author","values":["Thakoor, Omkar P"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T20:33:25Z","2019-08-11T09:15:10Z","2017-04-26","2017-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Unmanned aerial vehicle (UAV)","Routing","Game theory","Nash equilibrium","Price of anarchy"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Omkar Thakoor"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97785"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-05-01","The student, Omkar Thakoor, accepted the attached license on 2017-04-25 at 16:07.","The student, Omkar Thakoor, submitted this Thesis for approval on 2017-04-25 at 16:36.","This Thesis was approved for publication on 2017-04-26 at 09:43.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11060 on 2017-08-10 at 15:07:04","Made available in DSpace on 2017-08-10T20:33:25Z (GMT). No. of bitstreams: 2 THAKOOR-THESIS-2017.pdf: 519172 bytes, checksum: 587623d560fa9ca04ac801dab8fe0715 (MD5) LICENSE.txt: 4210 bytes, checksum: 9b2e37adf05842f3a4ec25ad163b5a0e (MD5) Previous issue date: 2017-04-26","Embargo set by: Colleen Fallaw for item 102838 Lift date: 2019-08-10T21:27:21Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 102838 on 2019-08-11T09:15:10Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["A game theoretic approach to UAV routing and information collection"]}]}],"canonical_facts":{"dc:contributor":["Garg, Jugal"],"dc:creator":["Thakoor, Omkar P"],"dc:date":["2017-08-10T20:33:25Z","2019-08-11T09:15:10Z","2017-04-26","2017-05"],"dc:description":["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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-05-01","The student, Omkar Thakoor, accepted the attached license on 2017-04-25 at 16:07.","The student, Omkar Thakoor, submitted this Thesis for approval on 2017-04-25 at 16:36.","This Thesis was approved for publication on 2017-04-26 at 09:43.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11060 on 2017-08-10 at 15:07:04","Made available in DSpace on 2017-08-10T20:33:25Z (GMT). No. of bitstreams: 2 THAKOOR-THESIS-2017.pdf: 519172 bytes, checksum: 587623d560fa9ca04ac801dab8fe0715 (MD5) LICENSE.txt: 4210 bytes, checksum: 9b2e37adf05842f3a4ec25ad163b5a0e (MD5) Previous issue date: 2017-04-26","Embargo set by: Colleen Fallaw for item 102838 Lift date: 2019-08-10T21:27:21Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 102838 on 2019-08-11T09:15:10Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97785"],"dc:language":["en"],"dc:rights":["Copyright 2017 Omkar Thakoor"],"dc:subject":["Unmanned aerial vehicle (UAV)","Routing","Game theory","Nash equilibrium","Price of anarchy"],"dc:title":["A game theoretic approach to UAV routing and information collection"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:34Z"}