Fantasia 2006 Team Description

Dingming Guo, Shulin Zhang, Guangbin Cui

Institute of University Students' Innovation, Dalian University of Technology, China

Abstract This paper simply describes the characteristics of the Fantasia team participating in RoboCup 3D Soccer Simulation League. Our main research focus lies on the cooperation and coordination of the multi-agent system. Thus we devised a collaboration oriented agent architecture on which we applied our approach based on Hungarian Method for solving task allocation problems and reconciling conflictions. Besides, the dynamic models of mobile objects and some behavior handling techniques are also mentioned in the paper.

1. Introduction

Fantasia as a research project that focuses on intelligent and autonomous agent and multi-agent system problems [1], [2] was established in 2005. And the team have been devoted to the research and development of intelligent algorithms and mathematic models that deal with realistic issues. Last year, the Fantasia participated in the Robocup China 2005 (July 28-30) and won the 3rd place in Robocup simulation 3D group. In the recent version of Fantasia soccer agent, a four-layer agent architecture, a set of low-level agent skills and high-level cooperation strategies are implemented. And this has made the team outplay the 2005 world champion with the highest score which is 2 to 0.

In the next section, we will introduce the architecture of Fantasia soccer agent. In Section 3, we will give our findings about the dynamic models of the soccer and the ball. And in Section 4 and Section 5, we will discuss behavior modeling techniques and a coordination approach based on Hungarian method respectively. In the last section, we will end with a summary.

2. Agent Architecture

A four-layer collaboration oriented architecture based on the BDI theory is implemented in the Fantasia soccer agent, as Fig.1 illustrates. The lowest layer which consists of a perceptron and an atomic action executor deals with the interactions between the agent and the environment. Then, the world model and the behavior handler occupy the second layer. A rich world model not only represents observations from the environment and the current agent state, but also reflects the possibility of the information observed and the confidence of possible states and the agent's inner belief which involves the common knowledge [3] about the simulation world and the agent's comprehension to the current situation. As a POMDP problem, the concept of probability popularly exists in the whole agent system. The first two layers described above are the infrastructure, while the remainders are the kernel. The next layer is composed of a decision module and a task manager that handles the allocation and cooperation of a certain task. The last but not the least, the highest layer indicates the agent's desire, which contains the goal shared between a group of cooperative agents and the possible policy. Although the work is not complete enough now, this framework has shown a good performance of collaboration in the match.

3. Dynamic Models

The physical model of 3D simulation server is based on the ODE (Open Dynamics Engine). It is hard to find the dynamic rules from the source code. By proceeding data fittings to a great amount of samples, an approximate representation has been found. All acting forces which are not exactly the power given by the agent's commands, should be transformed as

$$\vec{F} = \vec{F}_a \cdot \eta ,.$$

Here, $F_a$ is the force contained in the agent's command, and η is an effectiveness coefficient. The coefficient of kick force $\eta_k$ and that of drive force $\eta_d$ are totally different. While processing a ball in the air, the gravity $\vec{g}$ should also be considered, like

$$\vec{F} = \vec{F}_k + m_b \vec{g} ,.$$

There is a drag force which is directly proportional to the velocity $\vec{v}$. However, the drag coefficient $\mu_s$ of the soccer is different from the one of the ball, while the drag coefficient $\mu_{bg}$ of the ball on the ground is different from that $\mu_{ba}$ of the ball in the air. With an acceleration of differential form, we get a differential equation in terms of Newton's Second Law

$$\vec{F} - \mu \vec{v_t} = m \frac{dv_t}{dt} ,.$$

Assuming the velocity of a object is $v_0$ at time $t_0$, the velocity $\vec{v}_t$ can be calculated as

$$\vec{v}_t = \frac{\vec{F}}{\mu} + \left(\vec{v}_0 - \frac{\vec{F}}{\mu}\right) \cdot e^{-\frac{\mu}{m}(t - t_0)} ,.$$

The relative displacement $\vec{S}_{t-t_0}$ can be attained by

$$\vec{S}_{t-t_0} = \frac{\vec{F}}{\mu} (t - t_0) + \frac{m}{\mu} \cdot \left( \vec{v}_0 - \frac{\vec{F}}{\mu} \right) \cdot \left( 1 - e^{-\frac{\mu}{m} (t - t_0)} \right) ,.$$

