The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models

• The COM-MTDP addresses the lack of quantitative optimality evaluation and complexity characterization in existing teamwork research.Existing theories often ignore real-world uncertainty and costs, making their coordination prescriptions potentially suboptimal.Source: §1 · p. 2
• The COM-MTDP extends economic team theory with explicit models of communication and system dynamics, and generalizes decentralized POMDPs.Source: §1 · p. 2
• Constructing optimal teams without communication is NEXP-complete, while allowing free communication reduces the problem to PSPACE-complete.The paper analyzes complexity across domains classified by observability and communication cost.Source: §1 · p. 3
• Encoding two joint-intentions approaches lets the authors derive conditions for optimal team behavior and characterize the approaches’ decision-problem complexity.The approaches are based on GRA* and the joint responsibility model, and on STEAM.Source: §1 · p. 3
• The authors derive a novel coordination algorithm that outperforms existing strategies in optimality, but not efficiency.The analysis characterizes the complexity-optimality tradeoff among different means of team coordination.Source: §1 · p. 3
• Reusable, domain-independent algorithms evaluate coordination-policy optimality in a COM-MTDP model of a specific domain.The authors apply them to an example domain and characterize each strategy’s optimality as a function of domain properties.Source: §1 · p. 3
• The COM-MTDP evaluation finds that Jennings’ approach benefits performance in many example-domain configurations, while competing methods perform better in some.Source: §1 · p. 3
• Re-evaluating a STEAM-based implementation shows its observed suboptimality reflects a general propensity for extraneous communication across a significant range of domain types.Source: §1 · p. 3
• After reviewing related multiagent models, Section 3 characterizes the complexity of designing optimal agent teams.Source: §1 · p. 3
• Section 4 analyzes the optimality of existing coordination algorithms and derives a novel coordination algorithm.Source: §1 · p. 4
• Section 5 presents empirical results from applying the COM-MTDP algorithms to an example domain.Source: §1 · p. 4
• Section 6 summarizes the results, and Section 7 identifies promising future directions.Source: §1 · p. 4

2. The COM-MTDP Mo del

• The COM-MTDP is presented as a model for representing important aspects of multiagent teamwork.The section introduces the underlying team decision problem and then defines the complete model with explicit communication.Source: §2 · p. 4
• An illustration shows how the COM-MTDP represents the execution of a team of agents.Source: §2 · p. 4
• The section describes related multiagent coordination models and how the COM-MTDP generalizes them.Source: §2 · p. 4

2.1 Multiagen t T eam De ision Problems

• MTDPs frame selfless agents’ joint task as evaluating behavior policies, extending Ho’s team decision model to dynamic multiagent domains and agent beliefs.The model is assumed to be common knowledge among team members.Source: §2.1 · p. 4

2.1.1 W orld St a tes: S

• The model extends one-shot static problems to time-series random variables, represents noisy observations stochastically, and distinguishes collective from individual observability.The transition model assumes Markov world dynamics.Source: §2.1.1 · pp. 4–5

2.1.4 Poli y (Stra tegy) Sp a e

• Domain-level policies map an agent’s belief state, formed from observations over time, to an action, allowing strategies to represent richer mental states.The framework defines a combined belief state across agents.Source: §2.1.4 · pp. 5–6

2.1.5 Rew ard Fun tion: R

• COM-MTDP separates domain actions that change the world from communication actions that update teammates’ beliefs, while team members share a common reward.The model initially assumes messages arrive instantaneously and correctly, with no communication lag or noise.Source: §2.1.5 · p. 6
• Agents update beliefs after observations and again after messages, distinguishing the beliefs used to choose communication from those used for domain actions.The model assumes perfect recall of observations and received messages; under this assumption its state estimators take constant time, while complexity results allow only polynomial-time estimators.Source: §2.1.5 · pp. 6–7

2.2.2 Extended Rew ard Fun tion: R

• When communication and domain-action costs are independent, team reward decomposes into communication-level and domain-level components whose values sum.Communication is assigned no inherent benefit and may have a cost, but it can indirectly improve future actions by changing agents’ beliefs.Source: §2.2.2 · pp. 7–8
• The framework distinguishes general communication, free communication, and no communication, making no assumptions about general communication and noting communication may be prohibitively expensive.Source: §2.2.2 · p. 8

2.3 Mo del Illustration

• The setup begins with an initial world state and belief states, then draws each agent’s initial observation from the observation distribution.Agents subsequently update their beliefs before selecting messages.Source: §2.3 · p. 8
• Each agent interprets other agents’ communications to update its belief state, then selects a domain-level action according to its policy.The team receives a combined action and shared joint reward before the world transitions to a new state.Source: §2.3 · p. 8
• Agents repeatedly choose communication and domain-level actions, observe their effects, and update beliefs as the world evolves.The evolving state is treated as a Markov chain with separate stages for domain-level and communication-level actions.Source: §2.3 · pp. 8–9
• Over horizon T, the value of a policy is the expected reward received when executing that policy.Rewards accrue to the agents as a series during the process.Source: §2.3 · p. 9

