A Game Theoretic Approach to Multi-agent Systems in Highly Dynamic, Information-sparse, Role Assignment Scenarios
Open Access
- Author:
- Wray, Kyle Hollins
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Master of Science
- Document Type:
- Master Thesis
- Date of Defense:
- November 01, 2012
- Committee Members:
- Vijaykrishnan Narayanan, Thesis Advisor/Co-Advisor
Benjamin Berry Thompson, Thesis Advisor/Co-Advisor - Keywords:
- Multiagent Systems
Game Theory
Fictitious Play
Anti-Coordination Games
Predator Prey
Uncertainty
Robotics
Cooperation - Abstract:
- The wide array of problems found in the field of Multi-Agent Systems (MAS) require rapid coordination toward a desired system state amidst the often limited and inaccurate information observed by the agents within. This thesis investigates the conditions surrounding this kind of emergent coordination. We focus primarily on a problem entitled Defender and provide a solution that leverages game theory in its agents' construction. Defender is a multi-predator multi-prey problem in which the predators seek to capture as many prey as possible before any of the prey reach their haven. The problem itself is a continuous noisy version of scenarios found throughout the MAS literature, particularly in the RoboCup, an annual robotic soccer competition. As such, it defines two sides as goal regions with its agents restricted to observational noise and a limited field of view. It specifically examines dynamically changing versions of learning algorithms like fictitious play, rational learning, and regret matching, in addition to baseline algorithms following minimax regret and greedy strategies. These algorithms operate in an anti-coordination game, which only rewards agents that select different actions from one another. Furthermore, this thesis presents optimizations to these algorithms and tests their robustness in ad hoc team scenarios. Results show that fictitious play outperforms all other algorithms and tends toward strong cooperative behavior. In order to improve the algorithms in these kinds of problems, we also developed an adaptive communication architecture. The Distributed Communication Architecture (DCA) algorithm addresses the common issue found in real-world systems, specifically the message passing structure between agents. It is able to dynamically assign time slots to agents in a completely distributed manner. We apply this algorithm to Defender and show that while communication is not required to achieve emergent cooperation, it can improve the quality of agent's observations and subsequent decisions. Overall, this thesis investigates these primary topics to address the problem of constructing a team of agents seeking to cooperatively behave in a highly dynamic environment.