KylinSky3D Soccer Simulation Team Description for RoboCup2013

Chaohong Cai, Hong Jiang

Robot Lab, Hohai University Wentian College, Maanshan City, Anhui Province, China; Computer and Information College, Hohai University, Nanjing City, Jiangsu Province, China

Abstract The purpose of this paper is to describe the main features of the KylinSky2013 3D soccer simulation team. We model the robot as a 3D-LIPM, which simultaneously planning ZMP and CoG trajectory, and ZMP trajectory is represented by a cubic polynomial. We carried out with a cumulated and layered optimization method based on covariance matrix adaption evolution strategy is proposed to optimize bipedal walk. We also demonstrated some basic modules, such as agent architecture, world model and team coordination. Finally we summarized the research to review current and future works in the last part.

Keywords: Soccer simulation, Walking gait, Inverted pendulum, CMA-ES, Team coordination

Introduction

Robot soccer is a great challenge to researchers, because the environment is full of dynamics and non-deterministic. To play a good game in 3D soccer simulation, there are several works must be done. In the first place, a real time and dynamic balanced bipedal walking gait is critical to agent; from the last year, the standard game play is 11vs11, this means team strategy will play a very important role in the game, and a robust coordination strategy would enhance the level of whole team greatly; besides that, agent skills are not trivial due to drive ball to goal by one agent directly becoming more and more difficulty. According to these aspects, we have done a lot of research works about walking gait planning and optimization, team coordination strategy and single agent skills.

In order to obtain a robust walking gait, we have built a new walking engine based on 3D-LIPM(3D Linear Inverted Pendulum Model)[12] and our former gait planning method[3]. During single foot supporting phase, the dynamics of robot can be represented by a single inverted pendulum which connects the supporting foot and the center of mass of the whole robot. The model uses limited knowledge of dynamics, such as the location of total center of mass, total angular momentum and so on. For the trajectory of swing foot, we utilized the theory of synthesized sinusoids [1], and ZMP(Zero Movement Point)[7] trajectory was designed by a cubic polynomial.

A stable and flexible bipedal walk is often the key to the humanoid robot to complete the task smoothly and quickly. In order to learn such walking gait by machine learning method, a cumulated and layered optimization method based on CMA-ES(Covariance Matrix Adaption Evolution Strategy)[8] is proposed. In the learning process, learning task is divided into several critical layers from simple to complex, the fitness function of each layer is decided by each layer's learning target, the result of previous layer is the basis of current learning layer, and thus the learned results are accumulated from layer to layer, by then the learning task is completed finally. According to this method, robot learned an effective and flexible bipedal walk.

Since the ultimate goal is to play a game with 22 agents, we adopted some approaches of team coordination. Due to the restricted vision of agent, the formation which decided by each agent maybe different, we designed a communication protocol to ensure a consistent formation in each teammate. Some fundamental works have also been done, which include: expanding the world model; and debugging some offline motions, for instance, pass ball and kick ball motion.

The remainder of the paper is organized as follows. Section 2 briefly described agent architecture. The world model of agent is illustrated in section 3. Section 4 discussed the walking gait planning method and optimization strategy. Section 5 depicted some details about team collaboration. In the last section, we draw conclusions and present directions for future work.

Agent Architecture

We designed the agent architecture based on mixed partition method[5]. The overall structure of our program consists of three layers: connection layer, technique layer, and controlling layer. The function of connection layer is keeping a network connection between agent and simulation server. Technique layer is divided into four parts, which contains Basic parser, World model, Basic motions and Actor. The controlling layer is made up of Agent and Strategy, in which the Agent part contains the internal state of robot, Strategy part accounts for role assignment, formation updating and so on. The agent architecture of our team is displayed in Fig.1.

World Model

World Model includes perceptual information of agent, exact actions of agent need well-handled perceptual information. These direct information are not sufficient for agent strategy, hence we must do some reasoning works or extract enough potential information from perceptual messages, World Model aims at this subject. The content of World Model contains static and dynamic information of game, states of field, particular messages of each agent, and predicted information for strategy[6][11].

We divided World Model into two modules: field state and agent state. Field state reflects states of the whole soccer field, including static and dynamic information. Static information is unchangeable, containing the size of field, coordinates of flags, specifications of server, etc. Dynamic information keep updating every cycle, comprising position and velocity of ball, positions of teammates, the current game state, etc. Agent state describes a state of agent, it also covers static and dynamic information. Parameters of robot model makes up static information, and joint angle, walking velocity and current strategy comprised the dynamic part of agent state. Fig.2 illustrates the structure of World Model.

Walking gait planning and optimization

A stable and flexible walking gait is critical, especially as the collaboration between teammates is becoming more and more important. Agents could finish tasks easily if they have a flexible walking gait. As a result of these factors, a new walking engine which is based on 3D-LIPM was built. In the walking engine, to maximize the range that can be passed within a single supporting phase, double supporting phase was ignored; the trajectory of swing foot was planned by synthesized sinusoids.