2.4 Related W ork

• The COM-MTDP subsumes many existing multiagent models and enables novel analyses of real-world teamwork, including communication decisions.The section uses the framework to analyze optimality of communication decisions.Source: §2.4 · p. 9

2.4.1 De entralized POMDPs

• A DEC-POMDP parallels the COM-MTDP’s observability and world dynamics, models collectively partially observable domains, and has no communication.It is a COM-MTDP instance with no possible-message set.Source: §2.4.1 · p. 9

2.4.2 P ar tiall y Obser v able Identi al P a yoff Sto hasti Games

• The partially observable identical-payoff stochastic game uses a single shared payoff function, matching the team’s global reward, and resembles a DEC-POMDP.Its observation function can represent collectively partially observable domains, and it has no communication.Source: §2.4.2 · p. 9

2.4.3 Mul tia gent MDPs

• An MMDP extends a completely observable MDP to multiple agents, assuming individual observability and no communication.Source: §2.4.3 · p. 9

2.4.4 Xuan-Lesser Framew ork

• The Xuan-Lesser framework supports general communication but only a subset of collectively observable environments, excluding potentially interdependent local observations of a common state.Source: §2.4.4 · p. 10

3. COM-MTDP Complexit y Analysis

• NEXP-complete: with more than one agent, the finite-horizon COM-MTDP decision problem under general communication and collective partial observability asks whether policies can attain reward at least K.Source: §3 · pp. 10, 12
• The proof establishes hardness by reducing a DEC-POMDP to a COM-MTDP without communication while preserving the model’s other features and expected utility.The construction shows the COM-MTDP decision problem is at least as hard as the DEC-POMDP problem.Source: §3 · pp. 10–11
• With free communication, the decision problem can be solved by constructing an MDP over combined belief states and applying dynamic programming.The method determines whether the policy’s expected reward reaches K.Source: §3 · p. 11
• Under free communication, complete communication is a dominant policy, so teams need consider that policy when seeking optimal coordination.The dominance result supports the subsequent complexity analysis under free communication.Source: §3 · pp. 11–12
• PSPACE-complete: with free communication and collective partial observability, deciding whether a finite-horizon team policy reaches reward at least K has this complexity.Source: §3 · p. 12

a COM-MTDP , hS

• PSPACE-complete: under free communication and collective partial observability, deciding whether policies attain reward at least K over a finite horizon has this complexity.Source: a COM-MTDP , hS · p. 14
• P-complete: with collective observability, the decision problem has this complexity; the proof reduces to and from the MDP decision problem.Source: a COM-MTDP , hS · p. 14
• P-complete: with individual observability, the decision problem has this complexity, regardless of the communication policy.Source: a COM-MTDP , hS · p. 14
• NP-complete: with non-observability, the decision problem has this complexity, regardless of the communication policy, because equally uninformed agents cannot benefit from communication.Source: a COM-MTDP , hS · p. 14
• The greatest design challenges arise with collective observability or collective partial observability when communication has nonzero cost.Without communication, teamwork in collectively observable or collectively partially observable domains is highly intractable; free communication brings complexity on par with single-agent planning.Source: a COM-MTDP , hS · p. 14
• Reducing observability can lower complexity while changing expected reward: making all sensors unavailable reduces complexity from NEXP to NP, with an expected reward drop.Even polynomial complexity in the number of world states may remain impractically high.Source: a COM-MTDP , hS · p. 15

4. Ev aluating T eam Co ordination

• The methodology translates a teamwork approach into a policy mapping agent beliefs to communication decisions, then evaluates expected team reward in a specified COM-MTDP domain.The instantiated model represents the domain’s states, transition probabilities, and reward function.Source: §4 · p. 15

4.1 Join t In ten tions in a COM-MTDP

• Joint intentions offers prescriptions grounded in mutual belief but makes no optimality claim; under individual observability, goal achievement yields mutual belief without extra communication.The framework can identify domain properties under which mutual belief is optimal and quantify performance otherwise.Source: §4.1 · p. 16

4.2 Lo ally Optimal P oli y

• The COM-MTDP framework identifies domain properties under which attaining mutual belief generates optimal behavior, and uses the model to derive an analytical characterization of optimal communication.Source: §4.1 · p. 16, §4.2 · p. 17

4.1 Join t In ten tions in a COM-MTDP

