Crunch is a two-wheeled actively gyro-stabilized robot. It was my third robot, built over a period of only a few weeks during December 2003 - January 2004, also known as winter break during my junior year at Brown. The round decks are 6" diameter, the wheels are 4" diameter, and it is about 12" tall. Crunch was inspired somewhat by
but designed with much greater sensor payload as I had navigation in mind. It was named in honor of a sound that it frequently made during early development.
Crunch was built out of aluminum angle and bar stock and 3/8" plywood. Most of the mechanical work was done with a scroll saw and a cheap craftsman drill press, which, at the time, were my most sophisticated tools.
The drive motors are mounted under the lowest level and geared 1:1 to the wheel shafts. The shafts are supported by ball bearings sandwiched between several layers of 1/8" thick aluminum. The motors did not have encoders when I bought them; these were retrofitted; note the covers over the backs of the motors made from 35mm film canisters. The design is somewhat similar to
DPA's homebrew encoders
The onboard electronics were soldered by hand from large prototype boards, trimmed to fit on the 6" decks. The bottom level contains all the power systems and balancing control; the mid level contains the sensor systems; the top level contained the main computer, later replaced by a radio link to an offboard computer.
Crunch was powered by a battery pack made of 24 AA-size nickel-metal-hydride cells. It was hung directly under the top deck in order to increase the height of the center of gravity. This pack has a voltage somewhere in the range of 29-35 volts depending on charge state. Even small NiMH batteries are capable of surprising output currents.
The bottom circuit board includes the motor drivers, 5v power supply, charging circuit, and a AVR MEGA32 which controls them and balances the robot. The motor drivers are two LMD18200 integrated MOSFET H-bridges. The 5v power supply is an LM2576 switching unit, capable of supplying far more 5v current than the onboard systems require. The charging circuit is a simple DC-DC up-converter (the input is a 24v brick, which needs to be boosted to charge the batteries) controlled by the AVR according to battery voltage and current.
The second level contains a 40KHz sonar tranceiver multiplexed to 8 transducer pairs mounted at 45°ree; angles around the perimeter. The sonar is implemented with another AVR MEGA32.
The top deck originally contained a 16MHz DS80C320 microcontroller, which is essentially an improved 80C31. It could access 8K of EPROM containing a bootloader, 56K of Flash ROM containing the main program, and 64K of SRAM. It communicated with the drive and sensor boards via I2C.
Later, Crunch was retrofitted with a ring of 8 Sharp GP2D12 Infra-red rangefinders, mounted between the middle and top levels and wired to the sensor board. Also, the 8031 main computer was replaced with a 900MHz spread-spectrum radio modem so that higher level functions could be implemented by a (much more powerful) offboard computer. This was Crunch's "final" look.
The most basic way a robot can map its environment is to integrate its sensor readings on a grid using simple dead reckoning to determine its location. In other words, since the robot is aware of the movement of its wheels, if it assumes that the measurements are exact, the wheels are perfectly shaped, the wheels never slip, and the floor is perfectly planar, and it knows where it started, it always knows exactly where it is. Further, if it assumes, every time it gets a sonar return, that there was nothing closer than the measured distance but definitely something at exactly the measured distance, it can draw a map. Above is a map generated with sonar data (this was before the upgrade) by driving around my old dorm room at Brown. (The grid is 1M)
Obviously those assumptions are pretty optimistic. While they worked ok during a short trip inside one room, over time the dead reckoning fix deteriorates. This is particularly problematic if you return to where you started and the dead reckoning fix thinks you're somewhere else. This is what happens if instead of staying in the room Crunch is driven down the hall and into the kitchen. (In case you were wondering, Metcalf 304 is a pretty sweet room to get.) The room "adjacent" to where Crunch is shown is indeed the same room, despite dead-reckoning's naive guess at location. Clearly, something must be done.
Time to get clever. At this point, the sonar has been augmented with the infra-red sensors. Sonar and infra-red are nicely complementary: infra-red gives you an exact distance in a certain direction but misses anything even a few degrees off to the side; sonar is a wider beam so doesn't produce as accurate maps, but on the other hand, is less likely to miss something entirely. They are both integrated according to rough models on a map. (see upper-left of the above picture) Unlike before, though, it's not a global uniform grid; it's only a local map of a meter or so around the robot.
Every time the robot thinks it has moved 1m, it examines its local map and extracts only what it believes to be the observed walls, i.e. boundaries between places it thinks are clear and places it thinks are occupied. It stores these curves and links them to the last location where it made such a record according to how it thought it moved between the two locations.
The local maps are not perfect, but no matter: they are not subject to accumulated error. The movements between them, however, are another story: the errors in those add up over time. If the movements can be corrected, though, the map becomes consistent. This is done using a technique called particle filtering. Basically, the computer stores a large collection of guesses at the errors in each movement. When the path crosses itself, it measure how inconsistent the observations are with each other. If a guess results in a consistent map, i.e. walls being in the same place, it gets a good score. If the guess results in things not making any sense, it gets a bad score. The computer constantly throws out poorly scoring estimates and generates variants of well scoring estimates. The above map was generated by driving twice around a loop about 50m long. The squiggles on the left show some of the orientation errors over the total drive, the thick blue one being the best estimate which is generating the map. (Orientation errors are much more important to correct as they cause huge position errors over time.)
This algorithm is known as FastSLAM, though my implementation of it is extremely hacky due to the fact that Crunch is a really poor platform compared to what most researchers use. (It can't handle nearly as complex an environment as many robots running FastSLAM can.)
Here's another map; this was on the 4th floor of the Watson CS building at Brown.
Crunch hasn't seen action since I left college and is probably in need of some severe repairs. Recently, though, there is a new balancing bot on the drawing board...