Using Robocup to Teach Multiagent Systems and the Distributed Mindset

José M. Vidal and Paul Buhler, Using Robocup to Teach Multiagent Systems and the Distributed Mindset, ACM Symposium on Computer Science Education, 2002.

1 Decentralized Mindset

In "Turtles, Termites, and Traffic Jams" (1997), Mitchel Resnick argues that the decentralized mindset should be taught from an early age.
Humans have a propensity towards centralized explanations.
Ants' food gathering.
Traffic jams.
Corporate or political figureheads ("It's the CEO's fault").
The Internet ("The web is down").

2 Decentralized Systems

Internet. Semantic Web.
Automated manufacturing assembly lines.
Nanotechnology, robot swarms.
Biotechnology. Biology. e.g. the immune system.

3 Multiagent Systems

Software or robotic.
How to build them?
How to map a desired emergent behavior into the individual agent behaviors? (e.g., win the game)
Provide a hands-on experience. Use RoboCup in class.

4 Robocup

An annual competition, held jointly with AI conferences.
Leagues:
- Small robots.
- Medium robots.
- Large Robots
- Simulation league
- Rescue league.
Goal: A robotic team that can beat worldcup champions.
Participants are mostly college students, with a few "professional" teams. A junior league attracts high-school students.

5 Soccerserver

The Soccerserver is used in the simulator league.
The simulator implements a realistic world.
- Actions do not always have their intended result.
- The ball loses speed as it rolls.
- There is noise in the inputs.
- The players get tired.
Demo

6 Soccerserver System

Uses UDP for communications. Messages can be lost (but they are almost never lost on a LAN).
Every player connects independently to the soccerserver.
The soccermonitor is the GUI. I also connects to the server using UDP.

7 Physics

The soccer field and all objects on it are 2-dimensional.
The players and the ball are treated as circles.
All objects move according to Newtonian physics.
The action model is discrete. 100ms.
Collisions are resolved by the server
Noise is added to the movement of objects.

8 Player's Input

What it sees, in polar coordinates relative to its current position and viewing direction.
This information includes the position of other players, the ball, goal posts, fixed flags, and lines.
The sense_body tells the player about its own body.

9 See

Visual information arrives from the server in the following basic format:

(see Time ObjectInfo ObjectInfo ...)

where

ObjectInfo = (ObjName Distance Direction
               DistChng DirChng BodyDir HeadDir )

and

    ObjName  ::=  
    (player Teamname UniformNumber)
          | (goal [l|r])
          | (ball)
          | (flag c)
          | (flag [l|c|r] [t|b])
          | (flag p [l|r] [t|c|b])
          | (flag g [l|r] [t|b])
          | (flag [l|r|t|b] 0)
          | (flag [t|b] [l|r] [10|20|30|40|50])
          | (flag [l|r] [t|b] [10|20|30])
          | (line [l|r|t|b])

10 Sense Body

The following information is sent automatically to every client every sense_body_step milliseconds.

	(sense_body  TIME 
	  (view_mode QUALITY WIDTH)
	  (stamina STAMINA EFFORT)
	  (speed AMOUNT_OF_SPEED)
	  (head_angle RELATIVE_HEAD_ANGLE)
	  (kick KICK_COUNT)
	  (dash DASH_COUNT)
	  (turn TURN_COUNT)
	  (say SAY_COUNT) 
	  (turn_neck TURN_NECK_COUNT))

11 Player Actions

(turn Moment) Change the direction of the player according to Moment.
(turn-neck Angle) Adds Angle to the clients neck angle.
(dash Power) Increases the velocity of the player in the direction it is facing by Power*dash_power_rate.
(kick Power Direction) Kick the ball with Power in Direction if the ball is near enough.
(move X Y) Move the player to the position (X,Y). This command is available only in the before_kick_off mode, and for the goalie immediately after catching the ball (see the catch) command.
(catch Direction) Tries to catch the ball in direction Direction.
(say Message) Broadcast Message to all players.
(change_view ANGLE_WIDTH QUALITY) Change angle of view cone and quality of visual information.
Discrete actions are received at any time. Every simulator_step (100ms) the simulator updates the world model using these inputs. Only one action per agent is accepted.

12 Stamina

Each player has its own stamina. There are three relevant parameters.
stamina: used up when dashing and replenished slightly. Stamina increases slightly every cycle.
effort: determines the effectiveness of dashing.
recovery: controls how much stamina is recovered each cycle.
The player can dash only with Power lower than the current stamina. The stamina decreases by the Power.

13 Reasons for Developing Biter

For students to spend their time dealing with issues of agent coordination, cooperation, and emergent behaviors, but without completely sacrificing performance.
Biter does not provide tournament-level performance, but it would not be hard to extend it to do so.
To enable students to explore both reactive and goal-driven (BDI) architectures, and everything in between.
To provide students with a basic framework and avoid the dreaded if-then-else statement with 40 else-if parts and a nesting level of up to 10.
To provide help in debugging. This is minimal at the moment. A logging facility would be nice.

14 Biter History

Spring 2000: First use of Robocup in Introduction to Multiagent Systems class. Students built almost everything from scratch. Most of the time was spent on building and maintaining a world model with absolute coordinates. Paul Buhler implements the first version of Biter for his project. This version already includes the world model.
Shaun Wood works on it during the summer 2000, adding low-level functions for finding players in view cone, intercepting ball, etc., as well as a graphical debugging tool.
Fall 2000: First use of Biter in the class is successful. While the system is in use José Vidal releases version 2.0 which implements the Generic Agent Architecture. Later he getts rid of the multiple threads, which greatly improves performance.
During the summer of 2001 Hrishikesh Goradia added some more behaviors.
Fall 2001: First use of new version. Results in conclusion.

15 Biter's World Model

Our design was heavily influenced by The CMUnited-98 Champion Simulator Team. [1]
Biter receives see commands from the soccerserver and parses them.
Biter maintains a WorldModel which has the absolute location of every object on the field that the agent can or has seen recently.
Static objects are read in at startup.
First, the closest line and flag are used to determine the player's absolute location, then the location of all other objects is deduced from it. Their certainty is set to one.
If the ball is not seen then its updated using dead-reckoning from its previous velocity. The certainty about its location is reduced. When the certainty reaches zero it is removed.
Player positions can be updated the same way.
User must decide how fast to forget (reduce phantom objects).

16 Architecture

An agent is built by:
1. Creating all the desired behaviors.
2. Deciding which other behaviors a behaviors inhibits.
3. Deciding which situations every behavior canHandle.
4. Deciding how long each behavior will be busy. This is forever for permanent behavior.
5. Adding all the behaviors to the ActivityManager.

17 Conclusions

The class of Fall 2001 used it for their final project, started at the midterm.

5 teams:

	Betir	Samurai	Kar	China
Samurai	4, 6
KAR	6, 10	5, 6
China	1, 8	7, 0	3, 4
Sachin	0, 18	0, 10	2, 1	7, 1

Low scores reflect even matching.
Final behaviors were complex: zones, single passes, pass sequences.
Agent architecturs were more organized and still showed creativity.
Boundaries and fouls remained largely ignored (coding for the common case).
Some deadlocks still appeared, altough much less common.
Future work:Hrishikesh Goradia is working on making behaviors into Java Beans. If successful this would allow use as project in undergraduate class.

URLs

The CMUnited-98 Champion Simulator Team., http://jmvidal.cse.sc.edu/library/stone98a.ps

27 February 2002, 02:00PM