The coordinate system of our walking engine comprise two coordinate frames, the pendulum frame S and swing foot frame F. The coordinate frames allow step planning and leg control to be expressed in their natural frame of reference. This ensures that the system stays in manageable control because each component only acts on a limited amount of information anchored to its appropriate coordinate frame. The pendulum frame maintains the motion of center of mass, it is always offset by $s_{offset}$ towards the supporting foot, the motion of swing foot corresponds to swing foot frame. Fig.3 shows the coordinate system.

Walking pattern generation

3D-LIPM was proposed firstly by S.Kajita [12]. During the single supporting phase, the dynamics of robot can be represented by a single inverted pendulum which connects the supporting foot and the center of mass of the whole robot. The model simplifies computation and system control complexity due to its linear features, and the motion of CoG in sagittal plane and lateral plane can be planned separately. The following equations represent motion of CoG:

$$\ddot{x} = \frac{g}{z_c} (x - p_x)$$

$$\ddot{y} = \frac{g}{z_{\perp}} (y - p_{y})$$

where g is acceleration of gravity, $z_c$ is intersection of Z axis with horizontal plane, $p_x$ and $p_y$ is ZMP.

However, directly implementing this model on robot without any modification, robot will not walk stably, and even robot will fall down, the problem is caused by un-continuous walking primitives and point error of supporting foot [14]. ZMP based walking pattern is an appropriate choice which generating CoG trajectory by planning ZMP trajectory. We designed our walking pattern on NAO robot according to the method proposed in literature [16], which defines one step as two swing phases and one supporting phase. The trajectory of $p_x$ and $p_y$ is represented by cubic polynomial:

$$P_x(t) = \sum_{i=0}^{3} a_i t^i$$

$$P_{y}(t) = \sum_{i=0}^{3} b_{i} t^{i}$$

Then the analytical solution of equation (1) is:

$$\begin{bmatrix} X(t) \ \dot{X}(t) \end{bmatrix} = A(t) \begin{bmatrix} x^{s} \ \dot{x}^{s} \end{bmatrix} + [I - A(t)]C_{x} + B_{x}(t)$$

where

$$A(t) = \begin{bmatrix} \cosh(qt) & \frac{1}{q}\sinh(qt) \ q\sinh(qt) & \cosh(qt) \end{bmatrix}, q = \sqrt{\frac{g}{z_c}}$$

$$B_{x}(t) = \left[ \sum_{i=0}^{3} a_{i} t^{i} + 6 a_{3} t / q^{2} - a_{0} \right]$$

$$3 a_{3} t^{2} + 2 a_{2} t$$

$$C_{x} = \begin{bmatrix} a_{0} + 2a_{2} / q^{2} \ a_{1} + 6a_{3} / q^{2} \end{bmatrix}$$

Is the identity matrix, $x^s$ and $\dot{x}^s$ are initial position and velocity of CoG respectively. Similarly substitute equation (4) into (2) will get the analytical solution in Y axis. The unknown coefficients of equation (3) and (4) can be calculated by constraint conditions of motion, and then the trajectory of ZMP and CoG will be obtained.

The swing foot trajectory was designed by synthesized sinusoids. To avoid collisions when robot switch supporting foot, the velocity of swing foot should be zero at the moment of leaving and touching the ground. For the avoidance of jerkiness, the acceleration of these two moments should be zero too. Suppose the acceleration of swing foot is:

$$\dot{x}_r(t) = A\sin(\frac{2\pi}{T_c}t)$$

where A is the coefficient to be computed, $T_s$ is the cycle of single supporting phase. According to the restrict conditions, the trajectory of swing foot in the X axis direction is:

$$x_r(t) = \frac{D_s}{T_s}t - \frac{D_s}{2\pi}\sin(\frac{2\pi}{T_s}t)$$

where $0 \le t \le T_s$ , $D_s$ is the step length of one step. The planning method in other axis is similar.

Walking gait optimization

We proposed a learning architecture based on CMA-ES to learn a stable and flexible walking gait. CMA-ES is a policy search algorithm, it keeps updating distribution of population according to the parameters of individuals of each generation, and finally converge to an optimal solution.

Considering the number of parameters of walking pattern is over 30, optimize all of these parameters is un-necessary, we selected 9 critical parameters by the following index: 1) ZMP should always be in supporting polygon; 2) walking gait should be responding to top level command quickly; 3) agent should be walking to the target point smoothly and effectively.

In the learning process, learning task is divided into several critical layers from simple to complex, the fitness function of each layer is decided by each layer's learning target. The result of previous layer is the basis of current learning layer, and thus the learned results are accumulated from layer to layer and the learning task is completed finally. Fig.4 depicts the learning architecture.

Ongoing Research

The inverted pendulum controls the motion of center of mass by limited knowledge of dynamics, since the controller knows little about the system structure, a stable walk more likely relies on a feedback control. An approach based on control theory has been proposed by Kajita et al. [13] in which the CoG is designed to converge at the end of previewing period. Due to the inner tracking error of the preview controller, the magnitude of the preview gain converge slowly[2]. In our ongoing research work, we will implement a feedback control algorithm, which compensates hip angle of robot according to torso angle[9] and adjusts the posture of robot by gyroscope readings[4][15].

