View Original PDF

KgpKubs Team Description Paper Robocup 3D Simulation League 2018

Abhinav Agarwal, Nishant Nikhil, Vaibhav Agarwal, Buridi Sree Aditya, Ranjith Kumar, Pratik Tibrewal, Shivansh Mundra, Eeshan Gupta, Shubhanan Shriniket

Indian Institute of Technology, Kharagpur West Bengal, India

https://github.com/LARG/utaustinvilla3d/

Abstract This paper reports the recent developments by the Kgpkubs team. It describes the work on passing, formation strategies, heuristic role assignment and other tactics used to improve the game play.

Introduction

Kgpkubs is a team from IIT Kharagpur, India. It aims to make autonomous soccer playing robots. For this, the team is currently focusing on 3D Simulation and Small Size League Event in Robocup. Students from all departments and years are part of this including undergraduates and post-graduates. The principal investigator for the project is Prof. Jayanta Mukhopadhyay and it is also mentored by Prof. A.K. Deb, Prof. D.K. Pratihar and Prof. Sudeshna Sarkar. We have previously participated in FIRA RoboWorld Cup in the years 2013- 2015 in the Mirosot League. In 2015, we secured Bronze position in the same. In 2016 and 2017, we participated in RoboCup (3D Simulation League). We also participated in the Robocup Asia Pacific 2017 3D Simulation League.

This work is organized as follows. First, we give an overview of our base architecture and strategy in Section 2. Section 3 describes about attacker and goalkeeper tactics. Section 4 describes about the Positioning and 5 about the Role Assignment Algorithm. Section 6 describes the approach we use for deciding and doing pass. Section 7 describes the various machine learning methods that we have used and plan to use to optimize low level skills.

Overview

Our base architecture is based on team UT-AustinVilla code available on Github. The code is divided into appropriate modules and provides us with the flexibility to modify and develop easily.

Our strategy is based on using a mix of Delaunay Triangulation for proper positioning of robots on the field and assigning tactics for carrying out specific tasks. For Positioning, every robot performs calculation of positions using Delaunay Triangulation for all robots and then uses Hungarian Algorithm to find the position assignment for each robot. This result is then communicated by each robots taking turns. Upon receiving the results from the other 10 robots, the robot performs a voting to obtain their position and roles. Some important roles like attacker, defender, goalie are assigned based on some heuristic methods overriding the Hungarian algorithm.

Tactics

Although we uses Delaunay triangulation method to generate bot positions at certain instances of the game, it is not always possible to assign a predefined position to all agents. There is a need to obtain a separate tactic for those cases which may not yield desirable results with a predefined tactic data set. These cases are the most dynamic and important of all as they critically affect minor requisites which may arise during the game.

The Attacker bot is arguably the most dynamic bot on the field.This role is selected based upon certain heuristics like fallen status,distance from opponent etc. The attacker can quickly dodge, dribble, kick(fast and slow) and drive ball to goal. Goalkeeper is a static member of the game. It doesn't switch it functionality with any other bot on the field. It occupy the near-to-goal area of the field and is most sensitive to minor changes in ball position and velocity. The goalkeeper dives when it knows the interpolated ball position is out of its reach in a given time window. Hence, the goalkeeper decides when to dive as an incorrectly timed or useless dive may actually do more bad than good. We have multiple types of dives that goalkeeper can use, depending upon game play.

We have improved our multiagent coordination strategy from last year; players obstructing the path of the attacker diverge away. This results in a decrease in collisions among our players and hence a more uninterrupted attacking game play is established.

Positioning Module

In soccer, player positioning and role allocation is a very important aspect of the game. Meticulous player positioning affects the general temperament of the game and proper collaboration of various tactics is vital for a team to function efficiently.

Kgpkubs uses Voronoi-Cell Delaunay Triangulation method to generate and co-ordinate player positions with respect to the varying circumstances. Voronoi Cells are the result of a partitioning of the space into small regions based on their distances from their focal point. A point in a plane, say x, is said to lie in the Voronoi cell of a point y , if and only if the point x is more close to point y than any other point in the space.

Delaunay triangulation is the Dual graph of Voronoi cell plane. Hence, Delaunay triangles ensure that no other focal point lie inside the circum-circle of the Delaunay triangle formed. Also, due to this property it tends to avoid skinny triangles. As a result, interpolating any point inside the triangle yields to a smooth-gradient continuous equation in terms of the coordinates of the vertices of the triangle.

The algorithm used to generate player positions uses statistical data ( bot and ball positions under different conditions of the game ) and generates a data set of agent positions with respect to certain ball positions. In all 65 ball positions in strategic locations were identified and triangulated using the incremental algorithm to generate Delaunay triangles. Once the triangles are generated, the Gouraud Shading algorithm yields the value of bot positions at any given point in terms of the values of bot positions stored at the vertices of the triangle enclosing it. At first we positioned our bots symmetrically with respect to symmetrical voronoi points but it was causing some bots to go out of the field or clustering the bots to a specific area of the field thus causing various collisions. The positions of the bots with respect to a specific Voronoi Point are further overrided during the game play seeing the best possible positions of bot during a certain game state and replacing them with the alloted position which can be further used in similar game states. This helps us in dynamic positioning of the bots to a great extent. Also we are planning to use neural networks to find the best possible positions of the bot and also learn from real life football.