• Jennings’ instantiation sends goal achievement when an agent believes the goal holds, while STEAM selects communication by weighing expected miscoordination against communication cost (Jennings, 1995; Tambe, 1997).The paper encodes these two joint-intention instantiations as COM-MTDP communication policies for evaluation.Source: §4.1 · pp. 16–17

4.2 Locally Optimal Policy

• An agent’s local decision compares expected reward with and without sending the special message; sending is locally optimal when the difference is positive.The value measures the expected-reward difference attributable to that agent’s send-or-not-send choice.Source: §4.2 · p. 18
• The exact criterion is not directly implementable and conceals computational complexity, so the authors derive an operational expression using the COM-MTDP model.The authors identify exposing the computation’s complexity as a key aim of their analysis.Source: §4.2 · p. 18
• Theorem 7 informally favors sending the goal-achievement message when post-achievement execution cost outweighs communication cost, assuming that, upon achieving G, no communication other than that message is possible.Source: §4.2 · pp. 19–20
• With free communication, the criterion’s inequality is always true; with individual observability, it is false and agents prefer not to send, except under free communication.When the goal is achieved, individual observability means all agents know it, leaving no difference on the inequality’s left-hand side.Source: §4.2 · p. 21
• When observations are available and communication is not free, local optimality requires evaluating Inequality 16 at full complexity; although unacceptable for most real-world problems, this still yields exponential savings over searching the entire policy space.Source: §4.2 · p. 21
• Theorem 7 can assess whether a policy is locally optimal: if its inequality is ever false, the policy is not even locally optimal.The passages also describe using the criterion to evaluate policies at relevant times and belief states.Source: §4.2 · p. 21
• Inequality 16 computes expected miscoordination cost using distributions over possible states and histories, while STEAM’s single parameter approximates communication cost.The criterion considers histories consistent with current beliefs and looks across possible future state sequences; STEAM’s parameter can vary by joint plan or goal.Source: §4.2 · pp. 21–22
• The criterion justifies STEAM’s overall structure, but its online computational cost may make STEAM’s approximation worthwhile when domain-specific evaluation finds acceptable error.The paper proposes empirical evaluation to quantify the error-efficiency tradeoff for a specific domain.Source: §4.2 · p. 22

5. Empiri al P oli y Ev aluation

• COM-MTDP supports constructing optimal communication policies for specific domains or evaluating candidate approximate policies when optimal computation is prohibitive.The section uses the helicopter testbed to demonstrate a domain-independent methodology for modeling problems and evaluating candidate communication policies.Source: §5 · p. 22

5.1 Exp erimen tal Setup

• The helicopter scenario tests whether an Escort should message Transport after destroying radar, weighing the communication cost against Transport’s chance of observing the destruction.A message lets Transport know it is safe to fly at normal altitude sooner; without a message or observation, it may fly slowly and earn a lower team reward.Source: §5.1 · p. 23
• The evaluation varies observability and communication cost from 0 to 1 in 0.1 increments, comparing Jennings, silent, two STEAM settings, and locally and globally optimal policies.The high STEAM setting is strictly dominated by the low and medium settings in this domain.Source: §5.1 · p. 24

5.2 Exp erimen tal Results

• Figures 5 and 6 compare expected utility lost under Jennings, silent, and two STEAM policies against the locally optimal communication policy; larger losses indicate worse performance.The supplied results passage describes the comparison but does not include its numerical values or the direction of the policy results.Source: Figure 5 · p. 27, Figure 6 · p. 27, §5.2 · p. 27

5.2 Experimental Results

