Much of the following is an excerpt from the COM-MTDP JAIR article, providing additional details about:

• the helicopter domain used as a running example,
• the model of states, actions, world dynamics, and reward function used,
• the model of observability used, and
• the specific policies implemented and analyzed in our experiments.

NOTE: The special symbols and notation contained in this document may not be displayed correctly by your browser.

Consider two helicopters that must fly across enemy territory to their destination, as illustrated in Figure 1. The first, piloted by agent Transport, is a transport vehicle with limited firepower. The second, piloted by agent Escort, is an escort vehicle with significant firepower. Somewhere along their path is an enemy radar unit, but its location is unknown (a priori) to the agents. Escort is capable of destroying the radar unit upon encountering it. However, Transport is not, but it can escape detection by the radar unit by traveling at a very low altitude (nap-of-the-earth flight), though at a lower speed than at its typical, higher altitude. In this scenario, Escort will not worry about detection, given its superior firepower; therefore, it will fly at a fast speed at its typical altitude.

The two agents form a top-level joint commitment, G_D, to reach their destination. There is no incentive for the agents to communicate the achievement of this goal, since they will both eventually reach their destination with certainty. However, in the service of their top-level goal, G_D, the two agents also adopt a joint commitment, G_R, of destroying the radar unit. We consider here the problem facing Escort with respect to communicating the achievement of goal, G_R. If Escort communicates the achievement of G_R, then Transport knows that it is safe to fly at its normal altitude (thus reaching the destination sooner). If Escort does not communicate the achievement of G_R, there is still some chance that Transport will observe the event anyway. If Transport does not observe the achievement of G_R, then it must fly nap-of-the-earth the whole distance, and the team receives a lower reward because of the later arrival. Therefore, Escort must weigh the increase in expected reward against the cost of communication.

COM-MTDP Model of States

In the COM-MTDP model of this scenario (presented in Figures 2, 3 and  4), the world state is the position (along a straight line between origin and destination) of Transport, Escort, and the enemy radar. The enemy is at a randomly selected position somewhere in between the agents' initial position and their destination. Transport has no possible communication actions, but it can choose between two domain-level actions: flying nap-of-the-earth and flying at its normal speed and altitude. Escort has two domain-level actions: flying at its normal speed and destroying the radar. Escort also has the option of communicating the special message, s_GR, indicating that the radar has been destroyed. In the tables of Figures 2, 3 and 4, the ``·'' symbol represents a wild-card (or ``don't care'') entry.

• P( < x_E0,x_T0,x_R0 > , < a_E,a_T > , < x_E1,x_T1,x_R1 > )=
  P_E(x_E0,a_E,x_E1)·P_T( < x_T0,x_R0 > ,a_T,x_T1)·P_R( < x_E0,x_R0 > ,a_E,x_R1)

  Escort:

  Initial distribution, Pr(X_E⁰=0)=1
  

  xE0 aE xE1 PE Destination · Destination 1 0,...,8 fly xE0+1 1 0,...,8 destroy xE0+1 1 9 fly Destination 1 9 destroy Destination 1 · wait xE0 1

  Transport:

  Initial distribution, Pr(X_T⁰=0)=1
  

  xT0 xR0 aT xT1 PT Destination · · Destination 1 Destroyed · · Destroyed 1 0,...,9 · fly-NOE xT0+0.5 1 9.5 · fly-NOE Destination 1 0,...,8.5 Destroyed fly-normal xT0+1 1 9,9.5 Destroyed fly-normal Destination 1 · ¹ Destroyed fly-normal Destroyed 1 · · wait xT0 1

  Radar:

  Initial distribution, "x Î {1,2,...,8}, Pr(X_R⁰=x)=0.125
  

  xE0 xR0 aE xR1 PR · xE0 destroy Destroyed 1 · · ¹ destroy xR0 1 · ¹ xE0 · xR0 1

COM-MTDP Model of Observability

