Research Focus of SHU2002 Team

Xia Weifeng, Hu Qian

Department of Automation, Shanghai University, Shanghai, 200072, P.R. China

Abstract SHU2002 is a new team from Shanghai University focusing on high-level strategy, collaboration, and machine learning in Multi-Agent Systems for RoboCup simulation. The team's research focuses on supplementing the SBSP algorithm for dynamic formation control, implementing target-based communication protocols for improved efficiency, and applying machine learning techniques including ANFIS for offline learning and fuzzy classifier systems for online learning.

1. Introduction

Shu2002 is a new team built by several master student of Shanghai University .Due to the research interest in collaboration and machine learning in Multi-Agent System, we began our research on RoboCup simulation in may of 2001. We think that this dynamic, real-time and low bandwidth communication environment of RoboCup simulation provides us with a perfect experimental platform. It can examine whether the collaboration technique and machine learning theory could be well applied in such a Multi-Agent System.

Since the researches of low level technology such as agent architecture and individual skill have highly matured, in the past few sessions of competition, most teams designed their agent based on CMU. FCPortugal 2000 added the high level strategy algorithms such as SBSP (strategy Based situation Position) in the low level foundation of CMU, which got very good performance. We thought that the research of RoboCup simulation should be focused on high level strategy, so we did not emphasize on the low level technology. We design our agent architecture based on the simplified edition that FCPortugal distributed , FCPAgent, so that a large quantity of detailed work on low level skill had been saved, which enabled us to focus the research on the collaboration and machine learning of MAS.

Since we missed the time for register, we did not attend the competition of RoboCup 2001 in Seattle, but we attended the competition of Chinese RoboCup2001 organized by Chinese RoboCup committee soon afterward. TsinghuaAeolus ( champion in Seattle) and USTC WrightEalge (the 5th place in Seattle) also attended this competition. We defeated almost all the other teams except TsinghuaAeolus and USTC WrightEalge, and finally we won the 3rd place in this nationwide competition. We want to become the 3rd Chinese team that arises in international RoboCup competition.

2. Our Research Work in collaboration

Owing to the properties such as dynamic, uncertainty and real time of the field of soccer, entire intelligent group is required to handle such complex environment.The key is to have very flexible coordination and communication. Our work mainly includes two parts: one is the supplement for SBSP algorithm; the other is the establishment of target based communication protocol to improve the efficiency of communication.

2.1 Supplement of SBSP Algorithm

In the simplified edition of FCPAgent by FCPortugal, only simple and partial SBSP algorithms were gave. However, through the real test, we found that SBSP algorithm was also very effective even if it was not complete. Therefore, we decided to replenish SBSP according to its thought.

