Abstract
In an ad hoc teamwork setting, the team needs to coordinate their activities to perform a task without prior agreement on how to achieve it. The ad hoc agent cannot communicate with its teammates but it can observe their behaviour and plan accordingly. To do so, the existing approaches rely on the teammates' behaviour models. However, the models may not be accurate, which can compromise teamwork. For this reason, we present Ad Hoc Teamwork by Sub-task Inference and Selection (ATSIS) algorithm that uses a sub-task inference without relying on teammates' models. First, the ad hoc agent observes its teammates to infer which sub-tasks they are handling. Based on that, it selects its own sub-task using a partially observable Markov decision process that handles the uncertainty of the sub-task inference. Last, the ad hoc agent uses the Monte Carlo tree search to find the set of actions to perform the sub-task. Our experiments show the benefits of ATSIS for robust teamwork.
Introduction
Ad hoc teamwork presents a significant challenge in multi-agent systems: how can an autonomous agent collaborate effectively with unknown teammates without pre-established communication or strategies? This scenario is critical for real-world applications like disaster response, multi-robot logistics, or collaborative construction.
Traditional state-of-the-art methods, such as PLASTIC or OPAT, typically depend on learning or possessing accurate behavioral models of teammates to predict their next moves. However, in dynamic or time-constrained environments, these models are often unavailable or incorrect. Inaccurate models can lead to catastrophic coordination failures and deadlocks. ATSIS addresses this by shifting the focus from predicting exact actions to inferring high-level sub-task intentions.
Methodology
The ATSIS algorithm decomposes the coordination problem into three hierarchical steps:
- Sub-task Inference: Instead of modeling teammate behavior at the action level, ATSIS identifies which sub-task a teammate is pursuing. It calculates the value added by a teammate's observed actions to specific sub-tasks using Q-values from a single-agent MDP, assuming a temporarily static environment to avoid the need for complex teammate models.
- Sub-task Selection (POMDP): To account for the inherent uncertainty in teammate intent, the agent employs a Partially Observable Markov Decision Process (POMDP). This framework allows the agent to maintain a belief state over unattended sub-tasks and select the most appropriate one based on its own capabilities and the team's needs.
- Action Planning (MCTS/UCT): Once a sub-task is assigned, the agent uses Monte Carlo Tree Search (specifically the UCT variant) to determine immediate actions. A key innovation here is the "sub-task termination" condition, which stops the search once the specific sub-goal is met, drastically reducing computational overhead.
Experimental Setup
The algorithm was evaluated using the Pursuit Domain, a standard benchmark for multi-agent coordination.
In this 10x10 grid world, four "predator" agents must surround a single "prey." The task is naturally divisible into four sub-tasks: occupying the top, bottom, left, and right positions relative to the prey. The ad hoc agent was tested alongside various teammate types, including Greedy (GR), Team-aware (TA), and Probabilistic-destinations (PD) agents.
Key Results
ATSIS demonstrates superior robustness and efficiency compared to model-based baselines.
Robustness to Model Inaccuracy
As shown in Figure 6(b), when baseline methods like PLASTIC and OPAT are provided with incorrect teammate models, their performance collapses. PLASTIC, in particular, suffers from a high frequency of "long episodes" (over 250 steps), indicating frequent deadlocks. In contrast, ATSIS maintains a consistent capture rate of approximately 27 steps, regardless of teammate model accuracy, because it does not rely on those models.
Computational Efficiency
ATSIS significantly outperforms baselines in decision speed. By utilizing sub-task termination in its MCTS planner, it requires only 0.3 seconds per decision step, compared to 1.0 second for PLASTIC. Furthermore, while PLASTIC requires roughly 1,600 steps of observation to learn a teammate model from scratch, ATSIS provides high-quality coordination immediately.
Conclusion and Future Work
ATSIS provides a robust framework for ad hoc teamwork by focusing on intent inference rather than action prediction. While currently dependent on manually defined sub-tasks, future research will explore automated sub-task decomposition through reward shaping. Additionally, the authors aim to scale the approach to larger, more complex environments where traditional joint-state space modeling becomes computationally infeasible.
Summary updated