Multiagent UAV Routing: A Game Theory Analysis With Tight Price of Anarchy Bounds
Multiagent UAV Routing: A Game Theory Analysis With Tight Price of Anarchy Bounds
复制标题
DOI：
10.1109/tase.2019.2902360
复制
发表时间：
2020-01
影响因子：
5.6
通讯作者：
Omkar Thakoor;J. Garg;R. Nagi
中科院分区：
文献类型：
--
作者：
Omkar Thakoor;J. Garg;R. Nagi
我们研究了多智能体无人机（UAV）的路由问题，一组无人机需要收集信息，通过监视一个区域的操作。每个无人机都是自主的，不依赖可靠的通信媒介与其他无人机协调。我们制定的问题作为一个游戏，无人机的球员和他们的策略是不同的路线，他们可以采取。我们的模型还采用了有用的概念，信息融合。这导致了一个新的变种的加权竞争型游戏。我们表明，无政府状态（PoA）的游戏的价格是最多2，无论无人机的数量和传感器的能力。这也验证了早期工作的经验结果。此外，我们确定类的游戏存在一个纯纳什均衡。据我们所知，这是第一个这样的理论结果在相关文献中。最后，我们进行了实验研究，使用随机生成的实例与几个多智能体无人机路由策略。我们的见解是，当相同数量的无人机搜索较小的区域或更多的无人机搜索相同的区域时，PoA随着拥塞水平的增加而增加，并且平均而言，我们提出的策略比尝试的问题场景的集中式最优策略差不到10%。从业人员注意-无人机在国防和民用应用中的信息收集任务越来越受欢迎。当收集区域很大时，部署一个无人机机群是很平常的。车队的路由可以以集中或分散的方式执行。当由于带宽限制而无法实现集中式态势感知时，分散式路由可能是唯一的可能性，并且机群中每个UAV的集中式最佳路由太复杂而无法计算。自治解决方案还有其他几个优点，更不用说简单了。对于无人机系统的管理者来说，我们的工作提供了第一个理论表征，说明分散式路由有多糟糕。在各种信息融合的情况下，特别是弱和强，以及收集到的信息归属于一个团队的每个无人机，我们证明了舰队将收集至少50%的最佳集中式解决方案。从经验上讲，我们表明，事实上，车队的性能要好得多，一般不会比最佳集中式解决方案的10%差。希望我们的路由策略提供有价值的指导实践工程师或无人机机队的管理者。
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.