Abstract
Effective communication in multi-agent teams often assumes a shared joint policy, which is frequently unavailable in complex, real-world environments. This paper introduces the Single Agent in a Team Decision (SATD) problem, where an agent must decide whether to share unanticipated information with teammates whose full plans are unknown. We propose MDP-PRT, a hybrid model that integrates Probabilistic Recipe Trees (PRT) with Markov Decision Processes (MDP). By reasoning about the timing and value of information, MDP-PRT outperforms myopic communication strategies and achieves performance near that of computationally intensive, full-knowledge models like Dec-POMDP.
Introduction
In ideal multi-agent systems, agents operate under a "joint policy"—a master script where every participant's actions are known to all. However, in domains like healthcare, team members often share high-level goals (e.g., "improving patient health") without knowing the specific tactical plans of their colleagues. When an agent observes unanticipated information, such as a new symptom, they face a critical decision: should they interrupt a teammate immediately, wait for a better time, or refrain from sharing if the information is irrelevant?
This paper formalizes this challenge as the SATD problem. The SATD problem is characterized by three key factors: incomplete knowledge of teammate policies, the arrival of unanticipated information, and the critical importance of communication timing.
The MDP-PRT Framework
To address the SATD problem, we propose MDP-PRT, a model that bridges Belief-Desire-Intention (BDI) logic with Decision Theory (DT).
- Probabilistic Recipe Trees (PRT): These represent an agent’s beliefs about a teammate's hierarchical plans. By breaking goals into constituent tasks, the agent can reason about which specific sub-plans might be impacted by new information.
- Markov Decision Process (MDP): The problem is modeled as an MDP where the state space includes the agent's beliefs (the PRT). This allows the agent to look ahead and evaluate the trade-off between immediate communication and waiting to gain more certainty about a teammate's current actions.
Unlike "myopic" algorithms that only evaluate the immediate utility of sharing, the MDP framework allows the agent to reason that delaying communication to observe teammate behavior can refine its belief and potentially avoid the cost of irrelevant communication.
Experimental Evaluation
The model was evaluated using a modified version of the Colored Trails (CT) game, a standard testbed for multi-agent interaction. In this setup, agents navigate a board of colored tiles toward goals. One agent discovers a change in the environment (e.g., a blocked path) and must decide how and when to inform a teammate.
Key Results
The performance of MDP-PRT was compared against a myopic PRT-based "inform" algorithm and a Dec-POMDP model.
Outperforming Myopia
MDP-PRT consistently achieved higher average utility than the myopic PRT algorithm across various communication costs. By considering the timing of communication, MDP-PRT avoids unnecessary "chatter" when costs are high.
Near-Optimal Performance
When compared to the Dec-POMDP—a gold-standard model that assumes all possible observations are known at planning time—MDP-PRT performed remarkably well. Despite having less prior information, MDP-PRT stayed within approximately 15% of the optimal utility, demonstrating its viability for real-world scenarios where future surprises cannot be pre-calculated.
Conclusion
The MDP-PRT framework demonstrates that "helpful" communication is not merely about sharing information immediately, but about strategic patience. By using structured beliefs to guess teammate plans, agents can make sophisticated decisions that balance information value against communication costs. While future work is needed to scale this approach to larger teams and handle noisy observations, MDP-PRT provides a robust foundation for optimizing communication in uncertain, cooperative environments.
Summary updated