Swarm Vacuum Cleaners 2010
This project is a multi-agent simulation in which Roomba robotic vacuums exhibit swarm intelligence. Each robot is completely independent and autonomous, and acts with no representation of the world it operates in. Through simple rules and limited interaction with the environment and with the other robots, the Roombas are able to explore their world and work together to vacuum unknown environments. The simulated Roombas are modeled after the real-world equivalents -- they have the ability to move forward or reverse with some turning angle, two front bump sensors, and a (top-down) simulated IR sensor to detect other robots within a short range.
The control system for each robot is modeled after Brooks' "subsumption architecture". Each robot is represented by a RobotState object, a simple class that encapsulates control and state of the robot. Its update method calls 3 other methods in sequence, which are each simple state machines with some logic and internal counter. Each machine updates a variable representing the forward or reverse speed of the motor, and one representing the turning angle of the motor. After all 3 state machines have run, these two variables are used to issue the command to the robot's motor. The effect is to allow each state machine to, if appropriate, inhibit or override the previous state machine's signals to the motor, resulting in a layered control structure with simple behaviors at the bottom and increasingly complex behaviors at higher levels.
- The Vacuum SM always tells the motor to move forward with no turn angle
- The AvoidObstacles SM checks if either of the bump sensors has been activated, or if the robot has not moved despite the motor being enabled (necessary due to simulation bugs where the robot is hitting a wall but neither bump sensor sends a signal). If so, it reverses the motor and sets an appropriate turn angle depending on which bump sensor was hit. The SM will override the Vacuum signals for multiple cycles so that the robot has time to complete its turn away from the obstacle before it resumes vacuuming.
- The RunAway SM checks if another robot is within communication range of the IR detector. If so, it attempts to move away from the other robot by generating a sharp turn and overriding other signals for several cycles.
The effect of these layered state machines is an autonomous robot that effectively covers a map without any representation of that map. The Roombas will move around the area in straight lines, turning at random angles when they hit a wall or other obstacle, resulting in eventual full coverage of the map through this random walk.
The project was implemented in the Player/Stage environment using the C++ libraries. Player/Stage and the development libraries were installed from their packages using apt-get in Ubuntu linux. I plugged into Stage's simulation engine to do some graphics rendering on top of the Stage simulation window. This allowed me to visually display the cleaning status of the simulation as it was running. The world is divided into a square meter-size grid, and at each time step in the simulation, the current position of each robot is used to place colored boxes into each grid square. The color begins at white and becomes increasingly strong shades of green as a grid square is visited by a robot.
The research portion of this project involved 6 simulations, each run approximately 5 times. The different simulations involved varying the map in which the robots vacuumed, and the range at which they could detect each other. Two maps were created - one is an open area, similar to a large room or warehouse. The other map is a floor of an office building, with hallways, multiple rooms and closet areas.
In all cases 4 robots were simulated.
- Robots in an open map, with no communication
- Robots in an office map, with no communication
- Robots in an open map, 3 meter communication radius
- Robots in an office map, 3 meter communication radius
- Robots in an open map, 6 meter communication radius
- Robots in an office map, 6 meter communication radius
As some of these simulations took over an hour of real time for a single run, I was limited by available time to about 5 runs per test, which took several days. Each simulation was run until collective coverage of the grid imposed over the map reached 90%.
The following were the average times to reach 90% coverage:
Open Map (Averages)
- No Communication: 14.9 minutes
- 3 Meter Radius: 14.1 minutes (5.4% faster)
- 6 Meter Radius: 14.5 minutes (2.7% faster)
Office Map (Averages)
- No Communication: 65.4 minutes
- 3 Meter Radius: 53.4 minutes (18.4% faster)
- 6 Meter Radius: 52.2 minutes (20.2% faster)
There is a clear and significant improvement in cleaning/coverage speed when the robots are allowed to communicate and attempt to avoid each other. Observing the final overlay on the map from each simulation, the repulsion effect leads to less time stuck in corners and bouncing off other robots in small spaces. The map has slightly more even coverage than without communication.
It is hard to say why the robots performed better with a 3 meter range than a 6 meter range in the "open" map. I attribute it, at least in part, to the fact that 6 meters is a very large radius for this small area shared by the robots. The Roombas are forced to spend a lot of time circling trying to turn away from each other only to end up near another robot, instead of performing the normal cleaning pattern.
In the office map, the communication served to prevent all the Roombas from ending up in the same room for long periods of time, which sometimes happened when no communication was allowed.
Player/Stage is a difficult environment to set up and use. Just getting Player/Stage installed, and a driver program that performed no actions working took over a day. I ran into a lot of problems due to C++ Boost libraries used by libplayerc++ being a newer version than the libraries were built with. This meant that even some example code from the Player website would not compile.
The way Player and the robot clients interact through network sockets also created significant problems. Player queues up all sensor data, from the bump sensors, to the position proxy tracking odometry, to the simulation proxy tracking the real location of the robots, as packets on the socket. If you do not read these packets fast enough, they will build up, and once the queue is full, they start getting dropped and flood your screen with warnings. I had to read from the socket at a rate of something like 50 times per second to avoid this problem. Doing so increased the CPU usage of the clients to the point that in the large office simulation, Stage was running at almost 50% of realtime. Attempting to increase the simulation rate lead to more network related problems or Player simply locking up and requiring a kill -9 after some time.
The high polling rate and capturing video at the same time meant I had to dedicate my entire system to running simulations, over an hour at a time, to do this project. It was a very involved process for a relatively simple set of experiments.
Download the files here: http://www.dangrossman.info/cs511/code.zip
- sim.cfg: Player driver for the open world simulation with 4 robots
- sim2.cfg: Player driver for the office world simulation with 4 robots
- open.world: Defines the open map and robot positions
- office.world: Defines the office map and robot positions
- map.inc: Defines generic map properties
- open.png: Open map graphic
- office.png: Office map graphic
- roomba.inc: Defines the Roomba robot (geometry and sensors)
- sim.cpp: The main driver of the simulation, which connects to Player and Stage, and instantiates the controllers for the robots
- robotstate.h: Header file for class which maintains the state and controller logic for an individual robot
- robotstate.cpp: Implementation of robot state and controller logic for an individual robot
- Makefile: Makefile that compiles sim.cpp, robotstate.cpp into an executable called sim
To run the simulation:
- Run Player (ex: player sim.cfg)
- Run the driver (ex: ./sim)
To switch between the open and the office map, you must edit sim.cpp. There are two constants at the top of the file that correspond to the size of the map. The set corresponding to one map or the other is commented out depending on which map the simulation will run on. This is necessary to maintain the cleaning status structures which depend on the map size.
Movies and Pictures
I used Camtasia Studio to capture a number of movies of the simulation in progress, and sped them up by 800% before saving. These movies can be downloaded here:
Brooks, R. A. (1991b). Intelligence without representation. Artificial Intelligence, 47:139–159.
Dan Grossman (firstname.lastname@example.org), March 2010