Ziziphus Team Description Paper RoboCup2016

Mohsen Sadeghi Pour, Azin Ghasemi, Kamyar Kalajooyeranjbar, Khashayar Kalajooyeranjbar, Mohammad Chaposhloo, Mohsen Firoozbakht

Department of Computer Engineering, Islamic Azad University, South Tehran Branch, Tehran, Iran; Shahid Beheshti University, Tehran, Iran

Abstract Ziziphus Soccer 2D Simulation Team was established in 2013 by Computer Engineering Department of Islamic Azad University of South Tehran, Iran. We participated in RoboCup2015 competition. Our main idea was to propose a method for modeling the playground in multi agent systems and collect data for skills. However, this year, we changed formerly matrix modeling to concentric circles modeling and decision prediction methodology is used to choose most suitable victory region for the agent to act. Here, the data are stored in Decision History Table for every situation of the agent and validity of previous selected victory regions.

1 Introduction

Ziziphus Soccer 2D Simulation Team was established in 2013 by Computer Engineering Department of Islamic Azad University of South Tehran, Iran. Until RoboCup2014, we participated in several competitions namely, IranOpen and SharifCup in Iran. Furthermore, we could add our first international experience into our record by participated in RoboCup2015, Hefei, China. The team's aim is to refurbish and improve the Agent2D3.1.1-based strategy [1].

This paper is presenting an improved method for an opponent's gameplay learning method using the Branch Prediction [2] and Reinforcement Learning [3] ideas in multi agent system. Here, Matrix model is changed to concentric circles model. Section 2 describes the concentric circles modeling to store data for skills and section 3 describes a method to predict decision. Eventually, conclusion and future work are followed in section 4.

2 Modeling Area Using Concentric Circles

Concentric Circles Model (CCM) is an improvement to the previously used Matrix Modeling [4]. CCM is used to model the area around each player with some sectors instead of matrix's cells. Formerly, we modeled the area around each player by a unique square matrix (Fig. 1. B). However, in CCM the player is in the center of these circles (Fig. 1. A) and each sector of the CCM indicates a relative coordinate to the player in playground. Similar to square matrix, CCM is also contains the results of a Bernoulli Test [5]. Each question is a description of a skill. CCM provides several advantages over the previous strategy including, high precision information on the agent's near surround and information with lower precision on far surround and easy to analyze points with same distance, as it uses Polar coordinates instead of Cartesian coordinates.

3 Decision Prediction

The main idea of decision prediction is originated from Reinforcement Learning and Branch Prediction using BHT$^1$. In computer architecture, BHT can have Numbers of Bits to analyze previous conditions and results in order to predict and decide. i.e. Should current state have a branch or not?

In decision prediction, CCMs and our decision for each situation are stored at Decision History Table (DHT). Analysis of situation is based on the validity of decisions with previous similar situations which are found in DHT.

Decision means filling the CCM, finding victory region on it and selecting a victory region for doing action.

$^1$ Branch History Table

3.1 DHT Structure

DHT stores information about every situation of the agent and validity of victory regions. DHT structure contains four major parts including

• CCM Status; set of values for each CCM's sector.
• Agent2D Normal-Formation Triangulation; dividing play ground to triangles as shown in Fig. 2.
• Selected Region; the agent acts based on the victory region.
• Validity; consequence of victory or failure that depends on our action based on the Selected Region.

3.2 Decision Validator

Decision validator is a method to determine our decision consequences victory or failure in the next cycles.

Dribble. The decision is valid, if the agent would be still possessing the ball (ball is in the agent's kickable area) until reaching the decision's goal and making next decision.

Pass. The opponent couldn't be kickable before a teammate possess the ball.

Mark & Block. Previously, to mark & block an opponent, the player should had been in a position to make the largest victory region which contained opponent's lines (the lines between the opponent with ball and other opponents around it) and goal's lines (the lines between the opponent with ball and our goal posts). In current methodology, we have adopted some changes in blocking and marking. In blocking, the nearest agent in front of the kickable opponent will approach the selected position [4] for blocking, if the agent's act results in a failure (means kickable opponent do a successful dribble), it means the decision that was made is invalid and in future situations one more agent will assist in blocking process. In Marking, the nearest agent to the kickable opponent will approach to the selected position [4] for marking, if the agent's act results in a failure (means kickable opponent do a successful pass to marked opponent) its means the decision that was made is invalid.

3.3 Method of Finding Similar Situations

To find a similar situation in the triangle region where the agent is present, a CCM must be compared with existing templates in the triangle and adjacent triangles to find the most common matching templates. For this reason, we used an Optical Character Recognition (OCR) Matching Algorithm, because of the Sectored CCM is similar to a Matrix and OCR algorithms convert a picture of characters to a high contrast bitmap [7].

Normalized Correlation in Template Matching Algorithm [8] is used to find most matching CCM template with current CCM.

$$S(I,Tn) = \frac{\sum_{i=0}^{h} \sum_{j=0}^{w} (I(i,j) - |I|) (Tn(i,j) - |Tn|)}{\sqrt{\sum_{i=0}^{h} \sum_{j=0}^{w} (I(i,j) - |I|)^{2}} \sqrt{\sum_{i=0}^{h} \sum_{j=0}^{w} (Tn(i,j) - |Tn|)^{2}}}$$

In the above equation, h denotes numbers of circle level and w is numbers of sectors in each circle level, if I(x, y) is the input CCM and Tn(x, y) is the template CCM n, then the matching function S(I, Tn) will return a value indicating how well template n matches the input.

4 Conclusion and Future Work

This paper presents a method to predict decisions based on opponent's behavior. Ziziphus team, with its unique approach have every reason to be a competitive team in RoboCup2016 and achieve high-ranking position in this competition.

For future perspective, the proposed method can be extended by developing an ability for the agent to imagine oneself other agent's situation and plan the decisions with multiple steps.

References

1. Akiyama, H.: Agent2D Soccer Simulation 2D Base Source code and Documentation. http://en.osdn.jp/projects/rctools/releases/p4887
2. Hennessy, John L., Patterson, David A.: Computer Architecture: A Quantitative Approach. Fourth Edition. 82 (2007).
3. Abdallah, S.: A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamics, Journal of Artificial Intelligence Research. 33 (2008) 521-549. https://www.jair.org/media/2628/live-2628-4198jair.pdf
4. Sadeghi Pour, M., Ghasmei, A., Firoozbakht, M.: Ziziphus Temp Description Paper. The 18th annual RoboCup International Symposium, China, Hefei (2015).
5. Neapolitan, R., Naimipour, K.: Introduction to Algorithms. (2001)
6. Akiyama, H., Fedit2.: http://rctools.osdn.jp/pukiwiki/index.php?fedit2
7. Li, N.: An Implementation of OCR System Based on Skeleton Matching. Computing Laboratory University of Kent at Canterbury, United Kingdom. (1991).
8. Muda, N., Nik Ismail, Nik K., Abu Bakar, Siti A.: Optical Character Recognition by Using Template Matching (Alphabet). University Malaysia Pahang. (2007). http://umpir.ump.edu.my/969/1/NaCSES-2007- 086_Optical_Character_Recognition_By_Using_Templ.pdf