A Game Theoretic Approach to Multi-agent Systems in Highly Dynamic, Information-sparse, Role Assignment Scenarios

Open Access
Wray, Kyle Hollins
Graduate Program:
Computer Science and Engineering
Master of Science
Document Type:
Master Thesis
Date of Defense:
November 01, 2012
Committee Members:
  • Vijaykrishnan Narayanan, Thesis Advisor
  • Benjamin Berry Thompson, Thesis Advisor
  • Multiagent Systems
  • Game Theory
  • Fictitious Play
  • Anti-Coordination Games
  • Predator Prey
  • Uncertainty
  • Robotics
  • Cooperation
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.