Team ChaGamma-2004

NODA, Itsuki

Cyber Assist Reseach Center National Institute of Advanced Industrial Science and Technology; Japan Advanced Institute of Science and Technology

Abstract Chagamma-2004 is based on released code of UvA Trilearn-2004's, and enhanced in communication module.

Efficient Communication Using Agent Modeling

In Chagamma-2004, I'm attacking an issue to apply agent modeling for efficient communication. In speech-act theory used in FIPA's ACL (Agent Communication Language), a sender, who intend to inform a message to a receiver, is assumed not to believe the receiver already knows the message. In order to estimate receiver's belief, I apply agent modeling method based on hidden Markov model(HMM).

In FIPA's specification of ACL[FIP01], the condition for a sender s to inform a message φ to a receiver r is:

$$\mathbf{B}_s(\phi) \wedge \neg \mathbf{B}_s(\mathbf{Bif}_r(\phi) \vee \mathbf{Uif}_r(\phi)) \tag{1}$$

In the context of soccer games, a player s should inform his plan (intention) I(play) to a teammate r when:

the player s wants to do play, and
the player s thinks the teammate r does not know that s wants to do play.

Similarly, the condition for a sender s to ask (Call-for-Proposal) an action act to a receiver r is:

$$\neg \mathbf{Bref}_s(\iota(x:\alpha(x))) \land \neg \mathbf{Uref}_s(\iota(x:\alpha(x)))$$ $$\land \neg \mathbf{BsIrDone}(\langle r, \mathsf{Inform\text{-}ref}(s, \iota(x:\alpha(x))) \rangle), \tag{2}$$

where

$$\alpha(x) = \mathbf{I}_s \mathbf{Done}(\langle r, act \rangle | \phi(x)) \Rightarrow \mathbf{I}_r \mathbf{Done}(\langle r, act \rangle | \phi(x))$$

This means that a player s should ask a teammate r to do play when s does now know a way to let r do play without explicit communication in the soccer context. Using these conditions, we can reduce redundant communication among players.

In order to realize this efficient communication, we need a way to estimate teammate's belief, that is, to know Bs(Br(...)), Bs(Ir(...)) and so on. And, I'm trying to apply HMM technique for it. In my previous works[NOD03b,NOD03a], I proposed a hierarchical hidden Markov model to represent teamwork. In the model, I suppose that a player's behavior consists of a sequence of a simple plan (intention), and a simple plan consists of a sequence of actions. Both levels of sequences are modeled as hidden Markov model respectively, and coupled hierarchically. In addition to it, other's intentions are coupled as a condition of state transition in high-level (simple-plan level). Figure 1 illustrate the relations between two-level HMM and between agents.

Using probabilities and likelyhood calculated in the model, the agent can check conditions of communication shown in Eq. 1 and Eq. 2. In the model, an agent always estimates likelyhood of teammate's intentions using observation. This likelyhood represents the confidence of $\mathbf{B}_s(\mathbf{I}_r(...))$ , that is, teammate's intention in the belief of agent itself. Also, the agent can calculate likelyhood of its intention using only observation. The value represents the confidence of $\mathbf{B}_s(\mathbf{B}_s(\mathbf{I}_s(...)))$ , and can be used as an approximation of confidence of $\mathbf{B}_s(\mathbf{B}_r(\mathbf{I}_s...))$ .

Fig. 1. Hierarchical Hidden Markov Modeling for Team-play in Multiple Agents

References

[FIP01] FIPA, Geneva, Switzerland. FIPA Communicative Act Library Specification, Jan. 2001. Document number XC00037 (http://www.fipa.org/). [NOD03a] Itsuki NODA. Hidden markov modeling of team-play. In Proc. of IJCAI-2003, pages 1470–1472. Morgan Kaufmann, Aug. 2003. [NOD03b] Itsuki NODA. Hidden markov modeling of team-play synchronization. In Proc. of RoboCup 2003, Jul. 2003.