Making Friends in the Dark: Ad Hoc Teamwork Under Partial Observability

João G. Ribeiro, Cassandro Martinho, Alberto Sardinha, Francisco S. Melo

TL;DR

This paper introduces a new challenge for AI agents: ad hoc teamwork where the agent can't see the environment or its teammates' actions. They propose ATPO, a novel Bayesian approach that learns to cooperate by inferring the task and teammate behavior from limited observations, demonstrating effectiveness across various complex scenarios.

What Problem Does This Paper Address?

Imagine an AI agent dropped into a complex, real-world situation with unfamiliar teammates. It needs to help them achieve a common goal, but it can't see the full picture – the environment's state is hidden, and its teammates' actions are a mystery. This is the "ad hoc teamwork under partial observability" problem. Traditional ad hoc teamwork research often assumes agents can see the environment or at least their teammates' actions, making this scenario much harder. The core challenge is how an agent can effectively learn to cooperate and contribute when it has such limited information, especially without any prior training or reward signals to guide it.

Methods

The authors propose ATPO (Ad hoc Teamwork for Partially Observable environments), a model-based approach. ATPO operates under three key assumptions:

  1. Partial Observability: The agent never sees the full state of the environment.
  2. Hidden Teammate Actions: The agent cannot observe what its teammates are doing.
  3. No Prior Reward Signal: The agent cannot learn the task from scratch using rewards.

ATPO tackles this by maintaining a library of possible Partially Observable Markov Decision Processes (POMDPs), each representing a potential task and teammate behavior combination. It uses a Bayesian inference framework to maintain a belief distribution over these possible models. As the agent interacts with the environment and receives partial observations, it updates these beliefs. The agent then uses these updated beliefs to select actions that are optimal across all possible models, effectively inferring the most likely task and teammate strategy on the fly.

Datasets

The paper evaluates ATPO on 70 POMDPs across 11 distinct domains. These domains are designed to represent various multi-agent scenarios with different complexities in terms of state spaces, transition probabilities (teammate policies), and reward functions (tasks). Some notable domains include:

  • Gridworld: A standard navigation task.
  • Pursuit: Agents must capture a moving prey.
  • Abandoned Power Plant: A scenario with exploration and cleanup tasks.
  • Overcooked: A cooperative cooking game.

The paper does not introduce new benchmark datasets but rather uses existing multi-agent problem formulations adapted to the POMDP setting.

Key Insights and Ideas

  • Learning to Cooperate with "Darkness": The most significant insight is that effective ad hoc teamwork is possible even with severe information limitations (no state visibility, no teammate action observation). ATPO demonstrates that inferring the task and teammate behavior from partial observations is a viable strategy.
  • Bayesian Inference as a "Social Cue": ATPO's Bayesian approach acts as a mechanism for inferring social cues (teammate intentions and task goals) from indirect evidence (partial observations). This allows it to adapt its behavior without explicit communication.
  • Robustness to Uncertainty: The approach is shown to be robust to scaling in terms of both the number of possible tasks/teammates and the complexity of the environment (state space size). This suggests its potential for real-world applications where uncertainty is inherent.
  • Task Identification is Key: The results highlight that ATPO's ability to identify the correct task and teammate model significantly contributes to its performance, outperforming a random model selection baseline.

Key Results

  • Effective Teamwork: ATPO consistently achieved high performance across all 11 domains, reaching above 83.92% of the optimal performance (defined by a fully informed agent) in relative terms.
  • Domain-Specific Performance: ATPO performed best in the "abandoned power plant" and "MIT" domains (around 99.5% relative performance) and had its lowest relative performance in the "overcooked" domain (83.92%).
  • Scalability: ATPO demonstrated robustness in scaling to environments with up to 4831 states and to libraries of up to 32 possible POMDP models, with performance remaining above 70% even with larger libraries.
  • Belief Convergence: The average belief entropy analysis shows that ATPO successfully converges on the correct model, typically identifying it within 5-10 timesteps and reaching high certainty (around 90%) by 20 timesteps.

Limitations and Future Work

  • Limitations:
    • The current approach relies on pre-defined POMDP models. The performance can degrade if the true environment is not well-represented by any model in the library.
  • The computational cost of solving POMDPs can be significant, especially for large state spaces.
  • Future Work:
    • Extend ATPO to handle continuous or arbitrarily large state spaces, likely requiring function approximation techniques (e.g., neural networks).
  • Integrate model-based planning approaches like MuZero for more sophisticated decision-making.
  • Explore scenarios with dynamic teams where agents can join or leave.

Summary updated

Abstract

This paper introduces a formal definition of the setting of ad hoc teamwork under partial observability and proposes a first-principled model-based approach which relies only on prior knowledge and partial observations of the environment in order to perform ad hoc teamwork. We make three distinct assumptions that set it apart previous works, namely: i) the state of the environment is always partially observable, ii) the actions of the teammates are always unavailable to the ad hoc agent and iii) the ad hoc agent has no access to a reward signal which could be used to learn the task from scratch. Our results in 70 POMDPs from 11 domains show that our approach is not only effective in assisting unknown teammates in solving unknown tasks but is also robust in scaling to more challenging problems.
BibTeX
@inproceedings{ribeiro2023making,
  author = {João G. Ribeiro and Cassandro Martinho and Alberto Sardinha and Francisco S. Melo},
  title = {{Making Friends in the Dark: Ad Hoc Teamwork Under Partial Observability}},
  booktitle = {ECAI},
  year = {2023},
  doi = {10.3233/faia230486},
}
Figure