Novel Metrics and Randomized Algorithms for Robust Networked Multiagent Coordination
Abstract
Many emerging Air Force and Space Force technologies rely on complex networks of interacting agents. Unmanned vehicle swarms performing autonomous surveillance, distributed routing of military aircraft, collision avoidance in satellite mega-constellations (and many other applications) all share this feature in common- decisions made by one agent impact the optimal decisions of other agents; that is, they are network games. The resulting network games are dynamic, heterogeneous, and can be highly fragile- an agent which loses the ability to observe the actions of another agent may make ostensibly-rational decisions which inadvertently result in failures which cascade throughout the entire network. This project focuses on analytics and algorithms for identifying and mitigating network fragilities which result from individual agents inability to properly process the decisions of other agents. Whether this denial of capability is caused by adverse operational conditions or by a strategic adversary, our techniques will provide fundamental theory for designing and deploying robust networked interactive systems. A key tenet of this project is that recent results have shown that judicious use of randomized distributed algorithms can mitigate the harm of unplanned communication failures among agents; in this project we will study how to optimize these algorithms to ensure robust coordination among agents. Research Thrust 1- Analytics and Algorithms for Communication-Denied Sub-modular Maximization. This thrust will leverage and exploit the recent finding that in communication-denied problems, worst-case emergent behavior is highly fragile, suggesting that performance can be recovered by the use of randomized algorithms. Here, we focus on two main activities- (1) we develop graph-theoretic analytics to characterize how connectivity mong the agents influences emergent performance; (2) we design algorithms to robustly mitigate the harm of unplanned communication-observation breakdown among the agents. Research Thrust 2- Coordination Algorithms for Communication-Denied General Network Games. Once the central tenets of robust algorithm design are understood for denied games with submodular objective functions, we will extend these conclusions to much more general network game formulations. Here, the key goal is to understand how far the conclusions of Thrust 1 can be taken beyond the submodular setting. The results generated in this project will inform real-world algorithm development for distributed optimization of networked multiagent systems. In addition, they will provide significant basic contributions to the field of game theory.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 29, 2024
- Source ID
- FA95502310171
Entities
People
- Philip N. Brown
Organizations
- Air Force Office of Scientific Research
- Regents of the University of Colorado
- United States Air Force