• Jennings generally outperformed the silent policy across domain configurations, but the silent policy was superior when communication cost and observability were high; both policies were significantly suboptimal in some domains.The experiments characterize the conditions under which each policy performs better.Source: §5.2 · p. 27
• STEAM interpolates between Jennings and silent policies based on domain properties, but under low communication cost it switches at two thresholds and is most suboptimal there; at medium cost, it lacks a communication-cost threshold.Its generally better-than-fixed-policy performance is limited by the fact that within a given configuration it must always or never communicate.Source: §5.2 · p. 28
• STEAM’s maximum suboptimality was 0.587 under both low and medium communication cost, versus 0.700 for silent and 1.000 for Jennings; its mean was 0.063 and 0.083, respectively.Both mean values are below the silent policy’s 0.160 and Jennings policy’s 0.161.Source: §5.2 · p. 28
• The optimal communication policy is more flexible than STEAM, conditioning communication on the escort’s beliefs and transitioning gradually between always and never communicating.STEAM’s surface is a rough approximation with fewer degrees of freedom.Source: §5.2 · p. 28
• When observability is below 1, agents cannot attain mutual belief without communication, yet the locally optimal policy can make attaining mutual belief suboptimal in some configurations.The analysis identifies configurations where the locally optimal policy is expected to send fewer than one message.Source: §5.2 · pp. 28, 30
• STEAM tends toward extraneous communication under low observability and high communication costs, showing that its communication selectivity can still be suboptimal across a significant class of domains.The experiments reproduced this as a general tendency, rather than an isolated configuration.Source: §5.2 · p. 30
• In high-observability domains, the globally optimal policy can wait an extra time step after destroying the radar, then communicate only if the transport continues nap-of-the-earth flight.The locally optimal policy is itself suboptimal relative to the global policy.Source: §5.2 · p. 30
• The globally optimal policy can infer the transport’s flight method from its position history, effectively performing plan recognition without that capability being explicitly encoded in the domain.The general-purpose search algorithm discovers this inference strategy while traversing the policy space.Source: §5.2 · p. 30
• The globally optimal policy gained a slight expected-utility advantage over the locally optimal policy (mean difference 0.011, standard deviation 0.027, maximum 0.120).Source: §5.2 · p. 31
• The domain-independent code computed the locally optimal policy in under 5 seconds, while the search algorithm always took more than 150 minutes to find the globally optimal policy.Source: §5.2 · p. 31
• Using Theorem 7, COM-MTDP produced a communication policy that was nearly optimal, outperformed existing teamwork theories, and substantially reduced computation relative to finding the global optimum.Source: §5.2 · p. 31
• Although evaluated for an isolated communication decision, the authors expect relative policy performance to persist across multiple decisions, with larger losses from inflexible suboptimal policies.Source: §5.2 · p. 31

6. Summary

• By extending economic team theory with communication and dynamism, COM-MTDP can subsume many existing multiagent models.Source: §6 · p. 31
• COM-MTDP represents broad classes of team domains, enabling complexity results for arbitrary problem domains and identification of properties that simplify complexity.Source: §6 · p. 31
• The framework supports analysis across general domain classes and specific problem instantiations.Its methodology spans both broad classes and specific domains.Source: §6 · p. 31
• The framework can express existing teamwork theories and support broadly applicable theoretical results about their optimality.Source: §6 · p. 31
• For specific domains, the methodology uses general-purpose software tools to evaluate teamwork optimality, including for theories beyond the two joint-intentions instantiations demonstrated here.Source: §6 · p. 31
• Theoretical results can inform new coordination algorithms, and the framework, theorems, complexity results, and reusable software are intended as a basis for further teamwork analysis.The paper illustrates this link by translating Theorem 7 into an implemented algorithm for locally optimal communication.Source: §6 · p. 31

7. Future Work for COM-MTDP Team Analysis

• COM-MTDP analyses require knowledge of rewards, transition and observation probabilities, and agents’ competing policies, which may not always be readily available.Source: §7 · p. 32
• Other proposed team-analysis techniques (Nair, Tambe, Marsella, & Raines, 2002b; Raines, Tambe, & Marsella, 2000) do not require a priori hand-coding of such models, but acquire them automatically through machine learning.Source: §7 · p. 32
• The framework could be extended to learn model parameters and represent teams hierarchically, with multiple levels of abstraction (Nair et al., 2002b).Source: §7 · p. 32
• COM-MTDP analysis could cover team formation and reformation, including role assignment and reassignment after agent failure, potentially requiring explicit role models.Source: §7 · p. 32
• More complex team behaviors may require extensions that represent additional aspects of teamwork, such as authority structures.Source: §7 · p. 32
• Extending analysis to other kinds of coordination may require relaxing the shared-reward assumption to model non-joint rewards, with enriched models potentially requiring new mathematical foundations.Source: §7 · p. 32

Acknowledgments

• This article extends the authors’ earlier conference paper with missing proofs, new theoretical results, a detailed experimental setup, new experimental results, and additional discussion.Source: A kno wledgmen ts · pp. 32–33
• The research was supported by a DARPA award under the Control of Agent Based Systems program, managed by AFRL/Rome Research Site.Source: A kno wledgmen ts · p. 33
• The authors thank Daniel Bernstein, Ashish Goel, Daniel Maru, Stacy Marsella, Ranjit Nair, and Paul Rosenbloom for discussion and feedback, and the anonymous reviewers for comments and suggestions.Source: A kno wledgmen ts · p. 33

References

• The bibliography includes research on the complexity of decentralized control of Markov decision processes (Bernstein, Zilberstein, & Immerman, 2000).Source: Referen es · p. 33
• The listed work also covers coordination algorithms, partial global planning, and joint intentions in multiagent systems (Decker & Lesser, 1995; Durfee & Lesser, 1991; Jennings, 1995).Source: Referen es · p. 33
• It cites work on team decision theory and the information structures used in team decisions (Ho, 1980; Marschak & Radner, 1971).Source: Referen es · pp. 33–34