• W_a=W_E×W_T
  • W_E=X_E×X_T×W_RE, where agent Escort's possible observations of the radar consist of W_RE={present,destroyed,null}

  • W_T=X_E×X_T×W_RT, where agent Transport's possible observations of the radar consist of W_RT={destroyed,null}

• O_a(s, < a_E,a_T > , < w_E,w_T > ) = O_E(s, < a_E,a_T > ,w_E)·O_T(s, < a_E,a_T > ,w_T)
  • O_E( < x_E,x_T,x_R > , < a_E,a_T > , < x_E,x_T,w_RE > )=
    

    xE xR aE wRE OE · destroyed destroy destroyed 1 · destroyed ¹ destroy null 1 xR 1,...,9 · present 1 ¹ xR 1,...,9 · null 1

  • O_T( < x_E,x_T,x_R > , < a_E,a_T > , < x_E,x_T,w_RT > )=
    

    xT xR aE wRT OT 0,...,9.5 · destroy destroyed le-(xR-xT)(1-l) 0,...,9.5 · destroy null 1-le-(xR-xT)(1-l) 0,...,9.5 · ¹ destroy null 1 destroyed · · null 1

    l Î [0,1]

If Escort arrives at the radar, then it observes its presence with certainty and can destroy it to achieve G_R. The likelihood of Transport's observing the radar's destruction is a function of its distance from the radar. We can vary this function's observability parameter (l in Figure 4) within the range [0,1] to generate distinct domain configurations (0 means that Transport will never observe the radar's destruction; 1 means Transport will always observe it). If the observability is 1, then they achieve mutual belief of the achievement of G_R as soon as it occurs (following the argument presented in Section 4.1). However, for any observability less than 1, there is a chance that the agents will not achieve mutual belief simply by common observation. The helicopters receive a fixed reward for each time step spent at their destination. Thus, for a fixed time horizon, the earlier the helicopters reach there, the greater the team's reward. Since flying nap-of-the-earth is slower than normal speed, Transport will switch to its normal flying as soon as it either observes that G_R has been achieved or Escort sends the message, s_GR. Sending the message is not free, so we impose a variable communication cost (r_S in Figure 2), also within the range [0,1].

We constructed COM-MTDP models of this scenario for each combination of observability and communication cost within the range [0,1] at 0.1 increments. For each combination, we applied the Jennings and STEAM policies, as well as a completely silent policy. For this domain, the policy, p_aS^J, dictates that Escort always communicate s_GR upon destroying the radar. For STEAM, we vary the t and C_c parameters with the observability and communication cost parameters, respectively. We used two different settings (low and medium) for the cost of miscoordination, C_mt. Following the published STEAM algorithm [Tambe, 1997], Escort sends message s_GR if and only if STEAM's inequality t·C_mt > C_c, holds. Thus, the two different settings, low and medium, for C_mt generate two distinct communication policies; the high setting is strictly dominated by the other two settings in this domain.

We also constructed and evaluated locally and globally optimal policies. Under domain configurations with high observability, the globally optimal policy has the escort wait an additional time step after destroying the radar and then communicate only if the transport continues flying nap-of-the-earth. The escort cannot directly observe which method of flight the transport has chosen, but it can measure the change in the transport's position (since it maintains a history of its past observations) and thus infer the method of flight with complete accuracy. In a sense, the escort following the globally optimal policy is performing plan recognition to analyze the transport's possible beliefs. It is particularly noteworthy that our domain specification does not explicitly encode this recognition capability. In fact, our algorithm for finding the globally optimal policy does not even make any of the assumptions made by our locally observable policy (i.e., single agent is deciding whether to communicate or not, regarding a single message, at a single point in time); rather, our general-purpose search algorithm traverses the policy space and ``discovers'' this possible means of inference on its own. We expect that such COM-MTDP analysis can provide an automatic method for discovering novel communication policies of this type in other domains, even those modeling real-world problems.

References

[Tambe, 1997]

Tambe, M. 1997. Towards flexible teamwork  Journal of Artificial Intelligence Research, 7, 83-124.