On top of the above, we have developed a set of prediction routines, which work well in practice, to estimate the movement of a dynamic object.

4. Behavior Modeling Techniques

Based on the architecture introduced in section 2, the command of each simulation cycle is made from the bottom of agent layers up to the top and then from the top down to the bottom [4]. In other words, the infrastructure offers the information that supports the decision making and provides the capability of breaking down the task into atomic actions. And the behavior handler handles the latter. Some behavior modeling techniques are discussed below.

In the 3D server, the ball can only be accelerated radially away from the soccer body in the horizontal plane. Therefore, to perform an action to ball such as pass and shoot requires at least tow steps, of which the first step is to adjust the position relative to the ball and the second is kicking the ball. We consider that the procedure of position adjusting is the key step of the whole action for the search space of the agent is very small while kicking and the only thing to do is finding an appropriate force to kick in such passive circumstance. While considering the first step, general search algorithms could not get an optimum solution in limited time due to the vast state space growing with prediction period and the noise of observation signal. A number of constraint factors are set in the earlier version of Fantasia, and the solution space is reduced to a certain extent through the application of these constraint factors and team strategies. As a result, this problem is possible to be solved by heuristic search and dynamic programming. For example, an agent may ignore the teammates without cooperative relationship with itself and opponents far away from it. Furthermore, some empirical critical profit (or deficit) parameters are employed to cut down the search tree. These methods are easy to bring to effect and be debugged, but the shortcomings are obvious in partially observed environment, such as low stability, lack of flexibility and high dependency to parameters. Recently, Fantasia is trying to express state transition and observation model with extended Dynamic Bayesian Network (i.e. Dynamic Decision Networks), and solve the problem by policy iteration method [5]. Although the new approach still could not be proved outperforming the old one for the moment, it is significant to use the POMDP algorithms for it approximates to the essence of the problem, and what is more, it has much potential in the solution of such search problems [6].

5. Cooperation and Coordination

A complete collaboration procedure often consists of 3 phases, including negotiation, cooperation and coordination. Compared to other fields, the communication among agents is restricted in RoboCup Simulation Competition. Before the 3D server of version 0.4, the agents even could not communicate with each other. Moreover, the real-time performance is highly demanded in such dynamic environment. For these reasons, negotiation procedure is of little use.

The aim of cooperation is to share the same goal among a group of agents and to find an optimal tasks assignment solution [7]. Cooperation mainly depends on the common knowledge, the situation context and teammate behavior modeling techniques. In the architecture of Fantasia, cooperation is established on the layer of task, to obtain the balance between the effectiveness of individual serial tasks and the effectiveness of team parallel tasks. Conducting intention possibility identification which depends on the agent's common knowledge such as formation and strategy schema is able to maintain the consistency of team behavior in the environment without communication. However, owing to the uncertainty of observation, action conflicts between agents could not be avoided. The conflictions appear extremely obvious while intercepting and defending. Therefore, it is necessary to add a particular module to discover and coordinate conflictions. The aim of coordination is different from cooperation; the latter emphasizes on solving conflicts and keeping the accordance of team play though the result is not always optimum, while the former gives the optimal result in the precondition of no conflicts. The side effect of conflictions is not neglectable in these cooperation problems such as "Prisoner's Dilemma", in which the consistency is more important.

Fantasia agent includes a mechanism for discovering and reconciling conflictions. This method is a transformation from Harold Kuhn's well-known Hungarian Method which is used to solve optimal assignment problems [8], [9]. Taking $n$ tasks ($t_1, \ldots, t_n$) to $n$ agents ($a_1, \ldots, a_n$) problem for example, this method could figure out an optimal allocation of these tasks based upon each agent's weight to each task. Nevertheless, the stability of the solution is always not satisfying because of the existence of random errors and we also have found that Hungarian Method could not get convergent results in a partially observed environment.

Suppose communication of intentions is allowed and then the intention matrix $I = \left[a_i\left(t_j\right)\right]_{n \times n}$ consisting of all the agents' intentions is easy obtained by

