Alan Robinson, Hampshire College
This document describes the application of Braitenberg's Vehicles to the domain of the RoboCup AI competition. It will consider in turn the following major topics 1) Why RoboCup is an interesting domain, 2) The reasons that make it interesting to apply Vehicles to RoboCup, 3) In detail, my application of Vehicles to RoboCup. 4) The conclusions gained from therein.
The RoboCup soccer competition exists in two forms - physical robots competing in soccer-like arenas, and a simulation league that pits computer controlled agents against each other in an independently controlled server. In this project I am concerned with the later.
The simulation league relies upon a publicly available soccer simulator that allows two teams to compete against each other in a virtual soccer field. The physical parameters of the field and the players are all simulated and updated on the server side. Agents written for the competition control the players via socket connections to the server which also allow retrieval of the state of the game. Because all forms of communication are via network connections virtually any domain of AI can be made to interface with the server, and compete with other players controlled by software from radically different programming languages and AI theoretic domains.
Though the match is entirely simulated, the server is built to model some of the issues that arise in building physical robots that play soccer:
Though these added complications make building successful players more difficult and interesting, they are not the primary reason why RoboCup is an exciting challenge. More important is that a successful player must react in "real time", and not only as a single player interacting with a dynamic world, but also as a member of a team working toward a common goal. Though RoboCup is certainly not the first or only domain that features these properties, it is a domain which is in contrast to much of traditional AI research, where the problems attacked are rarely both real time, and involve multiple, fully inter-autonomous agents.
Due to the flexible nature of the interface to the server and the popularity of the competition, many different techniques have been applied to the design of players, many of them very internally complex. My interest in RoboCup centers around how much internal complexity is really necessary. Is there a comparably simple set of rules from which complex and appropriate behavior would arise? I chose to address this question using Braitenberg's Vehicles for two reasons:
First I'll describe what Vehicles are, then why they might be especially interesting for this task.
Vehicles defined
Braitenburg's entire book is dedicated to defining vehicles. Since both the small and large details all mater, space and time precludes defining them satisfactorily in this document. A short and dense definition will serve as a reminder for those already familiar with the work, and a longer one will give a few more details for those who are not.
In short
Most simply stated, Vehicles are collections of sensors and wheels. When a sensor receives a lot of stimuli (derived from how far away it is from objects in the world), it makes the wheel it is attached to move faster (or, if it is attached in reverse, slower). Different sensors often respond to different stimuli. Through combinations of sensors that are placed in different places on the body of the Vehicle (and thus, at varying distances from stimuli), the differential turning rates of wheels produce object seeking and object avoiding behavior. All this happens without any explicitly defined rules, or conditional logic, but simply through differing amounts of stimuli causing differing rates of wheel rotation. A typical vehicle
Sensor
Sensor
\ / | | wheel / \ wheel
In depth
All of Braitenberg's Vehicle designs are fundamentally similar. A Vehicle has two wheels in back, and several sensors spaced around the front that are connected to one or more of the wheels, with varying relationships. The more activation a wheel receives, the faster it turns.
Externally, Vehicles can exhibit complex, almost emotional behavior. Every behavior of a Vehicle is emergent, however, which is to say that no rule explicitly states that a vehicle desires to be near an object, ram into other objects, and avoid other objects entirely. Those intentions exist as external labels provided by the observer. Internally there are only connections between sensors and wheels. Furthermore, those connections are always active. No higher level abstractions decide which sensors to act upon given the current state. Rather, the summation of positive and negative weights must sum to zero if no action is to be taken.
A sensor produces activation based upon the amount of a specific stimulus it detects in the world. The relationship can be directly correlated (more stimuli, more activation), or fit the curve of any function (for instance, 1/X, X^2, or -X). The activation from each sensor is summed, and the wheel they are connected to turns forward or backwards (or not at all) depending on the sign and magnitude of the activation. With the right connections and weights between wheels, a Vehicle will orient and move towards the highest concentration of a stimulus, or, with a different set of connections, do the reverse. The majority of Braitenberg's book is consumed with describing a large set of other behaviors that this simple system can produce with relatively few sensors, wheels, and connections between them.
Vehicles for Soccer
In Vehicles, Braitenberg presents simple designs which exhibit externally complex behavior, and suggests the behavior of these simple models is similar in complexity to the behavior exhibited by real organisms. In the process makes many interesting points about the reducibility of many observable behaviors to very simple internal rules. Braitenberg, however, examines these behaviors in the abstract, without having the deal with the messy real world. While vehicles appear to do higher level tasks, can are they actually able to those tasks well? Successful soccer playing, for instance?
Vehicles Appropriateness for Soccer
In RoboCup, the requirement of real-time reaction leaves little time for computation on stored states. With Vehicles, computation is nothing more than the summation of current sensor activation. Since RoboCup is not an exact match to the vehicles domain (no wheels, etc), some translation is required between the two. This would mildly increase the number of cycles required, but not significantly..
In RoboCup, players must act as a team, with little communication, and quickly change roles as the ball moves around the field. In vehicles, agents can react to each other's actions and positions dynamically without any communication, and through emergent behavior, act as a team, again without communication. Since the coordination is emergent based upon locations on the field, vehicles change roles dynamically with no extra effort. This, of course, requires very carefully designed emergent behavior. Only actual trials will show if emergent behavior can produce appropriate soccer play.
In RoboCup, 11 players must interact on a team. In a traditional AI system, as the number of players increase, the amount of time spent coordinating behavior increases, usually with exponential slowdown. With emergent behavior, however, more players means that there are more chances that at least one agent will do the right thing (be in the right place at the right time) with negligible change in computation time as the number of players increase. The reason for this is that more than one player will try to achieve the most important current goal (controlling the ball, for instance), since no strong mechanism ensures that only one player tries at a time. If there were 11 separate critical tasks that always had to be maintained, then good emergent behavior would be very hard to design. Since, however, there are fewer tasks than players, emergent behavior needs only ensure one player is successful per task.
This section will discuss how I matched the domain of Vehicles to RoboCup, and the Vehicle design I used. Then I will narrate a few seconds of a typical match, and conclude with issues raised by making vehicles play soccer.
Translating Domains
From an abstract vantage point, Vehicles and RoboCup are a good match. At the implementation level, however, players are rather different from Vehicles. I addressed this via a translation layer that fed data between the Vehicle's simulation and the RoboCup server using the appropriate world view for each. The following major tasks were required:
The four forms of translation named above can be split into two categories. 1 and 2 are both "language" translations, in that without them neither the server or the Vehicle could have communicated at all. 3 and 4, however, assume a more assisting relationship, smoothing out requirements of playing soccer in the RoboCup domain such that vehicle complexity did not increase several times over just to address complications in RoboCup that are not necessarily inherent in soccer itself.
An important issue is that the "translations" could become more than just straight transformations, and start to create part of the behavior that defines the Vehicle's soccer game. In this version of the project, translations were kept to the bare minimum needed to allow Vehicles to play the game, so that the ability of pure Vehicles to play soccer could best be assessed.
Vehicle Design
If Vehicles are truly able to produce a full range of complex behavior then many different soccer playing strategies could be created. I, however, will discuss the strategy I designed, which induced the following abstract goals for all players:
To create these behaviors, I designed a vehicle with four types of sensor pairs, and connected each sensor contralatterly (i.e., all left sensors to the right wheel, etc.). Sensor activation was calculated by multiplying a constant value (the weight) by the amount of stimuli the sensor was currently receiving, and then passing the result through an envelope so that extreme levels of stimuli actually produced less activation. This function shape allowed vehicles to slow down as they got very near the object they were seeking, rather than just ramming into it or zooming by.
The weights (units are arbitrary):
Move towards ball: 500
Move towards my teammates: -250
Move towards opponents: 200
Kick toward my teammates: 30
Kick away from other players: -100
Kick toward goals : 2000
As long as the player is not within kicking distance the first set of weights are the only one's that affect play. When the player is near enough to kick the ball, it uses the second set of weights to determine where the ball is kicked.
Gameplay evaluated
Do the weights fulfill the goals listed above? Well, at first. Consider the behavior in the following timeline of a single game:
[Pregame] Players are randomly placed on the field, and all are initialized with the same vehicle control structure and weights.
[Seconds 0-2] The players nearest the ball at kickoff can see only the ball and their opponents, so they move at full speed, rushing towards the ball. The teammates closest to the ball enter the visual field of the teammates a little farther away, so those players will slow down and spread out, guarding against opponents. Further behind the front line the teammates are subject to conflicting desires to approach the ball and opposing players, and stay away from the several teammates they can see nearing the ball. For the most part, these conflicting desires keep these players back in defensive stance. Note that they were not assigned defense in any real sense, but because they are in the right part of the field to defend, they do.
[Seconds 3+] Once a player reaches the ball, the first problem emerges. Vehicles style movement works on curved motion over time effected by the wheel's differential rates of turn. None of this applies to ball kicking, where a single vector must be calculated. If, however, the kicking mechanism is constantly active as a separately orienting vehicle directly mounted on the player, it could continuously track the position of the goal, and report the appropriate vector on demand. Adding in weights for orienting on team members, and away from opponents, the vector reported could be the most appropriate pass, or the location of the goal, depending on the distance of the ball from the goal and other players.
Unfortunately, this was not possible to fully implement, since RoboCup players often do not know where the goal is (because they must be facing the goal to see it). A fancy RoboCup wrapper/translator could calculate this information with some success based upon last seen coordinates and knowledge of its own movement, though it would mean significantly more code spent on translation, again raising the issue of who was playing, the translator, or the vehicle.
Because I wanted to invest my time writing vehicles, not writing translators, I instead simulated the outcome of having a constantly orienting kicking mechanism. Whenever the kicking module was activated, the player manually rotated until it faced the goal, and then added the kicking weights, which would perturb the kicking direction away from the goal when appropriate. This was less than perfect, since the kicking angle was not evaluated continuously to triangulate upon the best location to kick, but it did demonstrate more intelligent play than just kicking the ball to the goal. Players made passes in the general directions of teammates, whenever the goal was well defended and teammates were unguarded. I'll discuss later the fact that this didn't necessarily mean they passed to players who had a good shot at the goal.
[Rest of the game] As the game progresses, and the ball moves from one side to another, the players who are nearest the ball (including those previously standing still) try to control it. If the ball suddenly moves away from the current cluster of players, the ball will no longer have enough attraction to make all of them follow, since teammates nearer the ball will repel those farther away. In this way, players conserve stamina, and stay spaced out around the field during the game, should the ball come their way. If they are near a opposing team member, they will drift towards them, guarding them.
The range of behavior, and the richness of it is fairly impressive, given that it is defined by a total of six weights applied between 12 sensors and two wheels. The quality of the game play, however, is not particularly great. The players do roughly the right things, but the execution is sometimes a little off, such as passing the ball in the general direction of a teammate, rather than directly to where the teammate will be. Why?
The weakness in applying RoboCup to Soccer
The above description of play is accurate, however it presents an optimistic side of the game. While behavior is generally appropriate, it is the small details which are most telling. It is in those details that the weakness of the vehicles model starts to show. The weaknesses flow from two types of problems applying vehicles to soccer: Those that had to do with how the domain was simulated, and those that had to do with a poor fit between vehicles and the behavior soccer requires. I will consider both in turn.
Mismatches between the RoboCup simulation and Vehicles
Primary among the problems of bringing vehicles to RoboCup is the limited range of view each player has. In order to maintain a reasonable distance from teammates, for instance, you need to know where they are. Without significant processing, all but those directly in front of you will remain invisible. This could be addressed by periodically rotating around the player's axis, but deciding when to do it and driving the process would be difficult within a pure vehicles model. Still, this is certainly an addressable problem with a better RoboCup to Vehicles translation layer. Plus it is an issue not strictly inherent to soccer (more, or better sensors would eliminate it completely), so even though it is the biggest current problem in the current implementation, I'm not too concerned about it.
Mismatches between Soccer and Vehicles
The next problems to be discussed are much more significant/theoretically interesting. To solve them, more than a good translator is required. Indeed, for these issues, it seems that players would have to be more than Vehicles with weighted connections between sensors and wheels. All of these issues could be addressed by adding structure and rules to how the vehicles act, but at the loss of the extreme simplicity and elegance of pure Vehicles. It should be worth noting that Vehicles are probably Turing complete, meaning that with enough connections (especially when built into a multi-layer network) any procedural algorithm could be implemented. I view such exercises, however, as not at all in the spirit of what makes Vehicles interesting. In this discussion, therefore, I'll assume directly connected sensors and wheels.
1) A very clear issue is that Vehicles have no way to predict where the ball will be in the future. Balls are not static objects; they are always in movement. Yet Vehicles orient on the current location of an object, not its future location. Often, that movement is easy to predict in the short range. It would be easy to hack in a sensor that predicted a future location based on the current movement vector. Such a sensor would most easily be implemented via procedural code, which is to say, it's not the sort of calculation that comes easily to a vehicle. Even if, however, the vehicle had a sensor that could predict ball location based upon its current vector, what of cases where an opposing team member (or even one of your own team members) is about to kick the ball?
Ideally, the vehicle would start heading towards where it needs to be then, or at least not waste stamina trying to reach the ball where it will shortly no longer be. Knowing either that the ball is about to be kicked, or where it might go, however, are prediction that cannot be made just by levels of stimuli impinging upon stereo sensors, (at least without more math than simple summation). Why? It should be fairly obvious that if it is hard to predict where the ball will be in the future given a simple vector, it would be even harder to design a Vehicle system sensitive to both future ball locations, opposing team member locations (which are based upon their goals, not just their current vectors), and opposing team kicking action. It is, however, the sort of prediction a procedural system could construct in many cases, given some sophistication.
1.1) A variation of the above, if the ball is heading towards a player, and the player heads towards the ball, often the player overshoots the ball, and has to turn around to catch it. There is no clear way to add differing behavior based upon the speed and direction of the ball, without moving to conditionals and other non-vehicle constructs. For instance, if the ball is moving fast towards a player, the player should move slower. But if the ball is moving away at high speed, the player needs to move even faster to catch it. Implementing lots of special cases like these quickly degenerates the simplicity that makes Vehicles attractive.
2) When passing to another player, its easy to tell who is most open in terms of not having opponents nearby. On the other hand, an opponent might be directly in-between the teammate and the goal. Using vehicles, there is no way to eliminate that player as a good passing target. All decisions must be made based upon a single vehicle's world view, derived from levels of stimuli impinging upon its sensors, not other's sensors. A player can appear a good passing target because no opponents are nearby, causing the kicking mechanism to orient on it. But if there is an opponent fairly far away from the kicker, who happens to be in-between the target player and the goal, there is no way to selectively give that opponent a larger negative sensor weight.
3) Players have no sense of where they should be on the field. Often this is an advantage, since defending & attacking, and switching between the two roles emerges naturally and fluidly from the weighted connections. Unfortunately, however, the locations of defending players becomes more and more scrambled as time progresses. Players do not move back to protect the goal when the ball moves to the other side of the field. In fact, if the game moves slow enough, all the players will move with the ball, though many at a good distance. The strong attraction of the ball is too much to override the desire to stay away from teammates who are also near the ball. Clearly, by splitting the players into attackers and defenders, this issue could be dealt with in many ways (for instance, defenders might desire to stay away from the opposing team's goal, etc. Making the players return to specific locations on the field, however, would be very difficult without some sort of cheat, such as placing beacons over their designated position.
4) Desire to stay close to opponents does not necessarily mean that a player will guard them well. Often, split between their zeal to reach the ball, and be near opponents in general, players get stuck behind opposing team members who are between them and the ball. On one hand, this seems like a good way to keep the ball from being passed back down the field by the opposing team, so this behavior is not always wrong. On the other hand, if the ball is sufficiently far down the field, it seems more appropriate to guard an opponent from the side, or even by getting between them and the ball. Another way to consider this problem is that Vehicles cannot do path finding. If a non-moving obstacle is in the way, a player would be content to push against it until the world state changes. Luckily, RoboCup (and soccer in general) has very little need for path finding, most of the time. It's a good thing soccer isn't played in a maze.
In the end, it seems like Vehicles are not as good a match with soccer as it might have initially seemed. At the same time, much of the effort and complexity of this project had to be completed just to make the Vehicles system interface with the soccer server. At least some of that translation would not be at issue with a real robotics system, or a different soccer simulation. Perhaps game play would be significantly better if that time had been spent on a slightly richer internal Vehicle structure. Allowing for non-linear weights, and connectionist style networks, rather than direct connections from sensors to wheels, would increase the range of behavior without significantly decreasing the elegant simplicity of Vehicle designs. That, combined with better translation between domains, might result in significantly better overall performance, while still maintaining the appeal of vehicle based design:
And even if the level of game play does not improve significantly in a fuller implementation, Vehicles are still a very interesting way to analyze the structure of the problem, or perhaps augment more traditional approaches. For instance, Vehicles are very good at switching tasks on demand and in the heat of the moment. A second module that wakes up periodically could help a lot by making strategic decisions (such as moving back to defending the goal, etc), or by taking over when the ball is close enough that vector and relative speed mater. Such a system could draw on the strengths of both Vehicles and procedural systems. There are probably a lot of combinations between more traditional approaches and Vehicles that would be very interesting and/or effective.
I'm happy to share my source code if anybody is interested. As noted above, there is a lot of work needing to be done, so I suspect you would be better off starting from scratch with the current example implementation for your favorite language. See the RoboCup Simulation Library Archive for a list. I found the krislet java program the easiest to work with, though I had to modify it to work with the 5.x server I used. You can download the original krislet implementation with my small patch here.