We have defined a basic position (X, Y) in each type of formation for every agent, while we have defined its role feature, mainly including Ball_Attraction, Admissible_Region, Behind_Ball_Interval, Offside_Interval, and Point_Attration etc., Different player has different parameter of role feature. At every moment, agent first gets its own basic position according to the current type of formation and its own role, then calculates the dynamic position according to its own feature parameter. Since feature parameters and basic positions of other roles are transparent to every agent in the formation, it can also calculate the dynamic positions of its teammates through the same formation, so as to estimate its position under the condition that a certain teammate cannot be observed, and all the movements of the player are based on this dynamic position. Every player is only responsible for the tasks nearby. At every moment that incident occurs (for example, blocking the opponent's ball), if it comes to a conclusion that its teammate can reach the target point sooner than itself through calculation, it will stay at its own dynamic position, and leaves the task to let other teammate handle, thus the overlapping of task is avoided.

Experiments show that, the enforcement of SBSP algorithm can make the entire formation dynamically change along with the movements of the ball and the varying tends of the situation. The forwards and midfielders will approach the opponent's half-field when attacking, while they can retreat rapidly when defending, able to keep constant encircling of the ball while it guarantees that the movements of all the team members can primarily cover the entire field, in order to prevent arising big leak of defense.

2.2 Target based Communication Protocol

In the past, the content of communication was generally included the environment state of every agent, so that in many time the message received by teammates could be much similar. Thus, the question that how to raise the efficiency of communication appeared. Additionally, in the environment model of agent, some message is accurate while some is inaccurate. So some measure should be adopted to ensure that communication content contains accurate message as much as possible.

To solve above problem, we have added some improvements on former RoboCup communication protocol, putting forward the way of target based communication protocol . Every time agent sends out a message, it will produce a target set according to the situation on site, then evaluate priority of its own environment message based on the target object, and select the message which is highly accurate and useful to target object to send out. When receiving information, agent will judge whether itself is included in the receiving target set according to the team mark and target set. If not, it won't analyze this message.

When applying the above improvements to the communication between the team members, we find that agent can receive much more accurate message and the communication is much more effective than ever before.

3. Our Research Work in Machine Learning

Machine learning is our another focus of research. Owing to the complexity of environment, it is important and difficult to establish accurate strategy modular. Usually, there are two general methods. One is to take advantage of the human's knowledge to establish complete reasoning system in the strategy modular; the other is to make use of machine learning method to enable the robot to establish strategy automatically. Due to the dynamic and noisy RoboCup environment, it is impossible for us to determine all the states of the match in advance. So establishing the mapped relation between environment state and movement space by using human's knowledge is far from possible. Therefore the machine learning method seems more feasible and important.

3.1 Offline Learning with ANFIS

when we solve pass line problems, we must consider many relate thing so that the state space will be huge. Peter Stone used the trained Decision Tree to evaluate pass line, but after tests we found the short of Decision Tree algorithm is its tree like logic structure can hardly describe highly non-linear property and its training scene can't cover the whole.

There are many pass experiences in human soccer match , for instance, the success rate will be low if the pass distance is too long, etc. So we think of using fuzzy technology to utilize the human knowledge effectively. Fuzzy inference system has been successfully used in many decision making and controlling field as a powerful tools to deal with highly non-linear and uncertain complex system. But fuzzy system has big limitation that the fuzzy rules cannot change along with the environment,it is short of the ability of self-learning . So we use the ANFIS (Adaptive Neuro-Fuzzy Inference System) to evaluate the pass problem, the fuzzy rules can be adjusted automatically by the learning function of Neuro Network.

We only consider several major factors such as distance, the congestion of target spot and pass line. According to experts' experience, we initiate the membership function and the weight of ANFIS . Training data is got through real match, each pass records the above factors' real data and its success or not. The adjustment of fuzzy rules is using the method of supervise learning. We use BP algorithm to adjust the membership function and the weight of FIS consequent, to make the ANFIS to approach the map relation between pass factors and the pass success rate.

To test the performance of ANFIS, we used the trained ANFIS to do pass decision in real match. Every time, the ball will be passed to the one whose success rate calculated by ANFIS is highest. The success rate is over 70 percent on the whole tested by thousands sample .

3.2 Online Learning

In RoboCup, online learning means agent learn during the match, and the general method includes reinforce learning and Genetic Algorithm. In PaSo-Team ' 98, F. Montrsello and E. Pagello applied the Classifier System based on GA to the online learning system successfully, which we think a very good trial.

After our experiment ,we found there is a problem of the using Classifier System. When the Classifier separate the environment state, generally we use ordinary discrete method. Because the state space of RoboCup simulation environment is huge, the number of state will be excessive if finely divided, while the requirement of precision is hard to be satisfied if roughly divided. And it also produce state leap when adopting simple discrete method. That is to say, state changes greatly while state takes place tiny changes. Owing to the successful experience of using fuzzy technology in above offline learning, we think fuzzy may also work in online learning.

We build arbitration module by learning fuzzy Classifier System. The environment state is defined with fuzzy linguistic variable in order to decrease the dimension of stare space. Every cycle, the priority of each movement module is evaluated, selected and judged by fuzzy inference. Using the machine learning method based on genetic algorithm, various fuzzy classifier rules generates automatically from dynamical environmental information. Through online learning, the fuzzy rules is automatically optimized. In FCS, we also adopted reinforce learning to select trigger message among the disorder environment message.

Through the verification by the real match, the agent with FCS arbitration can automatically adjust and optimize the way of arbitrating according to the situation and the reinforce message of movement effect.

4. Conclusion and Prospect

On the basis of adopting the mature low level technology, we focus our research on the collaboration and machine learning algorithm of agent. When attending the competition of China RoboCup2001, we have applied partial research to Team SHU2001, and got the third place only next to TsinghuaAeolus and USTC WrightEalge, which shows fully that our research really works.

Since we are a new comer in the field of RoboCup, there are lots of insufficiency in our research. What is comparatively obvious is that fuzzy inference requires a large quantity of calculation, while the requirement of real time must be considered in strategy and online learning, so the method we adopt should not be very complex and cannot take much time. Therefore our fuzzy rules are comparatively simple. Requirement of precision is hard to fill at some calculation.

Our recent plan aims at the above insufficiency. Better algorithm will be used to raise the efficiency of fuzzy operation so as to reach better effect. If time permits, we will also improve the low level technology to make our team have better effect in real match.