{"id":{"repo_id":"buffalo","oai_identifier":"oai:ubir.buffalo.edu:10477/84051"},"canonical_url":"https://search.dev.ndltd.org/etd/buffalo/oai:ubir.buffalo.edu:10477/84051","repository":{"repo_id":"buffalo","name":"Buffalo","base_url":"https://ubir.buffalo.edu/oai/request"},"display":{"title":"Game Theoretic Studies in Decentralized Routing of UAVs","abstract":"Ph.D.","abstract_html":"Ph.D.","abstract_has_math":false,"creators":["Couche, Michael; 0000-0003-1301-9918"],"institution":"State University of New York at Buffalo","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Karwan, Mark","Industrial and Systems Engineering"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-06-21T15:47:25Z","date_published":"2022-06-21T15:47:25Z","updated_at":"2026-07-27T19:05:30Z","subjects":["operations research"],"languages":["eng"],"rights":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10477/84051","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Karwan, Mark","Industrial and Systems Engineering"]},{"key":"dc:creator","label":"Author","values":["Couche, Michael; 0000-0003-1301-9918"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-06-21T15:47:25Z","2020"]},{"key":"dc:publisher","label":"Institution","values":["State University of New York at Buffalo"]},{"key":"dc:type","label":"Dc Type","values":["Text","Dissertation"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["operations research"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/10477/84051"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ph.D.","Unmanned Aerial Vehicles (UAVs) are widely used in intelligence, surveillance, and reconnaissance missions for defense and civilian applications. Centralized mission planning may not always be possible in the field, and a loss of information may occur due to decentralization. This loss of information is known as the price of anarchy. Game theory provides insight into decentralized routing and can determine the price of anarchy. In this research we present three approaches that populate a spectrum of anarchy. The first is a competitive game routing algorithm that finds the Nash equilibria of a game to route each UAV using a mixed strategy solution technique. The next is a leader-follower game routing algorithm that utilizes backwards induction in order to find the best possible solution for each UAV. The last procedure is a greedy algorithm in which a UAV collects information without regard for any other UAV. Over a design of experiments with different map types, we find that the leader-follower algorithm has clear advantages over the greedy, and is at least as good as the expected outcome of the competitive game algorithm for two player games. We extend the analysis to three player games and use an approximation algorithm for finding an ɛ-Nash equilibrium for the competitive game routing algorithm. The main difference here is that we are only finding one equilibrium compared to the two player game scenarios. There is an overall increase in the price of anarchy for three players, with the competitive game approach drastically increasing, and the leader-follower showing a major advantage. We also explore the effects of incomplete information on the price of anarchy, in situations in which UAVs may fall out of communications with each other for two players. We use a probabilistic random boolean generator to determine a communication condition at each time step of the multi-stage game. When players are out of communication, they employ the greedy algorithm. When in communication, the players employ both the competitive and leader-follower approaches. In some cases, this algorithm will outperform the traditional competitive and leader-follower approaches to find a better maximum gain. This is described as a sort of dithering effect.","**To request an accessible version of the file(s) associated with this item, contact library@buffalo.edu. Please include the item's persistent URL [http://hdl.handle.net/. . .] in your request.**"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Game Theoretic Studies in Decentralized Routing of UAVs"]}]}],"canonical_facts":{"dc:contributor":["Karwan, Mark","Industrial and Systems Engineering"],"dc:creator":["Couche, Michael; 0000-0003-1301-9918"],"dc:date":["2022-06-21T15:47:25Z","2020"],"dc:description":["Ph.D.","Unmanned Aerial Vehicles (UAVs) are widely used in intelligence, surveillance, and reconnaissance missions for defense and civilian applications. Centralized mission planning may not always be possible in the field, and a loss of information may occur due to decentralization. This loss of information is known as the price of anarchy. Game theory provides insight into decentralized routing and can determine the price of anarchy. In this research we present three approaches that populate a spectrum of anarchy. The first is a competitive game routing algorithm that finds the Nash equilibria of a game to route each UAV using a mixed strategy solution technique. The next is a leader-follower game routing algorithm that utilizes backwards induction in order to find the best possible solution for each UAV. The last procedure is a greedy algorithm in which a UAV collects information without regard for any other UAV. Over a design of experiments with different map types, we find that the leader-follower algorithm has clear advantages over the greedy, and is at least as good as the expected outcome of the competitive game algorithm for two player games. We extend the analysis to three player games and use an approximation algorithm for finding an ɛ-Nash equilibrium for the competitive game routing algorithm. The main difference here is that we are only finding one equilibrium compared to the two player game scenarios. There is an overall increase in the price of anarchy for three players, with the competitive game approach drastically increasing, and the leader-follower showing a major advantage. We also explore the effects of incomplete information on the price of anarchy, in situations in which UAVs may fall out of communications with each other for two players. We use a probabilistic random boolean generator to determine a communication condition at each time step of the multi-stage game. When players are out of communication, they employ the greedy algorithm. When in communication, the players employ both the competitive and leader-follower approaches. In some cases, this algorithm will outperform the traditional competitive and leader-follower approaches to find a better maximum gain. This is described as a sort of dithering effect.","**To request an accessible version of the file(s) associated with this item, contact library@buffalo.edu. Please include the item's persistent URL [http://hdl.handle.net/. . .] in your request.**"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/10477/84051"],"dc:language":["eng"],"dc:publisher":["State University of New York at Buffalo"],"dc:rights":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."],"dc:subject":["operations research"],"dc:title":["Game Theoretic Studies in Decentralized Routing of UAVs"],"dc:type":["Text","Dissertation"]},"updated_at":"2026-07-27T19:05:30Z"}