Imitation Learning of Team-play in Multiagent System based on Hidden Markov Modeling

1 Introduction

Imitation learning is considered to be a method to acquire complex human and agent behaviors and as a way to pro­ vide seeds for further learning [K193; Sch99; MK98]. While those studies have focused on imitating behaviors of single agents, few works address imitation for teamwork among multiple agents because the complexity of the world state increases drastically in multi-agent systems. On the other hand, stochastic models like hidden Markov models (HMM) have been studied as tools to model and to represent multi­ agent/human interactions [ORPOO; IB99]. It is, however, hard to apply these stochastic models to imitate teamworks by ob­ servation because of the complexity of the model of multiple agents. This study focuses upon intentions of agents as build­ ing blocks of an abstract state of the local world for the agent in order to overcome the problem. Using intention, I for­ malize teamwork and propose a hierarchical hidden Markov model for imitation learning of teamwork.

2 Teamwork and Imitation

2.1 Intention and Play

We suppose that an intention is a short-term idea to achieve a certain condition from another condition. For example, in soccer, the intention 'to guide a ball in a certain direction' is an idea to move to a certain direction with the ball. We assume that an intention is an individual idea; therefore, an agent does not pay attention to others' efforts to achieve their intention.

A play is postulated as a sequence of atomic actions to achieve a single intention. The play is a basic building block of overall behavior of agents. For example, in soccer, a 'drib­ ble' is a play to achieve the intention 'guide a ball in a cer­ tain direction', which consists of atomic actions like 'turn', 'dash', 'kick', and so on. A play for the intention is also an in­ dividual behavior without collaboration with other agents be­ cause an intention is an individual idea. As shown below, an intention and the corresponding play are used as a main trig­ ger to synchronize team-plays among multiple agents. This means that the intention is treated as a kind of partial condi­ tion of the world.

2.2 Team-play

We suppose that team-play is a collection of plays performed by multiple agents to achieve a certain purpose. As men­ tioned in the previous section, an intention is an individual idea. This means that multiple agents who do not change their intentions can not perform a team-play because they have no way to synchronize their plays. Instead, we assume that they can synchronize their plays by changing their intentions ac­ cording to situations of environments and intentions of other agents. For example, in soccer, when two players (passer and receiver) guide a ball by dribble and pass, players will change their intentions as follows:

In this example, the passer and the receiver initially have intentions 'dribbling' and 'supporting', respectively. Then, the passer changes the intention to 'seek-receiver', followed by the receiver's change to 'free-run', the passer's change to 'pass', and so on. Play synchronization is represented as con· ditions when agents can change the intention. In the example, the passer changes its intention from 'seek-receiver' to 'pass' when the teammate's intention is 'free-run'.

2.3 Imitation Learning of Team-play

The imitation learning of a team play is formalized as follows: (I) Observation: to observe behaviors of mentor agents and estimate what intention each agent has at each time step. (2) Extraction: to extract conditions prevailing when each agent changes intentions. A condition is represented as a conjunc­ tion of others' intentions. (3) Generation: to generate a se­ quence of intentions according to changes of environment and others' intentions. In the second step of this process, the in­ tention plays an important role: that is, conditions of changes of intentions. As described in Section 2.1, we consider that intention can represent world conditions. In addition to it, we use only intentions to construct rules for agents to change their intentions.

3 Hierarchical Hidden Markov Model for Agents

3.1 Single Behavior Model

We formalize behaviors of a basic play m performed by a single agent as a Moore-type HMM as follows:

where Sm = {smi li E Sm} is a set of states, V m = {vk} is a set of a pair of sensor value and action commands which are used as outputs from the state, Pm = {Prnij li, j E Sm}, Qm = {qmi (v)li E Sm, V E V m}, and Rm = {rmili E S m} are probability matrixes of state transition, state-output, and initial state, respectively.

3.2 Cooperative Behavior Model

