Expected Value of Communication for Planning in Ad Hoc Teamwork

William Macke, Reuth Mirsky, Peter Stone

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.

Mean marginal cost vs. per-station cost across different planning strategies.

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.

Distribution of queries over time for various algorithms.

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

Abstract

A desirable goal for autonomous agents is to be able to coordinate on the fly with previously unknown teammates. Known as "ad hoc teamwork", enabling such a capability has been receiving increasing attention in the research community. One of the central challenges in ad hoc teamwork is quickly recognizing the current plans of other agents and planning accordingly. In this paper, we focus on the scenario in which teammates can communicate with one another, but only at a cost. Thus, they must carefully balance plan recognition based on observations vs. that based on communication. This paper proposes a new metric for evaluating how similar are two policies that a teammate may be following - the Expected Divergence Point (EDP). We then present a novel planning algorithm for ad hoc teamwork, determining which query to ask and planning accordingly. We demonstrate the effectiveness of this algorithm in a range of increasingly general communication in ad hoc teamwork problems.
BibTeX
@inproceedings{macke2021expected,
  author = {William Macke and Reuth Mirsky and Peter Stone},
  title = {{Expected Value of Communication for Planning in Ad Hoc Teamwork}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17346},
}
Figure