| INTRODUCTION | PROBLEM DEFINITION AND ALGORITHM | EXPERIMENTAL EVALUATION |
| RELATED WORK | FUTURE WORK | CONCLUSION |
The goal of this project is to improve the Artificial Intelligence system of Cornell University's RoboCup team, specifically concentrating in developing a more complex passing game. The current AI system only takes into account a limited amount of possible passing lanes, thus making it impossible to pass on many occasions. Most of the time robots do not pass to each other; they prefer to dribble the ball towards the goal on their own. When they do pass, they might not even consider an optimal passing lane. Since the playing field will be enlarged next year, the need for passing game is pressing. With the wider field, there are more passing lanes to explore, unfolding new offensive plays. Furthermore, having a passing game would increase the overall playing level in RoboCup tournament.
In this project we designed algorithm that will give the ball handler more passing lane options to choose the optimal one. The basic approach of our algorithm is heuristic search. We are going to implement this algorithm in the actual RoboCup real time system. In a real time system, minimizing computation time is essential because of the demand to produce immediate reaction. Search problems can usually be complex and takes up lots of processing time. Heuristic search methods have been shown to be efficient alternatives to traditional search methods for a variety of search problems, including traditional search problems, moving-target search problems, STRIPS-type planning problems, robot navigation and localization problems with initial pose uncertainty, robot exploration problems, totally and partially observable Markov decision process problems, and reinforcement-learning problems, among others.
The inherent conceptual difference from our approach and the old one is that the latter consider points that can be reached by the ball. On the other hand, the former consider points that can be reached by the intended receiver. Our approach is better because the old algorithm occasionally considers points that cannot be physically reached by the intended receiver, which renders useless points.
We will present the output of our simulation, which is a list of coordinates denoting point of receptions, plus their corresponding heuristic value, sorted in increasing order. We conclude that when we consider nearly all options, an optimal passing lane can be selected.
Task definition:
Our algorithm specifically has to solve the problem: given a set up of a playing field (i.e. field configuration, with positions of our robots, opponents' robots as well as the position of the ball), and the fact that our team has the ball, come up with a set of possible points that we can pass to our teammates and choose the best one. The solution will enable Cornell RoboCup team to make intelligent passing to elevate its game.
We define best point as a position that maximizes the ability of the recipient of the pass to score a goal. The size of the set has to be such that it will not contain too many elements. The input of our program will simulate a playing field configuration. We will supply the coordinates of our and opponent robots as well as the ball position. The output is a set of coordinates that, when paired with the ball handler position, will form possible passing lanes. These passing lanes will be scored accordingly using several heuristics. Passing lane with the smallest score will be chosen as the best.
Algorithm:
Algorithm definition:
At the start of the program we need to set up the location of our robot, the opposing robots, and the ball. This is actually a trivial task for the vision systems and the AI have extracted the important information for us. First we identify the offensive players (in the simulation we will just pass in the information of our offensive players), which robot has the ball, and which are the prospective receiver of the pass.
Around these prospective receivers, we lay out a set of points within a radius of reach (40 cm); one of which will be the point of reception. These points represent the spots that the robots can reach in actuality. If the robot cannot actually reach the point, it cannot receive the ball there. These points will be stored as offsets from the current location of each prospective robot. The reason we pick 40 cm as an upper bound distance is because our offensive strategy is designed to keep a forward robot to stay in one side while another forward at the other side. Thus a quarter of a field both ways would enable a robot to cover its territory. Also, from our observation, robots do not usually travel more than 40 cm without stopping.
We will not be using the orientation information because our set of points are close enough together that any way we orient them, they are essentially the same set of points. In the actual implementation, however, we have to consider the rotational latency of our receivers. That is, we have to measure the distance of travel to the point of reception as well as which side the robot has to face. For our simulation, we will just consider these two components to average out with the velocity (1.5 m/s).
After these points are set up we will immediately prune points that can immediately be dropped such as points that are out of bounds, points behind other robots, points that require our robot to hit another robot to get to the point of reception. For the last type of points, we actually have obstacle avoidance software, however this will considerably slow down our robots and they will not get to the spot in time to receive the pass.
Now we can put these points through a heuristic function and find the best passing chances. Our final heuristics value is between 0 and 1 (inclusive). The lower the value, the better the quality of the passing lane. The value 0.5 is selected as a threshold to evaluate a pass. A value lower than .5 usually signifies that a pass lane is worth considering.
The heuristics are basically divided into two underlying principles. The first one is the likelihood of connecting a pass from one robot to another. The second one is the probability of the receiver of the pass to score a goal. There is a balance that we have to create between these two notions in the point system. We might want to try a risky pass that will give us a great chance to score, or a safe pass that would not give us a good chance to score, but at least we are more likely to retain the possession and try to create other chances from there. For our final heuristic value both principles will carry the same weights. Keep in mind we can only measure dimensions and the current opponent positions because we do not know how they might react from a pass.
The heuristics for our first principle, likeliness of making a pass connection, is as follows (The "point" referred is the point at which the receiving robot will receive the pass):
Heuristic 1a.
If point A is further away from the receiving robot than point B then point B is given lower (better) value.
Heuristic 1b.
If the path of pass to point A is further away from the closest opponent robot than point B from its corresponding closest opponent robot, then point A is given a lower value.
We measure heuristics 1a. by measuring the distance between the point of reception and the current position of receiving robot. The range of a raw measurement is between 0 (staying in place) and 40 cm (about a quarter of the width of the field). The assignment of values is: any point lower than 5cm, moving within 5 cm, is 0 while any point further is linearly mapped with 40 cm valued to 1.
We gauge heuristics 1b. by measuring the smallest perpendicular distance from the position of the opposing robots to a line created by the current position of the ball handler and the point of reception. Basically, the heuristics states that the further we our line of pass from an enemy robot, the better our chances of not having it picked off. We mapped the raw value in reverse linear manner to a range of 0 to 1, by assigning 1 to 12 cm (barely missed the robot) and 0 to 52 cm (about a third of the width of the field). We pick 52 cm because it the longest realistic distance that a robot can travel to intercept a ball, any points further than that are assigned to 0 (impossible).
Within the scope of these two heuristics we feel that heuristics 1a should bring more weight than 1b. The completion of a pass depends more on how fast the robot can get to the point of reception then the ball can get to that point. Also, the speed of our passes (about 1m/s, the maximum practical speed of robots are about 1.5 - 1.8m/s) is high enough that it takes a split second reaction to intercept it, either by predicting the direction of the pass or by a mere coincidence. Thus, we still have to consider the ability of the opponent robots to intercept our passes. Heuristics 1b. discourages us from passing too close to the opponent robot and have the ball bounce off them. Heuristics 1a is responsible for .275 of the final value, while 1b is responsible for .225 of the final value, for a total of .5 from heuristics 1.
The heuristics for our second principle, likelihood of making a score from the point of connection, is as follows:
Heuristic 2a.
If the point A is further away from the goal then point B then point B weights less than point A.
Heuristic 2b.
If point A is further away from the other opponent robots as a whole than point B, then point A is given lower value.
We measure heuristics 2a. by averaging distance from the point of reception to both goal post. The raw value is linearly mapped to a scale of 0 to 1 with 0 signifying shooting from the goal-line and 1 signifying shooting from 100.00 cm away from the goal. Any point further is assigned to 1.
We measure heuristics 2b. by averaging the distance from the point of reception to all the opponents' robots. We pick the average of distance, and not just the closest robots, is because if that robot impedes our shot totally, we will try to dribble past it, and then we still have to deal with the other robots anyway. We map the raw value to a scale between 0 and 1 for the final value in linear reversed linear conversion. The minimum value of 0 represents 103.6 cm, the maximum average distance of the opponent robots from us. The situation is if the opponents are the corner of their half of the field while the point of reception is at the middle of one half of the field. Anything further does not give us any more advantage. The maximum value of 1 represents 18 cm, minimum distance the proximity of other robots. In this case they are bumping us.
In the final heuristic value, the weight of heuristic 2a and 2b are equally weighted. Heuristic 2b takes account of how the proximity of opposing robots can severely hurt our chance to even shoot the ball and that the farther they are the better our scoring chance. Heuristics 2a, on the other hand, will take account the goalie, the fastest robot on the field.
It is better to shoot from the middle of the field than from the corner because the shooter can see more of the goal from there. For corner shots, goalies use an effective strategy of guarding the short corner and use its width to guard the angle for shots to the other side. We do not know how the opposing goalie will react after the pass will be completed. However, we assume that it will position itself at the optimally, mirroring the shooter, bisecting the angle created by the two line of shots to both goal post. This way our best bet will be to try to shoot to the posts. Our heuristics of averaging distance to both goal posts actually takes account of the option scoring to the short side as well as the far side. Because of the way we are measuring the value of heuristics 2a, to receive the same value, shots from corners has to be take closer than shots from the middle of the field.
This, however, clashes with heuristic 2b.which tends to give a better (lower) score if we are near the sideline. It is usually crowded in the middle of the field although we have a slightly better scoring chance if we shoot the ball from there. However, in the middle of the field, we may not even have a chance to line a shot. Thus, because we can argue that in the sidelines we have a better chance to shoot the ball in the first place, these heuristics (2a. and 2b.) should be assessed equally.
Methodology:
We run our program with many test cases i.e. field configurations. We wanted like to test the hypothesis: "more choices of passing lanes yield better selection of passing lane," by comparing our algorithm with the old one. Furthermore, we also evaluate, based on our soccer knowledge, whether the point returned by our algorithm is indeed the best point to pass to. We want the robots to think like human soccer players. The independent variable in our experiment is the input, i.e. the positions of the robots and the ball, and the dependent variable is the set of possible passing lanes.
The data collected from our experiment represents the set of coordinates that define possible passing lanes. Each point has its own total score, derived from the four heuristic values defined in Section 2: Problem Definition and Algorithm. The coordinates are ranked based on their total score. We use the scores to evaluate the validity of the passes.
Results:
We run our algorithm in 30 test cases (field configuration), some of which are be selected as examples in Appendix A. Out of the 30 tests, our algorithm performs up to our expectation 25 times. By 'our expectation' we mean that the passing point chosen by our algorithm is the same as the point that we, as human soccer players would choose. Thus, using human expectation as performance metric, we obtain 83.33% success rate. In the other 5 test cases, our algorithm does not choose a similar passing lane as a human soccer player would because it either: lacks the ability to do more than one step look-ahead or it is being too conservative.
In addition, in the 30 test cases, our algorithm always provides more passing lanes compared to the old algorithm. This 100% success rate is a good indicator that our algorithm will always supply the RoboCup AI system with bigger set of possible passing lanes. It does not matter whether the eventual chosen point is the same with the point selected by the old algorithm. This is because, with more options, at worst we will end up with the same decision as the one taken by the old algorithm. Therefore, our algorithm will never perform worse than the old algorithm.
Discussion:
In order to understand why our algorithm always gives more passing lane options, it is important to understand the old algorithm. It considers three different types of passes to construct a set of possible points. The first type is called split pass, it bisects the space in between two robots. With 5 opponent robots, there are at most 5 spaces that the algorithm will try to pass to. The second type considers points in front of opponent robots because our robot can seal the ball at these positions. Thus, there are at most 5 additional passing lanes. Finally, the algorithm also considers passing to an open space where no robots are detected. There are usually about 3 to 5 points in this area. Thus there are at most 15 points being considered. Keep in mind that some of the referenced points are not reachable by the receiver in the first place. This is much fewer than our algorithm, which considers up to 390 points.
This is a distinct advantage because from these points, new passes (both direct and lead passes) can be constructed. Direct passes are passes that are directed towards a stationary robot, while lead passes are directed towards a moving robot. In game situation, however, direct passes are more likely to be intercepted, because the opponents only need to stand on the path between the ball and the receiver. Lead passes on the other hand opens up a new set of opportunities. Unlike the passes produced by the old algorithm, these passes does not use opponent robots as reference points. In many cases, the optimal pass is taken from this set of passes because the set contains points that are further away from the defensive alignment. If the points fall within this alignment, our heuristic function will pick the best one possible.
A visible drawback from our results is an observable effect that we call point cluster. It is defined as a set of points with approximately the same scores and similar coordinate values. This entails that some points can be combined to form a single passing opportunities, though technically each point is legitimately different considering the spacing and the size of our robots.
Of course, there are always unique situations that lend itself to the old algorithm. Although we would probably produce the same passing lane as the old one, the old algorithm produces it faster.
Our background readings can be split into two groups: RoboCup-related and other relevant literatures that deal with the application of heuristic search on real-life problems. There are many applications of heuristic search on real-life problems: shortest distance problem, 8-puzzle problem, geographical analysis problem and many more. One example that stands out is optimal nuclear bombing problem. This problem is similar to ours in the sense that it uses heuristic search in order to locate points on a map. However, there are differences (besides the fact that theirs is doing harm to mankind and ours is not). Firstly, their algorithm scans the whole map at each iteration, whereas ours just consider a subset of the whole playing field at each iteration. This is because the nature of our problem is real-time whereas theirs is not. Another difference is that, their algorithm, just like most AI application in geographical problems, uses spatial analysis. Works using spatial analysis usually have problems because once data is collected from experiments, hypothesis can be formulated but not proved. Our algorithm can be used to prove our initial hypothesis that "more choices of passing lanes yield better selection of passing lane".
From our RoboCup readings, we discovered that some people have tried implementing passing play in their RoboCup team. One popular approach is using neural network to actually train the robots so that they could learn when to pass and when not to pass. This sounds like a good approach. However, it is not very practical if we are pitting the trained robots against unknown opponents, because we will not know how the opponent robots will react and behave on the field. Our approach is better than this because our algorithm makes the robots react based on the actual condition on the playing field. Thus our method for tackling this problem is currently more suitable for the actual RoboCup competition.
Although our algorithm works well in solving the passing problem, there are several issues that still have to be resolved. The most obvious thing is perhaps the fact that our algorithm still needs to be transferred into the actual RoboCup system. Once our code is ported into the system, we have to test it and there will be issue with robot's rotation. In our simulation, we only consider receiving robot's position and not its orientation. In actuality, the robot has to be oriented such that its dribbler faces the incoming ball in order to trap the ball. A method that calculates robot rotation has to be developed. This method does not fall into Artificial Intelligence category, thus it is not in our simulation.
One major assumption that underlies our approach is that we are not taking into account individual opponent's robots agility. We assume that, as long as the passing lane is beyond an average opponent's reach (the further away the better) then it is a valid passing lane. In the future, we may need to develop a way to extract this information. We can probably do this by logging in velocity and acceleration. This will enable the system to adjust itself to the ability of the opponent in determining which pass is save.
We also have to correct the point clustering that we get in our result. We may be able to approach it differently. One way is to look at passing lanes graphically, looking at spaces on the field in big picture before going more specific within a certain zone until we can pinpoint a single spot. If we can solve the problem above efficiently, we might have a chance to plan our passing strategy in more than just one step (the best pass at the current situation). Humans can see four to five exchanges ahead to help decide on the current move. We have to take account on how the opponents might react to our moves, which require learning the tendencies of the opponents. Overall this improved approach is similar to the minimax-algorithm, though we have window of 3 milliseconds to come up with a move.
From the results of the experiments done in section 3, it can be seen clearly that our algorithm will provide Cornell RoboCup AI system with more passing options. Furthermore, from a larger pool of possible points, we can consider optimal passing lanes that the old algorithm never took into account.
Our project shows that in real-time, unpredictable situations, heuristic search, with knowledge base is still the best approach. Since situations are unpredictable, learning algorithms are often unfeasible. Furthermore, since the situations are real-time, we have to minimize processing time, and heuristic is the best mechanism to achieve this goal. We hope that our project will inspire further research in using heuristic search on real-time problems, especially those in unpredictable situations. For example, lunar navigation and robot control.