Abstract
Ad hoc teamwork involves designing agents that can effectively collaborate with unknown teammates without prior coordination. A central challenge in this field is the observation-communication trade-off: an agent must decide whether to wait and observe a teammate's actions to infer their goals or to proactively query them at a cost. This paper introduces the Expected Divergence Point (EDP), a novel metric that predicts the expected time until a teammate's actions reveal their intended policy. By leveraging EDP, we define the Expected Zone of Querying ($eZ_Q$), a principled framework for determining the optimal timing and content of communication. Experimental results in a complex tool-fetching domain show that our approach significantly reduces marginal costs and maintains robustness across varying communication cost models.
Introduction
In ad hoc teamwork, an "Ego Agent" must assist teammates whose specific goals and strategies are initially unknown. While observing actions allows for goal inference, it consumes time and may lead to suboptimal initial steps. Communication can resolve ambiguity faster but often incurs costs—such as battery usage or cognitive load. Previous research often relied on "worst-case" metrics like Worst Case Distinctiveness (WCD), which can lead to overly cautious or excessively communicative behavior. We propose an "expected-case" approach that balances the cost of communication against the expected benefit of earlier goal resolution.
Methodology
The core of our approach lies in two technical innovations: the Expected Divergence Point and the Expected Zone of Querying.
Expected Divergence Point (EDP)
The EDP quantifies the expected number of steps until a teammate, following one of two possible policies, takes an action that is inconsistent with the other. Unlike worst-case metrics, EDP provides a more realistic estimate of when ambiguity will naturally resolve. We demonstrate that EDP can be computed efficiently using a Bellman-style update, allowing for offline pre-computation of divergence metrics for all policy pairs in a given environment.
Expected Zone of Querying ($eZ_Q$)
Building on EDP, we define the $eZ_Q$ as the temporal window where querying is most advantageous. The decision to query at time $t$ is based on comparing the cost of the query against the expected reduction in future path costs. To optimize the content of the query (i.e., which goals to ask about), we employ a genetic algorithm that seeks to maximize information gain while minimizing the cost associated with the number of items in the query.
Experimental Setup
We evaluated our framework in a generalized Tool Fetching Domain. In this grid-world environment, a "fetcher" (Ego Agent) must deliver the correct tool to a "worker" (teammate) at one of several workstations. To increase realism, we introduced multiple toolboxes, a Boltzmann goal distribution (modeling teammates who choose closer goals), and scalable cost models where query costs increase with the number of stations included in the question.
Results and Discussion
Efficiency and Cost Robustness
Our $eZ_Q$ Query algorithm consistently outperformed baselines, including "Never Query" and simple heuristics. As shown in Figure 1, the $eZ_Q$ approach maintains a significantly lower mean marginal cost even as the per-station communication cost increases. While baseline methods like "BL:Cost+Prob" show performance degradation, $eZ_Q$ adapts by selecting more targeted queries.
Query Timing and Early Intervention
A key insight from our study is the importance of early communication. Analysis of query distributions (Figure 2) reveals that the $eZ_Q$ agent tends to initiate queries in the earliest timesteps of an episode. By resolving goal ambiguity early, the agent avoids committing to incorrect paths, thereby minimizing the total steps taken to complete the task.
Conclusion
By shifting from worst-case to expected-case reasoning through the EDP metric, we provide a more efficient framework for communication in ad hoc teams. Our $eZ_Q$ planning algorithm effectively balances the trade-off between observation and communication costs. Future work will explore extending these concepts to continuous state spaces and scenarios involving proactive communication from teammates.
Summary updated