Except the control theory method, reinforcement learning can serve as an alternative method. Reinforcement learning is a learning algorithm that mimics the human learning procedure form experience[10]. Thus, the parameter selection problem will be solved by learning while it is hard for hand tuning method, and the optimal walking gait can be learned by this approach. In our future research, we will optimize the walking gait by reinforcement learning.

Team Coordination

Multi-agent domain aims at collaboration in an adversarial environment between agents. In 3D soccer simulation, the increasing number of agents form one team offers great challenge to research works.

During the game, each agent maintains a formation of the whole team. The position of ball and the state of game decides formation of the team, each role in formation is calculated by constant offset correspond to the position of ball. Because of the restricted vision, agents may maintain formation different form each other. We give each agent a specific time slice to communicate with each other, and in this way, each agent can share the formation with their teammates, and chose the formation with the most votes. Beside the formation, agent can broadcast its position and ball position to its teammates.

The further work is planned to design a more reasonable coordination system, especially improve the accuracy of role assignment algorithm, and develop an extensible team strategy with more pass ball actions.

Conclusion and Future Work

This paper introduced the main features and implementation of our team. The way we implemented the agent architecture, world model, walking gait planning and optimization method, team coordination were addressed. The walking gait planning method is based on inverted pendulum model, and combines the advantages of our previous gait planning approach. We optimized the walking pattern by a cumulated and layered learning architecture which is based on evolutionary algorithm.

In our future work, we will use reinforcement learning as an alternative method to optimize the walking gait. Reinforcement learning algorithm mimics the human learning procedure form experience, the algorithm can learn an optimal policy without ever being able to predict the effects of its actions, and it can solve a lot of problems caused by hand tuning method. Another important part of our future work is design an extensible and flexible coordination strategy. Currently, our team coordination strategy is mostly based on single agent's evaluation, a coordination model relies on a single agent's and the whole team's evaluation will be our further plan.

References

1. Deng Xin: Stable walking gait of biped walking robot. Master's thesis, Haerbin University of Engineering, 2007
2. Feng Xue, Xiaoping Chen, JinsuLiu and Daniele Nardi: Real Time Biped Walking Gait Pattern Generator for a Real Robot. RoboCup Symposium 2011, Istanbul, 2011.
3. Hong Jiang, Chaohong Cai: KylinSky3D Soccer Simulation Team Description for RoboCup 2011. In RoboCup 2011, Istanbul (Turkey), July, 2011.
4. Jacky Baltes, Sara McGrath and John Anderson. The Use of Gyroscope Feedback in the Control of the Walking Gaits for a small Humanoid Robot. Springer-Verlag Berlin Heidelberh, pp.628-635, 2005.
5. Jiang Chunlu: A research of agent's basic motions based on RoboCup3D simulation. Bachelor's thesis, Southeast University, 2006.
6. Liu Rujia, Sun Zengqi: The maintenance of world model for RoboCup3D simulation. Thesis Collection of China Soccer Robot Game, 2005:21-25.
7. M. Vukobratovic, "Zero-Moment Point: Thirty Five Years of Its Life," International Journal of Humanoid Robotics, Vol. 1, No. 1, pp.157-173, 2004.
8. N. Hansen. The CMA Evolution Strategy: A Tutorial[EB/OL]. http://www.lri.fr/~hansen/cmatutorial.pdf. 2012, May.
9. Odest Chadwicke Jenkins, Pawel Wrotek and Morgan McGuire. Dynamic Humanoid Balance through Inertial Control. IEEE-RAS International Conference on Humanoid Robots, Nov. 29, 2007.
10. Richard S. Sutton and Andrew G. Barto: Reinforcement Learning: An Introduction. The MIT Press, 1998.
11. Song Beibei: World model design for RoboCup3D simulation. Master's thesis, Hefei University of Industry, 2007.
12. Shuuji Kajita, Fumio Kanehiro, Kenji Kaneko, Kazuhito Yokoi and Hirohisa: The 3D Linear Inverted Pendulum Model: A simple modeling for a biped walking pattern generation. Proc. of the 2001 IEEE/RSJ, Hawaii, USA, Oct. 29-Nov. 03, 2001.
13. Shuuji Kajita, Fumio Kanehiro, Kenji Kaneko, Kiyoshi Fujiwara, Kensuke Harada, Kazuhito Yokoi and Hirohisa Hirukawa: Biped Walking Pattern Generation by using Preview Control of Zero-Moment Point. Proc. of the 2003 IEEE International Conference on Robotics and Automation, Taipei, Taiwan, September, pp.14-19, 2003.
14. Shuuji Kajita. Humanoid Robots[M]. Beijing: Tsinghua University Press, 2007.
15. Takahiko Sato, Hisashi Ono and Kouhei Ohnishi. Gyroscope Integrated Environmental Mode Compliance Control for Biped Robot. The 12th IEEE International Workshop on Advanced Motion Control, March 25-27, 2012.
16. Xue Feng. Biped Locomotion Control of Humanoid Robot in Indoor Environment[D]. University of Science and Technology of China, 2012.