Robotic soccer provides an adversarial scenario where collaborative agents have to execute actions by following a hand-coded or a learned strategy, which in the case of the Small Size League, is given by a centralized decision maker. This work takes advantage of this centralized approach for modelling the keepaway strategy learning problem which is inherently multi-agent, as a single-agent problem, where now each robot forms part of the state of the model. One of the classical reinforcement learning methods is compared with its batch version in terms of amount of time for learning and concluding about updates efficiency based on experiences reusability.
When we talk about Batch Reinforcement Learning (BRL), we refer to one of the current line of
research in the field of Reinforcement Learning (RL), also concerned about solving sequential
decision problems modelled by a Markovian Decision Process (MDP). Given the nature of these
problems, as the intuition may suggest, the scope of this type of learning has extended to areas like
Robotics applications
As in the classical approach, with online algorithms, we still focus on teaching an agent how
to behave under certain conditions based on punishments or rewards (reinforcement signals)
depending on the results of applying a certain action
BRL approach aims to collect a bunch of experiences and then use them for updating action
influences instead of updating the action value function in an incremental way. In this batch
framework, algorithms like Experience Replay (ER) or Fitted Q Iteration (FQI)
The Robot Soccer World Cup (RoboCup,
This work, like in
Unlike the above references, most of the works found on literature
Getting closer to our case of interest, assumptions on
This document intends to compare Q-learning and its batch-version using Experience Replay on a simulation of the RoboCup Small Size League, noting that this involves a centralized decision problem, given the setup of the league, reducing the learning problem to a single agent case where each robot plays a fundamental role on the state space representation.
The remainder of this document is as follows: Section 2 makes a further description for BRL, presenting the algorithms that will be used later. Section 3 makes a brief description of RoboCup Small Size League, and explains how this setup can be used for introducing variations on the approaches found on literature for learning a keepaway strategy, while Section 4 shows the implementation of BRL algorithms on a simulated environment. Finally, Section 5 draw some final conclusions.
Reinforcement learning
As mentioned before, the task of the agent is to learn the sequence of actions (therefore the optimal policy, < ) that leads to maximize the expected sum of all the rewards received in the long-term. This is tackled by maximizing the return Rt, i.e. the discounted sum of rewards that the agent will obtain from time t, given by
n*1 Rt = É krt+1+k; (1)
k=0 where stands for the discount factor, with 0 f < 1, and rt+1 stands for the expected (scalar) reward obtained for executing action at in state st. Then, two quantifications for the expected return are defined, the value function and action value function, V and Q respectively.
Value function is defined as the expected return when the agent is on state st at time t, V .s/ = E t ^Rtðst = s`; (2) while the action value function is defined as the expected return when the agent executes at on state st at time t following policy ,
Q .s; a/ = E t ^Rtð.st = s; at = a/`: Both functions are clearly related, as
V .s/ = Eaðs^Q .s; a/`:
A representative method in model-free RL is Q-Learning
Q.st; at/ } .1 * /Q.st; at/ + rt+1 + max Q.st+1; a/ ; a where this approximation, Q, corresponds to the learned action-value function, and stands for the learning rate.
In order to understand the difference between the incremental update from online algorithms and simultaneous update of batch algorithms, consider two consecutive transitions .s; a; r; s¨/, .s¨; a; r; s¨¨/ and the classical online Q-learning algorithm. Then, when Q.s¨; a/ is computed using the update rule on (5), this change will not be backpropagated to Q.s; a/ nor any of the state-action pairs preceding s¨, being updated just when those states are visited again.
In the pure batch reinforcement learning approach, the agent does not interact with the environment while the learning phase is taking place. In growing batch reinforcement learning, which most of the modern batch algorithms are based on, the task of collecting transitions and learning from them are alternated for improving the exploration policy.
Algorithm 1 describes the procedural form of a (growing) BRL approach independently of the
algorithm used for updating Q-values, as shown on
Moreover,
One of the basic BRL algorithms, Experience Replay (ER) aim to improve the speed of convergence of the action value function by replaying observed transitions repeatedly just as if they were new observations. Algorithm 2 shows the procedural form of this algorithm.
Experience Replay procedure 1: for each training iteration do 2: for each transition .si; ai; ri; si+1/ on D do 3: Update Q.si; ai/ by using 4: end for 5: end for
Q.si; ai/ } .1 * /Q.si; ai/ + ri+1 + max Q.si+1; a/ a
It is immediate to note that what this algorithm does, is to compute several times the updates of Q-learning on collected transitions as an offline algorithm would do, thus speeding up the propagation of Q values to preceeding states, but then the system is allowed to collect new transitions for improving those previously computed estimates.
RoboCup presents a challenging domain where a team of robots have to play a soccer match against
another robotic team, where the particular assumptions on the game varies across the different
leagues. This application focuses on the Small Size League (SSL), inspired by the development and
research work made by Sysmic Robotics USM (previously known as AIS Soccer)
Figure 1 depicts the scheme of this league, where the current positions of each robot at both teams is given as result of the image proccessing made by SSL-Vision, whose images are acquired through video cameras provided by the organization comittee, located at the top of the soccer field. Then, both teams receive the exact same data to their own decision maker programs, which once an action is chosen informs the actions to take for each robot of its team via a wireless channel.
Although we tackle the problem of finding a keepaway strategy, several challenges arises at
the Small Size League in addition to the already mentioned problems like goalkeeper training on
Although we use a slightly different state space representation compared with
As the offense strategy learning for allowing the takers to learn better strategies to effectively score is out of the scope of this work, we fixed their policy in a manner that they are always chasing the ball, and once they got it, just shoot to the goal area.
Figure 2 shows the setup of this problem in the simulated environment where algorithms will
be tested, GrSim
The state is composed by distances from every keeper to all the other robots, including takers and other keepers as shown in Figure 2. Also the distance from the ball to every robot is considered, and the angle between a keeper and each taker (with respect to an imaginary horizontal line across the soccer field). In other words, the state st at a given time t is composed by • dist(Ki ,ball), • dist(Tj ,ball), • dist(Ki ,Kj), i j, • dist(Ki ,Tj), • angle(Ki ,Tj), where Ki stands for the i-th keeper and Tj for the j-th taker. Also, the reader should note that although different state representations could work for a given problem, the angle is neccessary for modelling this problem. Even when assuming that all the robots are always facing the ball, since if just the distance d from the i-th keeper to the j-th taker is used, there would be theoretically infinite points around a circle of radius d and centered on the position of the keeper where the taker could possibly be.
Then, the possible actions to execute by a keeper are • hold./: all keepers remains on their current positions without making any pass nor trying to intercept the ball. • pass.Ki; Kj/: the i-th keeper performs a pass to the j-th keeper, where obviously i j since it would be equivalent to hold() action. • intercept.K1; K2; :::; Kn/: send keepers to intercept the ball whenever its respective binary argument is set to 1.
In this case, since there are 3 keepers, intercept.0; 1; 0/ would send 2nd keeper to intercept the ball, while intercept.1; 0; 1/ would send 1st and 3rd keepers to intercept the ball. Note that intercept.0; 0; 0/ is not allowed, since it would be equivalent to hold./ action.
Note that unlike the work in
Since the final objective of the keepaway learning problem, is to learn to keep as long as possible the ball away from the goal area, then we will reward actions that privileges the ball possesion, and punish actions that leads to lose possesion and punish harder when it leads to a goal scored against the team.
When implementing the algorithms described on Section 2, we used a growing BRL approach where the batch of experiences D contains transitions from 20 episodes, where each one lasts 2 minutes of gameplay (without considering reset time when a goal is scored and robots are re-locating). Then, after updating Q-values estimations all those transitions are discarded, so the size of the Batch always have the data for 20 episodes when entering to the learning phase.
According to rewards obtained through the learning episodes, whose values are set to 5 for keeping possesion on the ball, -5 in case of losing possesion and -50 in case of the enemy team scoring a goal. Then, according to these reinforcement values, Figure 4 shows the evolution of time possesion on the ball.
It can be seen from Figure 3, where the line represents the mean through 10 reproductions of the learning task, that batch version of Q-learning using Experience Replay achieve better performance compared with its classical online version on a smaller amount of time. However, it is expected that after several learning episodes more, batch version would learn faster but they both achieve the same results at last.
Despite the efficiency on the use of collected transitions of the learning agent, speed of convergence for both algorithms is directly affected by the number of possible states obtained from the chosen state space representation. Then, as the discretization grid becomes thinner, the state space becomes larger and tabular methods become slower and even impractical for a continuous state space representation, so function approximation methods are needed.
As expected because of data reusability of experiences gathered so far, Experience Replay learn faster in terms of defending the goal area, and this is mainly due to its synchrony nature and a better use of collected experience on the interaction process between the agent and its environment for this task. Obtained results shows the benefits of re-using data efficiently and in an inherently multiagent problem tackled from a single agent learning task given the centralized setup of this league. Future work may include a more in-depth analysis including other update rules and strategies in Batch Reinforcement Learning methods, as well as field testing in other leagues, and considering a continuous state space representation using function approximators such as artificial neural networks or a fuzzy representation of states.