Fig. 1. Delaunay Triangles formed
Fig. 1. Delaunay Triangles formed
Fig. 2. Voronoi Points for a ball position
Fig. 2. Voronoi Points for a ball position

Role Assignment Module

We use hungarian algorithm which solves the role assignment problem in polynomial time. Time complexity of this algorithm is O(n 3 ). At every one second, as per the ball position, we get a set of target points from voronoi triangulation. We did not run the Voronoi updation after every few cycles so as to prevent associated penalties, like:

  • To save time as Voronoi updation is a computationally-expensive action.
  • To prevent erratic bot behaviour arising due to sudden change in ball position.

These set of target points are then matched to players on field by hungarian algorithm. The cost function used for hungarian algorithm is euclidean distance between bot's current position and target location. It is also easy to visualize that using this type of role matching has following properties

  • (a) The collisions are mostly avoided.
  • (b) Longest distance is minimized
  • (c) It is dynamically consistent

We have a superficial layer over the hungarian role mapping. We override the hungarian mapping by using heuristic functions for specific roles for better assignments.

We have worked on prioritized role mapping which changes the position of bots by overriding Hungarian to the nearest opponent carrying the ball. This helps us in dynamic positioning of our bots.

Passing

Passing is one of the most essential element for a multi-agent football playing system. We implemented a fuzzy logic based passing, which for each team member within a threshold radius takes into account

  • target player's distance from source player
  • distances of opponent players from source player and target player
  • proximity to goal of source player and target player
  • angle to rotate for source player to face target player

and if all those binary conditions are satisfied then we deem ourselves in a favourable position to pass, otherwise we continue as is. Few points worth a notice:

  • while calculating distance you can't give the same value to an opponent player in front of our player and behind of our player.
  • you need to consider only those places to pass where you can kick accurately (at time of writing this kgpkubs had not developed a kick which can cover whole of the field).

Future Work

Currently we have used CMA-Evolutionary Strategy for improving low level skills, we aim to use deep reinforcement learning for the same where we plan to use deep deterministic policy gradient to better our walking action by training the inverse kinematics parameters. Furthermore we are aiming to use neural networks for automating the positioning module and parallelizing the algorithm for use on multi-core systems and considerably increasing the learning speed.

Acknowledgements

The team also acknowledges the mentorship and guidance of our professors Prof. Jayanta Mukhopadhyay, Prof. Sudeshna Sarkar, Prof. Alok Kanti Deb and Prof. Dilip Kumar Pratihar. This research is supported by Sponsored Research and Industrial Consultancy(SRIC), IIT Kharagpur. We also thank our former team members who made all of this possible.

References

  1. Patrick MacAlpine and Peter Stone. "Prioritized Role Assignment for Marking." In Proceedings of the RoboCup International Symposium (RoboCup 2016) in Leipzig, Germany, July 2016.
  2. Patrick MacAlpine, Eric Price, and Peter Stone. SCRAM: Scalable Collisionavoiding Role Assignment with Minimal-makespan for Formational Positioning. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI), January 2015.
  3. MacAlpine, Patrick, Francisco Barrera, and Peter Stone. "Positioning to win: A dynamic role assignment and formation positioning system." RoboCup 2012: Robot Soccer World Cup XVI. Springer Berlin Heidelberg, 2013. 190-201.
  4. Barrett, Samuel, et al. "Austin Villa 2011: Sharing is caring: Better awareness through information sharing." The University of Texas at Austin, Department of Computer Sciences, AI Laboratory, Tech. Rep. UT-AI-TR-12-01 (2012).
  5. Jun, Youngbum, Robert Ellenburg, and Paul Oh. "From concept to realization: designing miniature humanoids for running." J. on Systemics, Cybernetics and Informatics 8.1 (2010): 8-13.
  6. Erbatur, Kemalettin, and Okan Kurt. "Natural ZMP trajectories for biped robot reference generation." Industrial Electronics, IEEE Transactions on 56.3 (2009): 835-845.
  7. Strom, Johannes, George Slavov, and Eric Chown. "Omnidirectional walking using zmp and preview control for the nao humanoid robot." RoboCup 2009: robot soccer world cup XIII. Springer Berlin Heidelberg, 2009. 378-389.
  8. Liu, Juan, et al. "Apollo3D Team Discription Paper."
  9. Akiyama, Hidehisa, and Itsuki Noda. "Multi-agent positioning mechanism in the dynamic environment." RoboCup 2007: Robot soccer world cup XI. Springer Berlin Heidelberg, 2007. 377-384.