A group of terrorists has stormed into an office building and taken an unknown number of people hostage. They have blocked the entrances and covered the windows. No one outside can see how many they are, what weapons they carry or where they are holding their hostages. But suddenly a SWAT team bursts into the room and captures the assailants before they can even grab their weapons. How did the commandos get the information they needed to move so confidently and decisively?
The answer is a team of small, coordinated robots. They infiltrated the building through the ventilation system and methodically moved throughout the ducts. Some were equipped with microphones to monitor conversations, others with small video cameras, still others with sensors that sniffed the air for chemical or biological agents. Working together, they radioed this real-time information back to the authorities.
This is roughly the scenario that the Defense Advanced Research Projects Agency (DARPA) presented to robotics researchers in 1998. Their challenge was to develop tiny reconnaissance robots that soldiers could carry on their backs and scatter on the floor like popcorn. On the home front, firefighters and search-and-rescue workers could toss these robots through windows and let them scoot around to look for trapped victims or sniff out toxic materials. For now, these scenarios remain well beyond the state of the art. Yet the vision of minirobots has captured the attention of leading robot designers. Rather than concentrating on a few large platforms bristling with sensors (like Swiss Army knives on wheels), the focus these days is shifting toward building fleets of small, light and simple robots.
In principle, Lilliputian robots have numerous advantages over their bulkier cousins. They can crawl through pipes, inspect collapsed buildings and hide in inconspicuous niches. A well-organized group of them can exchange sensor information to map objects that cannot be easily comprehended from a single vantage point. They can come to the aid of one another to scale obstacles or recover from a fall. Depending on the situation, the team leader can send in a bigger or smaller number of robots. If one robot fails, the entire mission is not lost; the rest can carry on.
But diminutive robots require a new design philosophy. They do not have the luxury of abundant power and space, as do their larger cousins, and they cannot house all the components necessary to execute a given mission. Even carrying something as compact as a video camera can nearly overwhelm a little robot. Consequently their sensors, processing power and physical strength must be distributed among several robots, which must then work in unison. Such robots are like ants in a colony: weak and vulnerable on their own but highly effective when they join forces.[break] Whegs, Golf Balls and Tin Cans
RESEARCHERS HAVE TAKEN various approaches to the problems of building robots at this scale. Some have adopted a biological approach to mimic the attributes of insects and animals. For example, robot designers at Case Western Reserve University have developed a highly mobile platform modeled after a cockroach. It uses a hybrid of wheels and legs (“whegs”) to scoot across uneven terrain. A team from the University of Michigan at Ann Arbor has come up with a two-legged robot with suction cups at the ends of its articulated limbs that allow it to climb walls, much like a caterpillar.
Biology has inspired not only the physical shape of the robots but also their control systems. Roboticists at the Massachusetts Institute of Technology have invented robots the size of golf balls that forage for food in the same fashion as ants. They use simple light sensors to express “emotions” to one another and to make decisions collectively. This type of research takes its cue from the work of famous robot scientist Rodney A. Brooks. In the behavior-based control algorithms that he pioneered, each robot reacts to local stimuli. There is no central plan, no colonel commanding the troops. Instead the team's action emerges as a consequence of the combination of individuals interacting with one another. As innovative as this approach is, many problems remain before it can bear fruit. Deliberate missions require deliberate actions and deliberate plans—something that emergent behavior cannot reliably provide, at least not yet.
On the more deliberate side, researchers at the University of Minnesota have developed scouts, robots that can be launched like grenades through windows. Shaped like tin cans, these two-wheeled devices are equipped with video cameras that allow them to be teleoperated by a controlling user. Similarly, PARC (formerly known as Xerox PARC) in Palo Alto, Calif., has created a highly articulated snake robot that can be guided via remote video by a user. It literally crawls over obstacles and through pipes. Like the scouts, though, these robots currently lack sufficient local sensing and must rely on a human operator for decision making. This handicap makes them unwieldy for deployment in large numbers.
A few small robot platforms have become commercially available. Khepera, a hockey-puck-size robot developed in Switzerland, has become popular among researchers interested in behavior-based control. Hobbyists, too, are experimenting with the technology. Living Machines in Lompoc, Calif., puts out a tiny programmable robot known as Pocket-Bot. Along the same lines, Lego Mindstorms, an extension to the popular Lego toy bricks, allows the general public to build and operate simple robots. They are being used in science projects and college contests. But the sensing and control for these commercial designs remain extremely rudimentary, and they lack the competence for complex missions.[break] Power Shortage
AT CARNEGIE MELLON UNIVERSITY, the emphasis is on flexibility. We built a team of about a dozen “millibots,” each about five centimeters on a side. This is the scale at which we could still use off-the-shelf components for sensing and processing, although we had to custom-design the circuit boards and controllers. Each robot consists of three main modules: one for mobility, one for control and one for sensing. The mobility module sits on the bottom. Its two motors drive treads made from small O-rings. The present version can move across office floors and rugs at a maximum speed of about 20 centimeters a second, or about a sixth of normal human walking speed. As we develop new mobility platforms, we can snap them into place without having to redesign the rest of the robot.
The middle module provides processing and control. The current design contains an eight-bit microcontroller akin to the ones used in personal computers of the early 1980s. Though no match for modern desktop computers, these processors can still perform real-time control for the robot. The sensing module, which sits on top, includes sonar and near-infrared sensors for measuring the distance to nearby obstacles; a mid-infrared sensor (like those used in motion detectors) for detecting warm bodies; a video camera for surveillance; and a radio modem for communicating with other robots or the home base.
Perhaps the most severe limitation on these and other small robots is power. Batteries are bulky and heavy. They do not scale well: as its size is reduced, a battery reaches a threshold at which it cannot supply the power needed to move its own weight. The two rechargeable NiMH cellular-phone batteries on our millibots take up about a third of the available space. They provide enough power for only a limited array of sensors and a run time of between 30 and 90 minutes, depending on the complexity of the mission. Larger batteries would increase the run time but crowd out necessary components. Small-robot design is all about compromise. Speed, duration and functionality compete with weight, size and component availability.
To deal with these constraints, we have adopted two design methodologies for the millibots: specialization and collaboration. The former means that a robot is equipped with only enough sensing and processing for a specific task, allowing it to make optimal use of the available room and power. In a typical mission, some millibots are charged with making maps of the surroundings. Others provide live feedback for the human operator or carry sensors specific to that mission. To get the job done, the robots must collaborate.[break] Where Are We?
ONE VITAL TASK that requires collaboration is localization: figuring out the team's position. Larger robots have the luxury of several techniques to ascertain their position, such as Global Positioning System (GPS) receivers, fixed beacons and visual landmark recognition. Moreover, they have the processing power to match current sensor information to existing maps.
None of these techniques works reliably for midget robots. They have a limited sensor range; the millibot sonar can measure distances out to about two meters. They are too small to carry GPS units. Dead reckoning—the technique of tracking position by measuring the wheel speed—is frustrated by their low weight. Something as seemingly inconsequential as the direction of the weave of a rug can dramatically influence their motion, making odometry readings inaccurate, just as a car's odometer would fail to give accurate distances if driven on an ice-covered lake.
So we have had to come up with a new technique: a miniaturized version of GPS. Rather than using satellites, this technique utilizes sound waves to measure the distances between robots in the group. Each millibot is equipped with an ultrasonic transducer in addition to its radio modem. To determine distance, a millibot simultaneously emits a radio pulse and an ultrasonic signal, which radiate in all directions. The other robots listen for the two signals. The radio wave, traveling at the speed of light, arrives essentially instantaneously. The sound, moving at roughly 340 meters a second, arrives a few milliseconds later, depending on the distance between the robot sending the signal and the robot receiving it. A cone-shaped piece of metal on the sensing module reflects ultrasound down onto a transducer, allowing the robots to detect sound from any direction. The process is analogous to measuring the distance to an approaching storm by timing the interval between lightning and thunder.
By alternating their transmitting and listening roles, the robots figure out the distances between them. Each measurement takes about 30 milliseconds to complete. The team leader—either the home base or a larger robot, perhaps the mother bot that deployed the millibots—collects all the information and calculates robot positions using trilateration. Trilateration resembles the better-known technique of triangulation, except that it relies on distances rather than compass headings to get a fix on position. In two dimensions, each range estimate indicates that another robot lies somewhere on a circle around the transmitting robot. The intersection of two or more circles marks the potential location of other robots [see box on page 37]. The algorithm finds the arrangement of robots that best satisfies all the circle intersections and range measurements.
One thing that complicates the procedure is that more than one arrangement of robots may match the data. Another is that range measurements are prone to error and uncertainty. Ultrasonic signals echo off floors and walls, creating ambiguity in the distance readings. In fact, depending on the geometry, wave interference can cause the signal to vanish altogether. For this reason, we developed an algorithm that combines the ultrasonic ranging with dead reckoning, which, despite its problems, provides enough additional information to resolve the ambiguities. The algorithm estimates the measurement error and computes the set of robot positions that minimizes the overall error.
The advantage of this localization method is that the millibots do not need fixed reference points to navigate. They can enter an unfamiliar space and survey it on their own. During mapping, a few selected millibots serve as beacons. These robots remain stationary while the others move around, mapping and avoiding objects while measuring their position relative to the beacons. When the team has fully explored the area around the beacons, the robots switch roles. The exploring robots position themselves as beacons, and the previous set begins to explore. This technique is similar to the children's game of leapfrog, and it can be executed without human intervention.[break] Chain of Command
OBSTACLES PRESENT small robots with another reason to collaborate. By virtue of its size, a little robot is susceptible to the random clutter that pervades our lives. It must deal with rocks, dirt and loose paper. The standard millibot has a clearance of about 15 millimeters, so a pencil or twig can stop it in its tracks. To get around these limitations, we have come up with a newer version of the millibots that can couple together like train cars. Each of these new millibots, about 11 centimeters long and six centimeters wide, looks like a miniature World War I–style tank. Typically they roam around independently and are versatile enough to get over small obstacles. But when they need to cross a ditch or scale a flight of stairs, they can link up to form a chain.
What gives the chain its versatility is the coupling joint between millibots. Unlike a train couple or a trailer hitch on a car, the millibot coupling joint contains a powerful motor that can rotate the joint up or down with enough torque to lift several millibots. To climb a stair, the chain first pushes up against the base of the stair. One of the millibots near the center of the chain then cantilevers up the front part of the chain. Those millibots that reach the top can then pull up the lower ones [see box on opposite page]. Right now this process has to be remotely controlled by humans, but eventually the chain should be able to scale stairs automatically.
Already researchers’ attention has begun to turn from hardware development toward the design of better control systems. The emphasis will shift from the control of a few individuals to the management of hundreds or thousands—a fundamentally different challenge that will require expertise from related fields such as economics, military logistics and even political science.
One of the ways we envision large-scale control is through hierarchy. Much like the military, robots will be divided into smaller teams controlled by a local leader. This leader will be responsible to a higher authority. Already millibots are being directed by larger, tanklike robots whose Pentium processors can handle the complex calculations of mapping and localization. These larger robots can tow a string of millibots behind them like ducklings and, when necessary, deploy them in an area of interest. They themselves report to larger all-terrain-vehicle robots in our group, which have multiple computers, video cameras, GPS units and a range of a few hundred kilometers. The idea is that the larger robots will deploy the smaller ones in areas that they cannot access themselves and then remain nearby to provide support and direction.
To be sure, small robots have a long way to go. Outside of a few laboratories, no small-robot teams are roaming the halls of buildings searching for danger. Although the potential of these robots remains vast, their current capabilities place them just above novelty—which is about where mobile phones and handheld computers were a decade or two ago. As the technology filters down from the military applications and others, we expect the competence of the small robot to improve significantly. Working as teams, they have a full repertoire of skills; their modular design allows them to be customized to particular missions; and, not least, they are fun to work with.[break] THE AUTHORS
ROBERT GRABOWSKI, LUIS E. NAVARRO-SERMENT and PRADEEP K. KHOSLA began working together on the millibot project in the summer of 1999. Grabowski is a principal investigator at the MITRE Corporation. He served eight years in the U.S. Navy working with nuclear reactors and received a Ph.D. from Carnegie Mellon University. He has tinkered with electronics all his life and still enjoys playing with Legos and taking apart old VCRs. Navarro-Serment is a project scientist with the Robotics Institute at Carnegie Mellon, where he received his Ph.D. His background is in industrial automation and control systems; he used to head the electrical engineering department of the Guadalajara campus of the Monterrey Institute of Technology and Higher Education in Mexico. He is an avid amateur astronomer. Khosla is dean of the College of Engineering at Carnegie Mellon and is a member of the National Academy of Engineering. He made his name in robotics by developing the first direct-drive manipulator arms, which are now used in most automated factories. The authors thank the rest of the millibot team—Chris Paredis, Ben Brown, Curt Bererton and Mike Vande Weghe—for their invaluable contributions.