Swarm Vacuum Cleaners 2010

Project Description

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, complex maps.

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 independent 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.

Approach

Office Map

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%.

Results

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)

Software

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:

http://www.dangrossman.info/cs511/videos.zip

References

Brooks, R. A. (1991b). Intelligence without representation. Artificial Intelligence, 47:139–159.