AI AND A-LIFE
A game of three robots
The World Cup it isn't , but there is m than a trophy at stake in the world's strangest soccer tournament. The man with the whistle is John Casti
AS THE YELLOW PLAYER intercepts the orange ball cannoning off the board that surrounds the playing field, the blue goalkeeper moves out to cut down the attacker's angle on goal. But instead of shooting, the forward passes the ball to a team-mate streaking up the left side of the field, who darts around the sluggish goalkeeper and pops the ball into the net. Score one for the yellow team from Newton Labs in Seattle, in a crushing 20-0 defeat of the blue SOTY team from South Korea in last November's final of the first ever Microrobot Soccer Tournament. In just over a month, the teams will meet once again to try to knock Newton Labs off the winner's rostrum.
The MIROSOT, as it's known, is the brainchild of Jong-Hwan Kim, his colleagues and students at the Korea Advanced Institute of Science and Technology (KAIST) in Taejon, South Korea. They hope football will become a touchstone, stimulating the robot builder's art in much the same way that chess motivates artificial intelligence research. Robot football makes heavy demands in all the key areas of robot technology: mechanics, sensors and intelligence. And it does so in a competitive setting that people around the world can understand and enjoy. The hope, of course, is that by discovering how to get a robot to move with agility, see with acuity, and think perceptively in the limited context of a football game, it will be possible to use the same techniques to build robots to carry out other, more useful tasks.
Here the analogy with chess-playing and AI starts to break down, since in several decades of trying, there's not much evidence that the methods developed to allow computers to play chess to grandmaster level have any use beyond the edge of a chessboard. But the robot builders of the MIROSOT believe firmly that their case is different, probably because much of the challenge of robot football centres on the hardware issues of mechanical motion and vision processing rather than the pure information-processing problems that characterise chess programs.
November's tournament brought together 23 teams from nine countries on the grounds of KAIST, where they competed for the Hanminjok Cup. The same basic rules will apply for the second tournament, this June. Each team consists of just three robots. And each player's mechanics and "brain" must be packed into a cube no larger than 7.5 centimetres on a side. Unlike a real football pitch, the 130-centimetre by 90-centimetre playing field is bounded on all sides like an ice-hockey rink to prevent the ball-an orange-painted golf ball-from going out of play.
The teams gather information about the location of the ball and players from TV cameras suspended above the pitch. That information goes first to an off-pitch controller and then by radio to the robots themselves. And here is where the first big difference appeared between the teams-they vested differing degrees of autonomy in the robots themselves. All but two groups of researchers transmitted just positional information to their robots, allowing the machines to find their own way to the ball. These robots carried on-board sensors to help them avoid collisions with other machines.
One of the two exceptions was the Newton Labs team, which went for a more centralised approach. Its robots were "brainless", and the offpitch controller dictated their behaviour totally, telling them where to move and at what speed. These robots had no collision-avoidance sensors. So the competition did not simply set like against like: there was a "generational conflict" at work as well, between the old-style centrally planned strategies, and the beginnings of the more ambitious strategy of allowing robots to make their own decisions.
My own involvement with the MIROSOT stemmed from a chance encounter early last year in Japan with Kim at a meeting on artificial life and robotics. I had just given a talk on some football simulations that I'd carried out on Super Bowl XXIX, the championship event that capped the 1994-95 season in the American National Football League. These experiments consisted of playing the game between the San Francisco 49ers and the San Diego Chargers 100 times in my computer, using a program that rates all the players in the NFL by their individual playing characteristics. My goal was to see if the odds quoted by the Las Vegas bookmakers for the game bore any resemblance to statistical reality as calculated by my computer*.
For me, the interesting theoretical point of this experiment is that football is a classic example of what is termed a complex, adaptive system. These are systems composed of a medium-sized number (up to a few hundred thousand) of "agents" that are intelligent and adaptive. This means they take actions based on rules, and are adaptive in that they can change the rules or invent new ones if they see that the old ones are not working. Furthermore, the agents must make choices on the basis of incomplete information about what others in the system are doing. Other good examples of such systems are financial markets, immune systems and road-traffic networks, in which the agents are traders, molecules and drivers respectively.
A number of researchers have studied the behaviour of these systems, mostly in the virtual reality of computer memory ("What if", New Scientist, 13 July 1996, p 36). Robot designers have a unique opportunity to go a step further and build physical agents capable of interacting and adapting. Indeed, creating groups of cooperating automatons is a new and growing area of research in robotics. During my presentation in Japan I said there was no better test problem for a robot builder's tentative theory of a working complex, adaptive system than a football game.
It was after this that Kim told me about the MIROSOT. My first reaction was to bemoan the fact that I didn't build robots. "No problem," he replied. "You can come and be one of the referees and make sure none of those damned robots cheat." How could I refuse? So in early November, I packed my striped shirt, a set of red and yellow cards, and a whistle, and an electromagnetic zapper for frying the brains of any cheating robot, and headed for Taejon.
Piggybacked on the sporting competition was a symposium replete with technical discussions of the approaches employed by competing teams to get their robots to play a decent game of soccer. These problems centred on three main areas. First, there are the purely mechanical problems, such as how to move the robots about the field and get them to change direction quickly as the ball rolls around. On top of that come the "sensory" problems concerned primarily with seeing the ball and the other players. And finally there are strategic problems associated with processing information about the game and designing sensible strategies and tactics to win.
At this early stage in the development of microrobot football, researchers have yet to work out the best answers to these problems. This in itself leads to another difficulty: how should the teams combine their suboptimal solutions to each problem in order to produce the best overall result? And all this within the confines of a 7.5-centimetre cube. Newton Labs' centralised approach used a very sophisticated visual system and a rather primitive playing strategy (see "Maradona, eat your heart out"). So the Seattle researchers chose to devote most of the space in their robots to mechanical motion. Others, such as the SOTY team from KAIST, tried to compensate for inferior visual systems by implementing more elaborate playing strategies, through algorithms telling their players how to react in different situations. These bigger brains, however, forced the KAIST team to compromise on physical attributes such as speed.
One difficulty confronting all the teams was what one might term the "poverty of power problem". The power needed to operate the robot's mechanics is considerable, and each robot has to carry its own power source. Existing battery technology being what it is, this limited the length of each half of a MIROSOT game to five minutes.
These technological limitations make refereeing a robot soccer game an experience in both humour and frustration. The robots' vision systems are often swamped by information and liable to be confused by certain colours, leading to players pushing the ball into their own goal. At other times, goalkeepers stand as motionless as the Sphinx while the ball slowly rolls past them into the net. And if the referee were to follow the rules to the letter, the number of free kicks for off-side and penalties for fouling an opponent by running into them would slow play to a glacial crawl. A certain flexibility in interpreting the rules is needed to keep things moving.
So what kind of solutions to the technical problems separated the winners from the losers? The answer is as simple to state as it is difficult to implement: emphasise speed and vision at the expense of brainpower. How appropriate! Here is one place where robot soccer makes contact with its real-life counterpart. It was clear from the demo game that opened the tournament that the Newton Labs robots, with their superior vision and speed, would run off with the cup. In their five games, the Newton robots won 12-3, 13-0, 15-1, 19-0 and 20-0. By comparison, no other team scored more than eight goals in any game.
On the face of it, the Newton Labs victory does little to push forward the development of autonomous agents, which is one of the underlying ambitions of the MIROSOT organisers. The Seattle robots relied on a single brain that had "complete" information about the state of play. By comparison, most losing teams opted to let their robots play some part in decision-making based on "local" information. And no robot in the competition appeared to be able to adapt its tactics on the basis of what it had learnt during a game. So while the teams may have been complex, they cannot yet be called complex, adaptive systems.
For the present, then, robot football appears to be in the laughable state that computer chess was in during the 1950s. But no one is laughing at chess-playing programs today, not even world champion Garry Kasparov, who was given the scare of his life in a recent tournament with the reigning computer champion. Whether a similar scenario will unfold with computer football is debatable. No one expects robots ever to take the field against human footballers. But at least the skills shown by the teams participating in MIROSOT showed great potential for much more refined play.
During a discussion at the MIROSOT, the idea was raised that it might be interesting to introduce a new class of play, in which human opponents control one of the competing robot teams by using, say, a joystick, Nintendo-style. This would introduce a component of human-machine competition that would add spice to the tournament and further motivate the robot builders. In any case, everyone at the MIROSOT went home enthused about the whole idea of robot football, vowing not to let the Newton Labs team win in June. A new life form-the microrobot footballer-has been created. The next MIROSOT should give us a better indications about the evolutionary pathway this creature will follow.
BOX: Maradona, eat your heart out
BUILDING A MACHINE with world-beating football skills into a 7.5-centimetre cube takes a good deal of ingenuity. And the team from Newton Labs in Seattle proved to be masters of improvisation (see Diagram). The two Canon motors that drive each robot should probably have been whirring inside someone's photocopier. Salvaged from a surplus store, they were too big to sit opposite one another without breaking the size constraints. So they had to be offset, and connected to the wheels by a drive chain the team concocted from bits of Lego.
With wheels mounted on the sides, each robot needed casters front and back to stop it tipping. But the team-Anne Wright, Randy Sargent, Carl Witty and Bill Bailey-could not find wheels small enough. They settled instead for beating bits of drinks cans into sliders. Finding a small radio receiver also proved a problem until Sargent found a pair of wireless headphones in the local branch of Radio Shack. The receiver electronics fitted neatly on each robot, while the transmitter was connected to the off-pitch controller.
No corners were cut, however, with the vision system, which tracks coloured blobs in successive video frames and can identify their shapes. During the matches, a video camera viewed the pitch from above. To this the team linked its vision system, which told the master controller the whereabouts of the orange ball, together with the position and orientation of the Newton robots-which had yellow rectangles on their lids-60 times a second. The team's nearest rival could refresh its gaze only 10 times a second.
This system was a key to the team's success. The controller continually predicted the position of the ball and ran iterative calculations to decide the best tactics for the two forwards. It calculated where the ball would be in, say, a second's time and then asked whether either robot could reach that position and score a goal. If the answer was no, it moved on to calculate the position two seconds ahead, and so on. "We would run several hundred of these simulations 60 times a second," says Sargent.
Eventually, the controller would radio to one of the forwards, telling it how fast to run its motors in order to hit the ball into the net directly, or off the side board. "We bother about the angle at which we hit the ball, but don't care too much about the velocity other than it should be moving as fast as possible," says Wright. "We like to keep the ball moving quickly so that nobody else can deal with it."
Although the Newton robots had fast reactions, their aim was not always true. Their jerky movements introduced errors that sometimes sent the ball rebounding off the backboard. Yet on occasion, even this looked deliberate. "If you look at footage of the games, you'd swear they were passing. But it wasn't intended," says Sargent. It emerged simply because 1/60th of a second after the first forward shot at goal, the controller was planning an intercept course for its team-mate.
The Newton robots had only a few other rules. A forward not playing the ball was ordered to retreat between the ball and its own goal. The forwards were also subject to two programs that acted as "repelling forces". One strong, short-range force kept them away from other robots and the sides, while a weak, long-range force kept each forward as far from its partner as possible.
The third robot, the goalkeeper, was directed by a simple program that kept it moving from side to side, in line with the ball. The only change to this was if the controller calculated that the ball would go near the goal, in which case the keeper moved sideways to intercept it. "Other teams had more complex strategies," says Sargent. "Some would move forward and back and go to meet the ball. They didn't seem to be so effective."
From New Scientist, 26 April 1997
© Copyright New Scientist, RBI Limited 1999