Medusa: Towards Simulating a Multi-Agent Hide-and-Seek Game

Akshat Tandon, Kamalakar KarlapalemIJCAI 2018 · DOI

TL;DR

This paper introduces Medusa, a novel multi-agent simulator designed to model hide-and-seek scenarios. Medusa provides a flexible platform for simulating complex interactions between hider and seeker agents, enabling the study of emergent behaviors and the development of strategies in environments with dynamic visibility and spatial abstractions.

What Problem Does This Paper Address?

The paper addresses the challenge of simulating and analyzing complex social scenarios that can be abstracted as hide-and-seek games. While existing multi-agent simulators can handle visibility cones, they often lack the specialized tools needed to effectively model the spatial abstractions crucial for hide-and-seek dynamics. These abstractions include strategic points (potential hiding spots) and coverage points (potential seeking locations), which are essential for agents to plan their movements and achieve their objectives. The authors highlight that real-world scenarios like security patrols, intruder capture, and drone surveillance share these hide-and-seek characteristics, necessitating a dedicated simulation platform.

Methods

Medusa is a multi-agent simulator built to address these challenges. Its core features include:

  • Environment and Agent Modeling: It simulates a 2D bounded environment with polygonal obstacles, where agents (hiders and seekers) are point objects capable of moving in sixteen compass directions. Teams of agents can be formed.
  • Spatial Abstractions: Medusa introduces and utilizes "strategic points" (midpoints of obstacle edges) and "coverage points" (locations from which strategic points are visible). It employs algorithms to find optimal sets of coverage points based on visibility graphs and maximal cliques. "Coverage contours" are also introduced to help agents exploit local environments.
  • Visibility Model: Agents have configurable visibility regions, approximated by emitting uniformly spaced rays. The visibility region is dynamic, changing with agent movement. A hider is eliminated if visible to any seeker.
  • Architecture: The platform is modular, with components for defining environments, spatial abstractions, agent behaviors, team structures, and communication. The Experiment module controls simulation parameters, and the Simulator module executes the game, providing visibility percepts back to agents. A Visualization module offers real-time and replay visualization.

Datasets

Not discussed in the paper. The paper focuses on the simulator's capabilities and does not present experiments on specific datasets.

Key Insights and Ideas

  • Hide-and-Seek as a General Abstraction: The paper effectively frames hide-and-seek as a powerful abstraction for a wide range of real-world security and surveillance scenarios, highlighting the universality of the problem.
  • Importance of Spatial Abstractions: The introduction of "strategic points" and "coverage points" as explicit abstractions is key. These are not just geometric locations but represent tactical advantages for agents, simplifying complex environmental information for planning.
  • Visibility as a Dynamic Percept: Modeling visibility not as a static property but as a dynamic region that changes with agent pose and movement is crucial for realistic simulation.
  • Scalability to Thousands of Agents: The platform's ability to scale to a large number of agents is a significant advantage for studying emergent collective behaviors.

Key Results

The paper primarily focuses on the design and capabilities of the Medusa platform. It demonstrates the ability to:

  • Simulate hide-and-seek games with configurable environments, agent numbers, and visibility parameters.
  • Model and utilize strategic and coverage points for agent planning.
  • Provide visualization of agent interactions.

The paper mentions a demonstration where visitors can play against their strategies and provides a YouTube link for videos of the system and simulations. Specific quantitative results on strategy performance or simulation efficiency are not detailed in this excerpt.

Limitations and Future Work

  • Limitations: The paper acknowledges that the environment is a 2D bounded and continuous space, and obstacles are constructed from squares. The visibility model is an approximation. The computational cost of finding optimal coverage points is mentioned, with a discretization approach used to mitigate it.
  • Future Work: The authors suggest that Medusa can be used for studying emergent behaviors and developing agent strategies. The demonstration allows for human-vs-agent play, implying future work in human-agent interaction within these simulated scenarios. The paper also references a related work on agent strategies for hide-and-seek games, suggesting ongoing research in this area.

Summary updated

BibTeX
@inproceedings{tandon2018medusa,
  author = {Akshat Tandon and Kamalakar Karlapalem},
  title = {{Medusa: Towards Simulating a Multi-Agent Hide-and-Seek Game}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/866},
}
Figure