Deciding to Remind during Collaborative Problem Solving: Empirical Evidence for Agent Strategies

AAAI 1996

TL;DR

This paper investigates how agents in collaborative problem-solving scenarios decide when to remind their partners of mutually known information. They propose and empirically validate that agents should remind only when it reduces overall collaborative effort, and that an agent can effectively approximate its partner's attentional state by using its own.

What Problem Does This Paper Address?

In collaborative tasks, agents often possess more information than they can actively attend to at any given moment. This selective attention means that even if a piece of information is known to both agents, one agent might not be currently focusing on it. This can lead to inefficiencies if an agent has to re-derive or re-retrieve information that the other agent already knows but isn't attending to. The core problem is how an agent can intelligently decide when to proactively "remind" its partner of such information to improve the team's overall performance, rather than just assuming the partner will recall it. This is particularly relevant in multi-agent systems where communication and processing costs can be significant.

Methods

The authors developed a simulation testbed called "Design-World" to model collaborative problem-solving. In this testbed, two agents negotiate the design of a two-room house, aiming to maximize the utility of the chosen furniture. The key innovation is the modeling of an agent's limited attention and working memory (AWM), which simulates the constraint of only being able to attend to a subset of known information.

They then defined and tested four discourse strategies:

  1. All-Implicit: Never reminds, assumes partner has all relevant information salient.
  2. Explicit-Warrant: Always reminds, assumes partner has no relevant information salient.
  3. ESP (External State Prediction): Assumes agent A has a perfect model of agent B's attentional state.
  4. Solipsistic: Assumes agent A uses its own attentional state to approximate agent B's attentional state.

The core of their approach is to evaluate these strategies based on a "PERFORMANCE" metric, defined as the task's raw score minus "COLLABORATIVE EFFORT." Collaborative effort is broken down into communicative effort (message production/understanding) and retrieval effort (memory access). Their adaptive strategies (ESP and Solipsistic) decide to remind if it reduces collaborative effort, considering the costs of communication vs. retrieval.

Datasets

The paper does not use external datasets. Instead, it relies on simulated dialogues generated within the "Design-World" testbed. The testbed itself is a novel benchmark designed to evaluate agent communication strategies under controlled conditions of resource limitations and task complexity.

Key Insights and Ideas

  • Performance-Driven Reminding: The most fundamental idea is that reminding should be a strategic decision driven by overall team performance. Agents should only remind if the cost of communicating the reminder is less than the cost saved by the partner not having to retrieve or infer the information.
  • The Power of Self-Modeling (Solipsism): Surprisingly, an agent using its own attentional state to approximate its partner's (the Solipsistic strategy) performed very well. This suggests that even with imperfect knowledge of the partner's exact state, a reasonable approximation can lead to significant performance gains.
  • Overhead Matters: The ESP strategy, which assumes perfect knowledge of the partner's state, sometimes performed worse than the Solipsistic strategy. This highlights that the overhead of maintaining a detailed model of another agent can outweigh the benefits, especially if the partner's state is not drastically different from one's own.
  • Adaptive Strategies Outperform Static Ones: Both adaptive strategies (ESP and Solipsistic) generally performed as well as or better than the static strategies (All-Implicit and Explicit-Warrant) across various conditions. This indicates that flexible, context-aware reminding is superior to fixed policies.

Key Results

  • PERFORMANCE Hypothesis Supported: Both adaptive strategies (ESP and Solipsistic) consistently improved performance compared to static strategies, particularly under conditions where retrieval effort was costly.
  • Solipsistic Hypothesis Supported: The Solipsistic strategy performed comparably to the ESP strategy, suggesting that an agent's own attentional state is a viable proxy for its partner's. In some scenarios, Solipsistic even outperformed ESP, especially when the cost of maintaining the ESP model was factored in.
  • Context-Dependent Benefits: The effectiveness of strategies varied with AWM (attention/working memory) range and the dominance of communication vs. retrieval costs. For instance, ESP was beneficial compared to All-Implicit at higher AWM ranges when retrieval effort dominated. Solipsistic was beneficial compared to Explicit-Warrant when communication effort dominated.

Limitations and Future Work

  • Synchronous Communication: The current model assumes synchronous communication. Future work could explore how these strategies perform in asynchronous environments.
  • Simplified Task: The Design-World task is a simplified negotiation scenario. Testing these models in more complex, open-ended problem-solving domains would be valuable.
  • Formal Model Dependence: The results are tied to the specific formal model of collaborative problem-solving and AWM used in the Design-World testbed. Generalizing these findings to other agent architectures and cognitive models is an open question.
  • Human-Computer Interaction: The authors suggest testing these models in human-computer interaction scenarios, such as intelligent tutors, to see how they extend to non-homogeneous agents. They also propose investigating circumstances where the ESP hypothesis might hold more strongly than the Solipsistic one.

Summary updated

BibTeX
@inproceedings{1996deciding,
  title = {{Deciding to Remind during Collaborative Problem Solving: Empirical Evidence for Agent Strategies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure