FC Portugal 3D Simulation Team: Team Description Paper

Nuno Lau, Luís Paulo Reis, Bruno Pimentel, Nima Shafii

DETI/UA – Electronics, Telecommunications and Informatics Dep., University of Aveiro, Portugal; DEI/FEUP – Informatics Engineering Department, Faculty of Engineering, Univ. of Porto, Portugal; IEETA – Institute of Electronics and Telematics Engineering of Aveiro, Portugal; LIACC – Artificial Intelligence and Computer Science Lab., University of Porto, Portugal

http://www.ieeta.pt/robocup/

Abstract FC Portugal 3D team is built upon the structure of our previous Simulation league 3D teams. Our research is mainly focused on the adaptation of previously developed methodologies from our 2D soccer teams [1, 2, 3, 4, 5] to the 3D humanoid environment and on creating new coordination methodologies based on the previously developed ones. In our 2D teams, which participated in RoboCup since 2000 with very good results, we have introduced several concepts and algorithms covering a broad spectrum of the soccer simulation research challenges. From coordination techniques such as Tactics, Formations, Dynamic Positioning and Role Exchange, Situation Based Strategic Positioning and Intelligent Perception to Optimization based low-level skills, Visual Debugging and Coaching, the number of research aspects FC Portugal has been working on is quite extensive [1, 2, 3, 4, 5]. The research-oriented development of our team has been pushing it to be one of the most competitive over the years (World champion in 2000 and Coach Champion in 2002, European champion in 2000 and 2001, Coach 2nd place in 2003 and 2004, European champion in Rescue Simulation and Simulation 3D in 2006, World Champion in Simulation 3D in Bremen 2006 and European champion in 2007). This paper describes some of the main innovations of our 3D simulation league team relating them with previous work developed by simulated RoboCup teams in 2D and 3D simulation leagues. New skills have been developed for the simulated humanoid agent which include an omnidirectional walk, and flexible kick. It also includes information related to the agent architecture and low-level considerations. The current research is focused on improving these skills by developing a generic skills optimization framework, building robust mid-level skills and integrating high-level coordination mechanisms.

1. Introduction

FC Portugal was built upon the low-level skills research conducted during previous years. Although there is still space for improvement in FC Portugal low-level skills, we feel that we currently have a very performing set of these skills. We are currently focused on the high-level decision and cooperation mechanisms of our agents. The skills have been developed using several different techniques (hill climbing, genetic algorithms, population swarm optimization).

For RoboCup 3D soccer simulation competition that was based on spheres (from 2004 to 2006), the decisive factor (like in the 2D competition) was the high-level reasoning capacities of the players and not their low-level skills. Thus we worked mainly on high-level coordination methodologies for our previous teams.

Since 2007 humanoid agents have been introduced and teams consist of only a few agents, research in coordination has not been very important in the 3D league. Developing efficient low-level skills, contrarily to what should be the research focus of the simulation league, has been the main decisive factor in the 3D league. This year the number of agents will increase significantly and cooperation issues will again be very important for the efficiency of the team.

Several interesting topics are opened by the introduction of humanoid agents, including in the use of learning and optimization techniques for developing efficient low-level skills. In previous work, we have introduced methods for developing very efficient low-level skills using optimization techniques [1, 6]. This work has already conducted to the development of an efficient set of humanoid walking and kicking skills.

2. Research Directions

New research directions include research on agent architecture, the humanoid model and its associated restrictions in terms of dynamics, sensing, and decision, will foster the development of new layered architectures for its controlling agents. The lower layers will be responsible for the basic control of the humanoid such as equilibrium while the higher layers take decisions at a strategic level. Several methods for generation of humanoid behaviors are being compared, including simulated annealing, Tabu search, genetic algorithms, particle swarm optimization and reinforcement learning and how these behaviors are integrated together.

Some directions of research in FC Portugal also include developing a model for a strategy for a humanoid game and the integration of humanoids coming from different teams in a inter-team framework to allow the formation of a team with different humanoids.

Opponent modelling may be a critical module in humanoid soccer, including the opponent basic behaviors performance, its positioning, etc. are factors that must be taken into account when selecting a given strategy for a game.

Other research with humanoids includes intelligent sensing, because the humanoids cannot look in all directions at the same time. So, it is very important to choose the best looking direction considering all restrictions introduced by the dynamics of humanoid movement.

Also heterogeneity will be important because in the future it is expected that not all humanoids will be identical, having humanoids with different capabilities introduces new problems of task assignment that will have to be dealt within humanoid teams.

3. FCPortugal 3D Agent Architecture

The FC Portugal Agent 3D [7] is divided in several packages: each one with a specific purpose. Figure 1 shows the general structure of the humanoid agent.

• WorldState: Contains classes to keep track of the environment information. These include the objects presented in the field (fixed objects as is the case of flags and goals and mobile objects as is the case of the players and the ball), the game state, (e.g. time, playmode) and game conditions (e.g. field length, goals length);

• AgentModel: Contains a set of classes responsible for the agent model information. This includes the body structure (body objects such as joints, body parts and perceptors), the kinematics interface, the joint low-level control and trajectory planning modules;
• Geometry: Contains useful classes to define geometry entities as is the case of points, lines, vectors, circles, rects, polygons and other mathematical functions;
• Optimization: Contains a set of classes used for the optimization process. These classes are a set of evaluators that know how each behavior should be optimized;
• Skills: This package is associated with the reactive skills and talent skills of the agent. Reactive skills include the base behaviors as is the case of walk in different directions, turn, get up, kick the ball and catch the ball. Talent skills are some powerful think capabilities of the agent, which include movement prediction of mobile objects in the field and obstacle avoider;
• Utils: This package is related with useful classes that allow the agent to work. This includes classes for allowing the communication between the agent and the server, communication between agents, parsers and debuggers.
• Strategy: Contains all the high-level functions of the agent. The package is very similar to the team strategy packages used for other RoboCup leagues.

4. Agent Model

The agent model is constructed by reading a XML file that contains the body structure. This file is defines the body parts, the joints and the perceptors and the corresponding positions related to each other. The following represents an excerpt of the configuration file that is currently being used:

<robot type="humanoid" rsgfile="nao/nao.rsg"> 
 <bodypart name="torso" mass="1.2171" /> 
 <bodypart name="lhip1" mass="0.09" /> 
 <bodypart name="rhip1" mass="0.09" /> 
 ... 
 <joint name="lleg2" per="llj2" eff="lle2"

axis="0,1,0" min="-25" max="45">

This information stores the body structure information of the humanoid. Several important parameters are derived from this information as, for example, the direct kinematics transformation matrices and useful measures as is the case of the center of mass, which is used to ensure more stability on each generated behavior. This strategy keeps the code more generic and independent of the model, allowing for an easy integration of different models using the same code, which may allow the future integration of heterogeneous robots.

5. Bipedal Walking

The FC Portugal team has recently integrated Nima Shafii that had previously been the leader and principal developer of the Simulation 3D MRL team. Nima has continued his previous work on the development of low-level skills using optimization and learning methodologies [8]. These skills will be used in our 2010 team. The following sections detail the work that has been performed in order to develop an efficient and robust bipedal walk skill that leads to the currently functional omnidirectional walk of our humanoid

5.1 Movements in Sagittal

Trunk sagittal and coronal plane motion are fairly repeatable [9] therefore Fourier series can be used to model the trajectory of the joints in these planes. In our approach, According to [10] legs joint angular trajectories in sagittal plane are divided in two parts; the upper portion and the lower portion. The trajectories for both legs are identical in shape but are shifted in time relative to each other by half of the walking period. The Truncated Fourier Series (TFS) for generating each portion of hip and knee trajectories are formulated below.

$$\theta_{h}^{+} = \sum_{i=1}^{n} A_{i} \cdot \sin(iw_{h}t) + c_{h}, w_{h} = \frac{2\pi}{T_{h}}$$

$$\theta_{h}^{-} = \sum_{i=1}^{n} B_{i} \cdot \sin(iw_{h}t) + c_{h}, w_{h} = \frac{2\pi}{T_{h}}$$

$$\theta_{k}^{+} = \sum_{i=1}^{n} C_{i} \cdot \sin(iw_{k}t) + c_{k}, w_{k} = w_{h}$$

$$\theta_{k}^{-} = c_{k} \ge 0$$ (1)

In these equations, the plus (+) sign represents the upper portion of walking trajectory and the minus (-) shows the lower portion. i=1 and $A_i$, $B_i$, $C_i$ are constant coefficients for generating signals. The h and k subscripts stands for hip and knee respectively. $C_h$, $C_k$ are signal offsets and $T_h$ is assumed as the period of hip trajectory. Considering the fact that all joints in walking motion have equal movement frequency and stride rates is statistically equal, the equation $w_k = w_k = \frac{2\pi}{T}$ can be concluded.

Parameter $t_1$ is the start time of lock phase for knee joint and parameter $t_2$ represents the end time of lock phase and in this duration of time $\theta_k^- = c_k \ge 0$ .

According to [11], by specifying the start and end time of the lock phase, two parameters of $t_1$ , $t_2$ could be eliminated. Therefore the number of variable for optimization to produce legs movement in sagittal plane decreased to 6.

In sagittal plane, during human walking, the arms normally swing in opposite manner to legs, which helps to balance the angular momentum generated in the lower body [12]. Trajectory of arms is similar to sinusoidal signal with same frequency of legs [12]. Humans swing their arms close to 180° out of phase with their respective legs during walking [13].

It can be expected that the utilization of arm swing provides good performance to yaw moment stability, and recovery from stumbling. The effectiveness of this method is confirmed with an improvement of the accuracy of straight walking at different speeds. According to [14], the trajectory of arms is a sinusoidal signal; therefore, to produce proper angular trajectories to arms swing, it is enough to obtain proper parameters for the following equation (2).

$$f(t) = A \sin(\omega_{mn} t), \omega_{mn} = \omega_{mn}$$ (2)

In the above equation, A and $\omega$ are assumed as the amplitude and frequency of the signal, respectively. Since legs and arms have the same frequency, $\omega_{arms}$ can be considered equal to $\omega_{legs}$ . According to mentioned equation only the proper value of parameter A must be obtained.

According to [14], increasing the walking speed and amplitude from standing to running the robot can walk more stable and faster. We implemented a model for the robot to walk from smaller gait with lower amplitude to bigger gait with higher speed and acceleration. In this model a linear equation is used to lead the robot to increase the amplitude of trajectory linearly form zero (stop state) to desired angular trajectories. T is assumed as a parameter to determine how much time is needed for this increment algorithm to reach these desired trajectories. All angular trajectories such as arms and legs will be multiplied by the product of the following equation.

$$K = tim e / T$$ , $tim e < T$
$K = 1$ , $tim e >= T$ (3)

5.2 Movements in Coronal

The range of motion in the coronal and transverse plane is less than that is seen in the sagittal plane [15] but it has an important role to keep the balance of walking and reach the highest speed of walking. The range of its motion depends on the speed of walking at higher speeds this range is smaller. Coronal plane movements are periodic motions [9]. Abduction and adduction are terms for movements of limbs relative to the coronal plane.

To produce legs' motion in coronal plane and also considering keeping the balance of robot, we proposed a walking sequences and scenario (Fig. 2). It illustrates the walking sequences in a walking period. $\theta$ is assumed as the maximum of legs movement. Like in the previous section in coronal plane, feet were kept parallel to the ground in order to avoid collision and considering of the fact that just one of each hip's joint moves each time, the angle of ankle is equal to the hip's angle of the opposite leg.

According to the scenario in order to produce proper angular trajectories to move the hips in coronal plane, proper parameters for the following equation must be obtained (4).

$$f(t) = H \sin(wt), t < T_h / 2$$

$$f(t) = 0, t > T_h / 2$$ (4)

In the above equation, H and $\omega$ are assumed as amplitude and frequency of signal respectively and $T_h$ is assumed a period of hip. Ankle trajectories can be calculated from hip trajectories and as it is shown, left and right hip angular trajectories are the same but with a phase shift of -pi. The period of walking in sagittal plane and coronal plane is equal. Therefore $T_h$ and $\omega$ is eliminated in this method and for producing the proper abduction and adduction, the proper value of H parameter must be found.

In this approach the best parameters to generate angular trajectories for bipedal locomotion must be found. For this kind of optimization problem, Particle Swarm Optimization can achieve very good results [8]. Therefore PSO seems to be an appropriate solution.

6. Omnidirectional Ball-kicking using Inverse kinematics

An inverse kinematics multi-stage search methodology was developed in order to achieve an omnidirectional ball-kicking skill. In each stage of the search, the angle of one joint varies along its assignable range with short intervals. The kicking foot position is determined using forward kinematics and thus its distance to the target can be determined. The angles which result in the smallest distance are the ones which will be applied in the given joints. Because only some joints have influence on the position of the kicking foot, the search can be based on a short kinematic chain which is composed of relevant joints only.

The proposed approach can be very useful to dynamically outline body part trajectories. In particular, we have used it to develop our omnidirectional ball-kicking skill. When kicking a ball towards a target, three important parameters can be considered (see Fig. 3):

$dist_{KR}$ : the distance between the kicker and the ball;

• $\alpha$ : the angle between the kicker orientation and the relative direction of the ball,
• $\beta$ : the angle between the relative direction of the ball and the target direction relative to the ball.

In general, humanoid robots are still positioning themselves in line with the ball and the target, so as to be able to kick it properly. This corresponds to having $\alpha \approx \beta \approx 0^{\circ}$ . However, our method for flexible ball-kicking, i.e. for kicking the ball towards some particular target, does not require this (often long) preparation phase. The skill is composed of the following movements:

• 1. Transferring the robot weight to its left foot;
• 2. Slightly raising the robot's right foot;
• 3. Positioning the right foot near the ball;
• 4. Kicking the ball;
• 5. Bringing the right foot back to its original position.

The weight transfer, the right foot raise, and its later return can be achieved with simple predefined skills because they do not depend on the particular circumstances. On the other hand, positioning the foot "behind" the ball, and kicking it "forwards" can have different meanings, depending on the relative positions of the robot, the ball, and the target. One must dynamically determine which direction is "forwards" and "backwards" with respect to the kicking motion and the latter might not even be in line with the foot's initial position (see $\beta$ in Fig. B2).

The first step to determining the foot trajectory to follow during the actual kicking stage is to determine vector $\overrightarrow{BT}$ defined by the ball (B) and the target (T) positions: $\overrightarrow{BT} = T - B$ . The starting (I) and stopping (F) foot points for the kicking movement can then be calculated as follows:

$$I = B - a \frac{\overrightarrow{BT}}{|\overrightarrow{BT}|}$$ (5) and $F = B + b \frac{\overrightarrow{BT}}{|\overrightarrow{BT}|}$ (6)

in which a and b are coefficients that define how far behind and how far ahead of the current position of the ball the foot will start and stop during the kicking phase, respectively. After I and F are calculated, inverse kinematics can be applied to determine which joint angles should be used. If one focuses on movement planning for kicking with NAO's right foot, one can select its right hip, thigh and knee joints for getting the right foot to reach the positions calculated.

Experience has shown us that, in addition to foot positioning, foot orientation is essential, not only for kick accuracy but also for robot stability. When moving leg joints, careless foot orientation leads to unexpected positions of foot edges. In case the latter hit the ground (Fig. 4), the humanoid loses stability, possibly falling. Thus attention should be paid to keeping feet parallel to the ground. Our solution to this problem comprises some forward kinematics and trigonometry basics to calculate the angles which should be applied to NAO's ankle joints.

In addition to the methods described above, we are enhancing this omnidirectional kicking skill by adding dynamically adjustable foot orientation in order to kick the ball with a correctly oriented surface and thus achieve better accuracy. For this purpose, we will study the possibility of integrating a generic fitness function parameter into the inverse kinematic search.

7. High-Level Decisions and Coordination

Flexible Tactics has always been one of the major assets of FC Portugal teams. FC Portugal 3D is capable of using several different formations and for each formation players may be instantiated with different player types. The management of formations and player types is based on SBSP – Situation Based Strategic Positioning algorithm [1, 4]. Player's abandon their strategic positioning when they enter a critical behavior: Ball Possession or Ball Recovery. This enables the team to move in a quite smooth manner, keeping the field completely covered.

The high-level decision uses the infrastructure presented in the section 3. Several new types of actions are currently being considered taking in consideration the new opportunities opened by the 3D environment of the new simulator. We also have adapted our previous researched methodologies to the new 3D environment:

• Strategy for a Competition with a Team with Opposite Goals [1, 4, 5, 16];
• Concepts of Tactics, Formations and Player Types [1, 3, 4, 16];
• Distinction between Active and Strategic Situations [1, 4];
• Situation Based Strategic Positioning (SBSP) [1, 4, 5];
• Dynamic Positioning and Role Exchange (DPRE) [1, 4, 5];
• Visual Debugging and Analysis Tools [1, 3, 17];
• Optimization based Low-Level Skills [1, 3].
• Standard Language to Coach a (Robo)Soccer Team [2, 3];
• Intelligent Communication using a Communicated World State [1, 3, 5];

• Flexible Set-plays for coordinating robosoccer teams [18].

In 2010, research will be mostly concerned in developing optimization based low level skills for the humanoid agent and robust mid-level skills. The high-level layers of the team will be adapted to be used in the humanoid simulator (these methodologies have already been adapted to our Simulation 2D, Simulaton 3D with spheres model, small-size, middle-size [19] and rescue teams [20]).

8. Conclusions

Almost all of our research on high-level flexible coordination methodologies is directly applicable to the 3D league and the increase in the number of elements of the each team is very welcome, enabling coordination methodologies to be useful in this league.

Robust low-level skills have been developed for the NAO humanoid model, using optimization and learning techniques, enabling us to continue the research in strategical reasoning and coordination methodologies that should be the focus of the simulation leagues inside RoboCup.

Future work will be concerned in developing a general optimization framework for biped robots' low-level skills and developing coordination methodologies enabling teams of humanoid robots to play robosoccer games in a robust and flexible manner.

Acknowledgements

This work was partially supported by the Portuguese National Foundation for Science and Technology FCT- PTDC/EIA/70695/2006 Project - "Adaptive Coordination of Robot Teams" and by the SFRH/BPD/65575/2009 and SFRH/BD/66597/2009 scholarships. We also acknowledge Matthew Sottile for developing the S-expressions library used in our code and Little Green Bats team for their 2008 source release (some of our low-level movements are adapted or optimized from there).

References

1. Luis Paulo Reis and Nuno Lau, FC Portugal Team Description: RoboCup 2000 Simulation League Champion, In P. Stone, T. Balch and G. Kraetzschmar editors, RoboCup-2000: Robot Soccer World Cup IV, LNAI 2019, pp 29-40, Springer, 2001.
2. Luís Paulo Reis and Nuno Lau, COACH UNILANG A Standard Language for Coaching a (Robo) Soccer Team, in Andreas Birk, Silvia Coradeschi and Satoshi Tadokoro, editors, RoboCup2001 Symposium: Robot Soccer World Cup V, Springer Verlag LNAI, Vol. 2377, pp. 183-192, Berlin, 2002.
3. Nuno Lau and Luis Paulo Reis, FC Portugal Homepage, [online] available at: Http://www.ieeta.pt/robocup, consulted on February 2010.
4. Luis Paulo Reis, Nuno Lau and Eugénio C. Oliveira, Situation Based Strategic Positioning for Coordinating a Team of Homogeneous Agents in M.Hannebauer, et al. eds, Balancing Reactivity and Social Deliberation in MAS – From RoboCup to Real-World Applications, Springer LNAI, Vol. 2103, pp. 175-197, 2001
5. Nuno Lau and Luis Paulo Reis, FC Portugal High-level Coordination Methodologies in Soccer Robotics, Robotic Soccer, Book edited by Pedro Lima, Itech Education and Publishing, Vienna, Austria, pp. 167-192, December 2007, ISBN 978-3-902613-21-9
6. Hugo Picado, Marcos Gestal, Nuno Lau, Luís Paulo Reis, Ana Maria Tomé, Automatic Generation of Biped Walk Behavior Using Genetic Algorithms. In J.Cabestany et al. (Eds.), 10th International Work-Conference on Artificial Neural Networks, IWANN 2009, Springer, LNCS Vol. 5517, pp. 805-812, Salamanca, Spain, June 10-12, 2009
7. Hugo Marques, Nuno Lau and Luís Paulo Reis, FC Portugal 3D Simulation Team: Architecture, Low-Level Skills and Team Behaviour Optimized for the New RoboCup 3D Simulator, Reis, L.P. et al. eds, Proc. Scientific Meeting of the Portuguese Robotics Open 2004, FEUP Editions, C.Colectâneas, Vol. 14, pp.31-37, April, 23-24, 2004, ISBN 972-752-066-9
8. Nima Shafii, Omid Mohamad Nezami, Siavash Aslani and Saeed Shiry Ghidary*.* Evolution of Biped Walking Using Truncated Fourier Series and Particle Swarm Optimization, RoboCup Symposium 2009, Jacky Baltes, Michail G. Lagoudakis, Tadashi Naruse, Saeed Shiry, editors, Springer, LNAI, Graz, Austria, 2009
9. R. J. Konz, S. Fatone, R. L. Stine, A. Ganju, S. A. Gard, S. L. Ondra. A Kinematic Model to Assess Spinal Motion During Walking, Journal of Biomechanics, vol. 31, pp. E898- E906, 2006.
10. L. Yang, C. M. Chew, A. N. Poo. Adjustable Bipedal Gait Generation using Genetic Algourithm Optimized fourier Series Furmulation. In: Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4435 - 4440, 2006.
11. N. Shafii, M. H. Javadi, B. Kimiaghalam. A Truncated Fourier Series with Genetic Algorithm for the control of Biped Locomotion. In: Proceeding of the 2009 IEEE/ASME International Conference on advanced intelligent Mechatronics, pp. 1781--1785, 2009.
12. H. Elftman, The Function of the Arms in Walking. J. Human Biology Vol. 11, pp. 529— 535, 1939.
13. S. H. Collins, M. Wisse, A. Ruina. A 3-D Passive Dynamic Walking Robot with Two Legs and Knees. Int. Journal Robotics Research Vol. 20, pp. 607 - 615, 2001.
14. N. Shafii, A. Khorsandian, A. Abdolmaleki, B. Jozi. An Optimized Gait Generator Based on Fourier Series Towards Fast and Robust Biped Locomotion Involving Arms Swing. In: Proc. 2009 IEEE Int. Conf. on Automation and Logistics, pp. 2018 - 2023, 2009
15. D. Thewlis, J. Richards, S. Hobbs. The Appropriateness of Methods Used to Calculate Joint Kinematics. Journal of Biomechanics, Vol. 41, pp. S320--S320, 2008
16. João Certo, Nuno Lau e Luís Paulo Reis, A Generic Multi-Robot Coordination Strategic Layer, RoboComm 2007 - First International Conference on Robot Communication and Coordination, Athens, Greece, October 15-17, 2007
17. Nuno Lau, Luís Paulo Reis e João Certo, Understanding Dynamic Agent's Reasoning, In Progress in Artificial Intelligence, 13th Port. Conf. on AI, EPIA 2007, Guimarães, Portugal, December 3-6, 2007, Springer LCNS, Vol. 4874, pp. 542-551, 2007
18. Luís Mota e Luís Paulo Reis, Setplays: Achieving Coordination by the appropriate Use of arbitrary Pre-defined Flexible Plans and inter-robot Communication, RoboComm 2007 - First Int. Conf. on Robot Communication and Coordination, Athens, Greece, October 15- 17, 2007
19. Nuno Lau, Luís Seabra Lopes, G. Corrente and Nelson Filipe, Multi-Robot Team Coordination Through Roles, Positioning and Coordinated Procedures, Proc.IEEE/RSJ Int. Conf. on Intelligent Robots and Systems – IROS 2009, St. Louis, USA, Oct. 2009
20. Luís Paulo Reis, Nuno Lau, Francisco Reinaldo, Nuno Cordeiro and João Certo. FC Portugal: Development and Evaluation of a New RoboCup Rescue Team. 1st IFAC Workshop on Multivehicle Systems (MVS'06), Salvador, Brazil, October 2 – 3, 2006