As discussed in the previous section, we consider that team­ play consists of a sequence of intentions of multiple agents. This means that cooperative behavior of a single agent in a team of agents is considered as transitions among several ba­ sic plays (HMM'). Therefore, we formalize cooperative be­ havior as the following modified Mealy-type HMM,

where M = {HMM'm} is a set of basic plays and U { uk} is a set of output from the model (normally, same as M); E = {em lm E M} is a set of initial play probabilities, F = {frwin lm E M, i E Sm, n E M} is a set of exit­ ing probabilities from plays, and G = {9mnj lm E M, n E M , j E S n} is a set of entering probabilities to plays. Also, H = {hmn(u)lm E M, n E M, u E U} is a set of gate probabilities between plays. Formally, these probabilities are defined as: em = Pr(~>), !min= Pr(R~>is~~), 9rnnj = Pr(s~J IR~- 1 ) ), and hmn(u) = Pr(u(t- 1 ) IR~- 1 ), R~>).

Using these probabilities, an actual probability from state i in play m to state j in play n is calculated as

3.3 Joint-Behavior Model

Finally, we coupled multiple HMM<s, each of which repre­ sents the behavior of an agent. Coupling is represented by gate probabilities H. For example, when agent X and agent Y are collaborating with each other, the gate probability hmn ( u) in HMMc for agent X indicates the probability that agent Y is performing play u at time t when agent X changes the play from m ton during time t-+t + 1. Using the gate probability, the agent calculate a likelihood of the state Snj at a certain time t + 1 according to the following equation:

, where i)(t+l) is a partially observed output value in vat time t + 1.

4 Experiments

I applied the framework to collaborative play of soccer. The demonstration by mentors is dribble and pass play as shown in Fig. 1: A player starts to dribble from the center of the left half field and brings the ball to the right half. At the same time, another player runs parallel along the upper (or lower) side of the field supporting the dribbling player. Then, the first player slows to look-up the second player; it then passes the ball to that player. Simultaneously, the second player starts to dash to the ball and dribbles after receiving the ball. After the pass, the first player exchanges roles with the teammate so that it becomes a supporting player for the second player.

To imitate this demonstration, I trained six HMM's to model 'dribble', 'slow-down and look-up', 'pass', 'free-run', 'chase-ball', and 'support'. Each ofHMM's has 5 states. The output of these HMM's consists of local situations (the rela­ tive position and the velocity to the ball) and agent's actions ('tum', 'dash', 'small-kick', 'long-kick', 'trap', and 'look'). Note that there is no information about others' situations for output of HMM's. As described in Section 2.2, others' situ­ ations are taken into account during the Extraction phase in learning.

Two HMM<s for agent X (the first player) andY (the sec­ ond player) are constructed after the training of the HMM's. Then, the learner observes behaviors of the mentor and ad­ justs probabilities of the HMM<s.

Figure 2 shows result of observation and estimation. This figure shows the relative likelihood of each play state for each agent at each timestep estimated by Observation phase. In this figure, there are 12 rows of small squares: upper 6 rows correspond 6 plays of the first player (agent X), and the rest 6 are plays for the second player (agent Y). Each row corre­ sponds to a play D, K, P, F, C, and S, each of which means 'dribble (D)' , 'slow-down and look-up (K)', 'pass (P)', 'free­ run (F)', 'chase-ball (C)', and 'support (S)', respectively. In each row, a column consists of 5 small squares each of which corresponds a state ofHMM'for one of the 6 plays at a certain timestep. The ratio of black area in the square indicates the relative likelihood with which the state of the HMM'is active at the timestep. Columns are aligned along with time. So, a horizontal line of squares means changes of likelihood of a state of HMM'. From this figure, we can see that the learner estimates that the agent X starts the play with the intention of 'dribble', followed by 'slow-down', 'pass' and 'support', while the player Y starts 'support' play, followd by 'chase­ ball' and 'dribble' plays.

After the training by the Observation, the learner can gen­ erate behaviors similar to the demonstration by using the ac­ quired probabilities of the HMM<as shown in Fig. 3. This figure is constructed in the same way as Fig. 2, but only one square is filled in a timestep because the Ieamer decides one of the possible states according to the likelihood shown in Eq. I. In this example, although the Ieamer sometimes gener­ ates wrong state transitions, for example a transition to states to the 'free-run' play in agent Y during agent X is doing 'slow-down', it recovers to the suitable transitions and con­ tinues to imitate the demonstrator. This shows robustness of the model against accidents. Because the model is cou­ pled loosely with world and other's states by output probabil­ ities of HMM, it can permit variation and misunderstanding of world and others' states.

5 Discussion

There are several works on coupling HMMs that can repre­ sent combinational probabilistic phenomena like multi-agent collaboration [JGS97; GJ97; JGJS99]. In these works, prob­ abilistic relation among several HMMs (agents) are repre­ sented as state-transition probabilities, such that the amount of memory complexity increases exponentially. This is a se­ rious problem for imitation learning because we assume that the number of examples for imitation is small. In our model, the relation among agents is represented by gate probabilities H, in which others' states are treated as outputs instead of as conditions of state transition. Using them, the likelihoods of state-transitions are simplified as products of several prob­ abilities (Eq. 1 ). In addition, detailed states of other agents are abstracted by play (intention), As a result, the number of parameters is reduced drastically, so that learning requires very small number of examples as shown in above examples. Although such simplification may decrease flexibility of rep­ resentation as a probabilistic model, experiments show that the proposed model has enough power to represent team-play among agents.

Intention in the model brings another aspect to communi­ cation among agents. We assume that there are no mutual communication in the proposed model. However, we can in­ troduce communication as a bypass of observation and esti­ mation of other's intention (play). The proposed model will be able to provide criteria for when an agent should inform their intention to others by comparing agents' actual inten­ tions and estimated intention of the agent itself by simulating its own HMMc .

One important issue is the design of the intention. In the proposed model , intentions play various important roles like chanking of the actions and conditions of world state. There­ fore, we must design intentions carefully so that team-plays can be represented flexibly.