A Penny for Your Thoughts: The Value of Communication in Ad Hoc Teamwork

Reuth Mirsky, William Macke, Andy Wang, Harel Yedidsion, Peter StoneIJCAI 2020 · DOI

Introduction

Ad hoc teamwork involves autonomous agents collaborating with unfamiliar partners without prior coordination. Traditionally, these agents are assumed to be "mute," relying solely on observation to infer intent. However, real-world scenarios often allow for basic communication protocols. The challenge lies in the fact that communication is costly—imposing cognitive or temporal loads. This paper introduces the SOMALI CAT (Sequential One-shot MultiAgent Limited Inquiry Communication in Ad Hoc Teamwork) framework to determine exactly when and what to communicate to maximize team efficiency.

The Tool Fetching Domain

To evaluate communication strategies, the authors developed the Tool Fetching Domain. In this environment, a "worker" agent moves toward one of several workstations. A "fetcher" (the ad hoc agent) must identify the worker's destination and deliver the corresponding tool from a central toolbox.

The Tool Fetching Domain: A fetcher agent must infer the worker's goal station to provide the correct tool efficiently.

The goal is to minimize the total time taken. If the fetcher waits too long to observe the worker, it loses time; if it queries too early, it might waste a limited communication resource on a goal that would have soon become obvious.

Strategic Communication: The Zones of Reasoning

The core contribution of this work is a heuristic algorithm that identifies the Critical Querying Point (CQP). This is achieved by dividing the task timeline into three functional "Zones of Reasoning":

  1. Zone of Information ($Z_I$): The period where a query can reveal the goal before it becomes obvious through observation.
  2. Zone of Plan Branching ($Z_B$): The period after which the agent must commit to a path to remain optimal.
  3. Zone of Querying ($Z_Q$): The overlap between $Z_I$ and $Z_B$. This is the "sweet spot" where information gained can still influence an optimal course of action.
Zones of Reasoning and the Critical Querying Point (CQP) across different potential goal stations.

The CQP is defined as the earliest timestep within $Z_Q$. As shown in the figure, different stations have different zone configurations. For instance, if $Z_I$ and $Z_B$ do not overlap (as seen in the Station 3 timeline), no useful query exists for that specific goal at that time.

Results and Key Insights

The $Z_Q$-based approach was tested against baselines like "Never Query" and "Query at Start." The results demonstrated that querying at the CQP is highly efficient, requiring only 3.65 additional steps beyond a perfect-information scenario, compared to 7.25 steps for the next best baseline.

A key insight is the Value of Silence. By waiting until the CQP, the agent allows the teammate's initial movements to naturally eliminate some possibilities. This makes the eventual query far more targeted, often disambiguating entire sets of goals rather than single targets. Communication is treated as a strategic resource with fluctuating potential value, rather than a constant stream.

Conclusion

The SOMALI CAT framework provides a robust method for timing communication in ad hoc teams. While currently limited to optimal teammates and deterministic environments, it lays the groundwork for more complex, real-world human-robot interaction where every "thought" or query has a price. Future research will explore stochastic environments and sub-optimal teammate behavior.

Summary updated

BibTeX
@inproceedings{mirsky2020penny,
  author = {Reuth Mirsky and William Macke and Andy Wang and Harel Yedidsion and Peter Stone},
  title = {{A Penny for Your Thoughts: The Value of Communication in Ad Hoc Teamwork}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/36},
}
Figure