$$\begin{cases} a_i(t_j) = 1 & a_i \text{ perform } t_j \ a_i(t_j) = 0 & \text{else} \end{cases}$$

Therefore, if there is a $j$ yielding

$$\sum_{i=1}^{n} a_i \left( t_j \right) \neq 1,$$

it means the task $t_j$ conflicts with another. For instance, both of two full backs have treated the same opponent as their defense target. We find out two ways to solve the conflict in experiments, of which the easier one will be discussed below. This approach having a high rapidity of convergence within 2 or 3 cycles is on the principle of keeping the original tasks of the agents without conflicts.

First of all, the intention matrix $I_{n\times n}$ should be transformed to the one satisfying the following conditions

$$\begin{cases} \sum_{i=1}^{n} a_{i}(t_{j}), j = 1.0, \dots, n \ \sum_{j=1}^{n} a_{i}(t_{j}), i = 1.0, \dots, n \end{cases}$$

Suppose Hungarian Matrix $H = [h_{ij}]{n \times n}$, and the maximum form of Hungarian Method is adopted, then $H{n \times n}$ should be modified as

$$h'{ii} = h{ii} + a_i(t_i) \cdot \eta \cdot \tau, \quad i, j = 1, \dots, n$$

Here, $\eta$ (an appropriate quantity could be trained by off-line learning, and a more accurate value could be adjusted during the game) is a modified coefficient and $\eta > \max(h_{ij})$, while $\tau$ is a stochastic disturbance for facilitating the convergence.

Now, we get a new Hungarian Matrix $H' = [h'{ij}]{n \times n}$.

Finally, we apply Hungarian Method to $H'_{n\times n}$ and gain an appropriate solution.

In fact, even if the mutual modeling method of teammate behavior is used, it is still hard to attain the real intentions of teammates. For this we use a matrix of probabilities of intensions instead by introducing the probabilities of intensions and the elements satisfy

$$\sum_{i=1}^{n} a_i(t_j) = 1.0, \quad i = 1, \dots, n ,.$$

And upon that we are able to get a better result follow the approach mentioned above.

6. Summary

In this paper we briefly described the ideas implemented in Fantasia and some helpful findings we have achieved. The dynamics formulas mentioned in section 3 well matched with the data acquired from the monitor. And a BDI based agent framework with the concepts of probability and confidence provide strong support to the POMDP algorithms and future extending. Since the Fantasia is on the threshold of Robocup competition, hand-coded methods and empirical rules are still being used. However, our main interest concentrates on the multi-agent collaboration and further research will be continuously performed in the future work.

References

1. Weiss, G., ed.: Multiagent Systems: a Modern Approach to Distributed Artificial Intelligence. MIT Press (1999).
2. Vlassis, N.: A concise introduction to multiagent systems and distributed AI,Informatics Institute, University of Amsterdam (2003).
3. J. Geanakoplos: Common knowledge. Economic Perspectives, 6(4), 1992.
4. P. Stone.: Layered Learning in Multi-Agent Systems. PhD thesis, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, Dec. 1998.
5. Hansen, E. (1998). Solving POMDPs by searching in policy space. In Proceedings of the 14th Conference on Uncertainty in Artifical Intelligence (UAI), pp. 211–219, Madison, WI.
6. D. Aberdeen. A (Revised) Survey of Approximate Methods for Solving Partially Observable Markov Decision Processes. Technical report, National ICT Australia, 2003.
7. P. Stone, M. Veloso: Task Decomposition, Dynamic Role Assignment, and Low-Bandwidth Communication for Real-Time Strategic Teamwork. In: Artificial Intelligence, 110(2):241–273,1999.
8. P. Gerkey, J. Mataric: A formal analysis and taxonomy of task allocation in multi-robot systems. In: Intl. Journal of Robotics Research, 23(9):939-954, September 2004.
9. W. Agassounon, A. Martinoli: A Macroscopic Model of an Aggregation Experiment using Embodied Agents in Groups of Time-Varying Sizes, In: Proc. of the IEEE Conf. on System, Man and Cybernetics (SMC), Hammamet, unisia, pp. 250–255,2002.