HfutEngine2013 Simulation 2D Team Description Paper

Yongxing Dai, Shuanglu Dai, Jianxiong Pan, Huaizhi Tang, Hui Wang, Qiang Lu, Dongfei Wu, Shiquan Wang, Hao Wang, Baofu Fang

Artificial Intelligence And Data Mining Lab

Abstract This paper mainly describes the new method of HfutEngine2013, which aims to deal with the problem of passing-ball model and the intelligent way to pass balls. The passing behavior can be interpreted with the Information Theory.

Introduction

Team HfutEngine was founded in 2002 and took part in the RoboCup ChinaOpen2002.In the following years, HfutEngine develops fast and joins many matches. From 2005, the team used UVA BASE 2003 as the base code, and added AI methods to it and updated the code along with the server's upgrade. In RoboCup ChinaOpen 2007, the team gained the 2nd place of soccer simulation 2D. Furthermore, it got the 7th place of soccer simulation 2D in World RoboCup 2008 and 4th place of soccer simulation 2D in RoboCup ChinaOpen 2009[5]. We hope to obtain a good grade in World RoboCup 2013. It is the 4th time for us to take part in The World RoboCup. We want to probe into Multi-Agent System and Robocop with anyone interested in them.

Passing-ball Algorithms based on the value of behavior

Robot Soccer is an important way for multi-agent research. In our exploitation we found that any Multi-Agent cooperation was based on how the single agent adapt to the Multi-Agent System. If every element in the system can accommodate the system, the system is steady[11, 12]. It is not need to have unitized command for every agent. Our strategy is based on the value judgment, that is every Agent has its own evaluator to calculate correspond value. Then the action which have max value is being executed by executants[11] .

2.1 Passing decisions introduction

Each team has their own method to pass accurately and fluently which ensures the decision executive. For example, the passing incomes in the future can be forecast with the training of Artificial Neural Networks used in WrightEagle[7] . The Delaunay Triangulation algorithm is used in the formation as an aid of the passing-ball model in Helios, which gains satisfied effect[6]. The concept of crossing speed is introduced into Tsinghua.s team to ensure the accuracy of the pass.

2.2 HfutEngine2013's passing-ball model

HfutEngine2013's passing-ball model is showed as Figure 1. To obtain a value, every point is put into the evaluation function trained by learning based on axiology[4]. An identified passing point can be determined by the highest value of these points. Since the weights of the evaluation function has been fixed by the method of Learning Based on Axiology, the passing still miss frequently in the race, which is needed to be fixed again with a new method.

Weights Adjustment Algorithm based on reinforcement learning

(Section header only; see subsections below)

3.1 Construction of Markov source transfer matrix

(Section header only; see subsections below)

3.1.1 The Markov source transfer matrix algorithm

When any message of the source sequence only has relation with the previous one, it is mathematically defined as the first-order Markov chain. If the transition probability is independent of the location of the Markov chain, it is called Homogeneous Markov chain[1-3]. The transition probability from source A to source B can be calculated according to Bayes' theorem[2]:

$$P(B_i \mid A) = \frac{P(B_i)P(A \mid B_i)}{\sum_{i=1}^{n} P(B_i)P(A \mid B_i)}$$

3.1.2 State description of the source of Markov transfer matrix

As illustrated in Fig.2, the Stadium is divided into a set of 10*10 rectangles as the states of Markov source and each source has 100 transmission directions.

3.2 Transition probability matrix of Markov source training

An additional property is added to each position in the transfer matrix which marks the success of the pass. The property in each position of the transfer matrix is obtained by 100 games with Helios2008 which provides a sufficient amount of data to calculate the proportion of the successful pass which means the transfer probability[3, 4].The steps of training are listed as follows:

Step1: Each position in the transfer matrix can be initialized to 0.01 which means the transfer probability.

Step2: Once a successful pass happened, the property will be plus one, otherwise it will be plus zero.

Step3: Use the property to calculate the transfer probability in each position of the transfer matrix.

The transfer probability in each position equals to the property which belongs to this position divided by the sum of the property.The Markov matrix chart of information source transmitting, obtained by training, is showed as Figure 3, which shows the distribution of the passing rate in the whole field, where double-digit coordinate values of axis X represent the information source region of the holding player while double-digit coordinate values of axis Y represent the information source region of the catching player and those of axis Z reflect the passing rate from information source region X to Y.

Experiments and analysis

(Section header only; see subsections below)

4.1 Comparison of the passing method with other teams

The two peak values of the passing rate are respectively situated in the front midfield and the back midfield, which is similar with the positions of the other two peak values showed by WrightEagle's image of position evaluation[6] . In addition, The revising method of evaluated values in Markov process can obtain the p-t-p passing value, which possesses better dynamic characteristics. Relative to Tsinghua's fixed passing models, our methods can also be applied to more situations such as dribbling and clearing ball.

4.2 Training effect

After a long time of training, the team has received very good effects, the passing quality enhanced significantly. The result compared with the passing rate of the original team is showed as Table 1 and the result against Helios2008 is showed as Table 2.

Table 1. Passing success rate Confronting with Helios2008

Table 2. The result of Confronting with Helios2008

4.3 Conclusion

The data above which improves the success rate of passing and score when confronting Helios2008 shows that the ideal result of passing ball has been obtained by using Markov process to describe the problem of intelligent passing. However, it is of empirical formula that we divide the stadium. We are looking forward to finding out a more suitable method so that we could abstract the stadium to number of Markov source more effectively and theoretically. We will try our best to dealing with more issue of the RoboCup Simulation 2D and the research of Multi-Agent System by using the Information Theory in the coming time.

References

1. Thomas M.Cover, Joy A.Thomas.: Elements of Information Theory[M]. A John Wiley & Sons, INC PUBLICATION, 2006
2. Tom M. Mitchell.: Machine Learning[M]. Beijing:China Machine Press, 2003
3. KeShi.: The Agent Decision Research based on the Theory of Markov Decision[J]. University of Science and Technology of China, 2010.05
4. Long Li.: Learning Based on Axiology and its Application in RoboCup2D Simulation[J]. HeiFei University of Technology, 2009.5
5. BaoFu Fang, Hao Wang.: The Technology of Robot Soccer[M]. HeiFei University of Technology
6. Hidehisa A., Itsuki Noda.: Multi-agent positioning mechanism in the dynamic environment[A]. RoboCup 2007: Robot Soccer World Cup XI pp. 377-384 ,2008
7. AijunBai, Haochong Zhang, Guanghui Lu, Miao Jiang and Xiaoping Chen.: WrightEagle 2D Soccer SimulationTeam Description 2012[OL]. University of Science and Technology of China,2012
8. Jiang Dawei, Wang Shiyuan: Using the Simulated Annealing Algorithm for Multiagent Decision Making[A]. RoboCup 2006: Robot Soccer World Cup X pp.110-121, 2007
9. Stuart R., Peter N.: Artificial Intelligence))a modern Approach[M]. Beijing, Posts & Telecom Press, 2004
10. Peter S. and Manuela V.: Team-Partitioned, Opaque-Transition Reinforcement Learning[A]. In M. Asada and H. Kitano, editors, RoboCup-98:Robot Soccer World Cup II. Springer Buch Verlag, 1998.
11. Weiss G.: Multi-agent systems: A modem approach to distributed artificial intelligence[M]. The MIT Press§Cambridge§MA§1999:11-16
12. Stone P.: Layered Learning in Multi-Agent Systems[D]. Carnegie Mellon University,1998