TY - JOUR
T1 - Multiagent UAV Routing
T2 - A Game Theory Analysis with Tight Price of Anarchy Bounds
AU - Thakoor, Omkar
AU - Garg, Jugal
AU - Nagi, Rakesh
N1 - The work of J. Garg was supported by NSF CRII under Award 1755619. The work of R. Nagi was supported in part by ONR through the Program Management of Dr. D. Wagner under Award N000014-16-1-2245.
Manuscript received April 3, 2018; revised August 21, 2018, October 19, 2018, and January 1, 2019; accepted February 11, 2019. Date of publication March 20, 2019; date of current version January 9, 2020. This paper was recommended for publication by Associate Editor D. V. Dimarogonas and Editor S. Reveliotis upon evaluation of the reviewers\u2019 comments. The work of J. Garg was supported by NSF CRII under Award 1755619. The work of R. Nagi was supported in part by ONR through the Program Management of Dr. D. Wagner under Award N000014-16-1-2245. (Corresponding author: Jugal Garg.) O. Thakoor is with the Department of Computer Science, University of Southern California, Los Angeles, CA 90089 USA (e-mail: othakoor@ usc.edu).
PY - 2020/1
Y1 - 2020/1
N2 - We study the multiagent unmanned aerial vehicle (UAV) routing problem where a set of UAVs needs to collect information via surveillance of an area of operation. Each UAV is autonomous and does not rely on a reliable communication medium to coordinate with other UAVs. We formulate the problem as a game where UAVs are players and their strategies are the different routes they can take. Our model also incorporates the useful concept of information fusion. This results in a new variant of weighted congestion-type games. We show that the price of anarchy (PoA) of the game is at most 2, irrespective of the number of UAVs and their sensor capabilities. This also validates the empirical results of earlier works. Furthermore, we identify classes of games for the existence of a pure Nash equilibrium. To the best of our knowledge, these are the first such theoretical results in the related literature. Finally, we conduct experimental studies using randomly generated instances with several multiagent UAV routing policies. Our insights are that PoA increases with the congestion level when the same number of UAVs search a smaller area or more UAVs search the same area, and on an average, our proposed policies are less than 10% worse than the centralized optimal for the problem scenarios attempted. Note to Practitioners - UAVs are becoming increasingly popular for information collection tasks in defense and civilian applications alike. When the collection area is large, it is not unusual that a fleet of UAVs is deployed. Routing of a fleet can be performed in a centralized or decentralized manner. Decentralized routing might be the only possibility when centralized situational awareness is not possible due to bandwidth limitations and centralized optimal routes for each UAV in the fleet are too complex to compute. Autonomous solutions have several other advantages, let alone simplicity. For managers of UAV systems, our work provides the first theoretical characterization of how bad could decentralized routing be. Under various scenarios of information fusion, specifically weak and strong, and the attribution of information collected to each UAV of a team, we prove that the fleet will collect at least 50% of the best-centralized solution. Empirically, we show that, in fact, the performance of the fleet is much better and generally not worse than 10% of the best-centralized solution. Hopefully, our routing strategies provide valuable guidance to the practicing engineer or manager of a UAV fleet.
AB - We study the multiagent unmanned aerial vehicle (UAV) routing problem where a set of UAVs needs to collect information via surveillance of an area of operation. Each UAV is autonomous and does not rely on a reliable communication medium to coordinate with other UAVs. We formulate the problem as a game where UAVs are players and their strategies are the different routes they can take. Our model also incorporates the useful concept of information fusion. This results in a new variant of weighted congestion-type games. We show that the price of anarchy (PoA) of the game is at most 2, irrespective of the number of UAVs and their sensor capabilities. This also validates the empirical results of earlier works. Furthermore, we identify classes of games for the existence of a pure Nash equilibrium. To the best of our knowledge, these are the first such theoretical results in the related literature. Finally, we conduct experimental studies using randomly generated instances with several multiagent UAV routing policies. Our insights are that PoA increases with the congestion level when the same number of UAVs search a smaller area or more UAVs search the same area, and on an average, our proposed policies are less than 10% worse than the centralized optimal for the problem scenarios attempted. Note to Practitioners - UAVs are becoming increasingly popular for information collection tasks in defense and civilian applications alike. When the collection area is large, it is not unusual that a fleet of UAVs is deployed. Routing of a fleet can be performed in a centralized or decentralized manner. Decentralized routing might be the only possibility when centralized situational awareness is not possible due to bandwidth limitations and centralized optimal routes for each UAV in the fleet are too complex to compute. Autonomous solutions have several other advantages, let alone simplicity. For managers of UAV systems, our work provides the first theoretical characterization of how bad could decentralized routing be. Under various scenarios of information fusion, specifically weak and strong, and the attribution of information collected to each UAV of a team, we prove that the fleet will collect at least 50% of the best-centralized solution. Empirically, we show that, in fact, the performance of the fleet is much better and generally not worse than 10% of the best-centralized solution. Hopefully, our routing strategies provide valuable guidance to the practicing engineer or manager of a UAV fleet.
KW - Game theory
KW - multiagent systems
KW - price of anarchy (PoA)
KW - surveillance and reconnaissance
KW - unmanned aerial vehicles (UAVs)
UR - http://www.scopus.com/inward/record.url?scp=85068003227&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068003227&partnerID=8YFLogxK
U2 - 10.1109/TASE.2019.2902360
DO - 10.1109/TASE.2019.2902360
M3 - Article
AN - SCOPUS:85068003227
SN - 1545-5955
VL - 17
SP - 100
EP - 116
JO - IEEE Transactions on Automation Science and Engineering
JF - IEEE Transactions on Automation Science and Engineering
IS - 1
M1 - 8671711
ER -