Land mines are a real problem. In 1993 alone, 100,000 land mines were picked up and 2.5 million land mines were placed on the ground, mostly in areas of eastern Europe (especially Bosnia) and southeast Asia. Demining is a dangerous and costly operation but robots can pinpoint the location of mines, bypassing a significant portion of the danger and cost to people. The Robotic Sensor Based Planning Lab, in collaboration with Mark Schervish, professor of Statistics, is actively working on land and sea demining.

Currently, inexpensive mine hunting robots have recourse only to simple algorithms. These algorithms either direct the robot to randomly move about or use rule-of-thumb heuristics that operate only in simple environments, such as areas that do not contain any obstacles. These approaches have the obvious drawback of not guaranteeing to pass a mine detector over all points in a target region. This is tantamount to using a highly faulty detector. Even if tolerating lack of completeness were an option, randomized approaches are grossly inefficient when efficiency is measured in terms of area covered per unit time.

To ensure complete coverage, this work employees a cellular decomposition, which divides the target region into subregions, called cells, such that simple back-and-forth motions, like that of an ox plowing a field, suffices to cover the cell. The planner achieves complete coverage simply by ensuring that the robot identifies and visits each cell in the region. Prior work includes developing a decomposition called the boustrophedon decomposition and this effort has developed a procedure to implement the boustrophedon decomposition in an unknown environment, i.e., allow for coverage of unknown regions.

Probabilistic planner technology can significantly extend the capabilities of current sensors in demining applications. In many situations time may not permit covering a target environment completely. However, if the planner has access to a probabilistic map of mine locations, it can guide opportunistically the robot. For example, the planner might direct the robot to sweep first the cell most likely to contain mines. After reaching a time limit without encountering a mine, the planner could then postulate that the cell is mine-free and direct the robot to another cell. Using a priori information can also solve the dual problem — lane clearing. So, instead of finding regions of high mine concentrations, this method could find sparsely mined regions that allow safe passage.

All robotic mine hunting operations face one critical challenge: positioning, which is sometimes termed navigation. This work provides a powerful alternative to GPS and transponder systems. by supplying two approaches to address the positioning problem while covering large-scale regions: algorithmic (software) and technological. The boustrophedon decomposition solves this problem by automatically encoding environmental characteristics that allow the robot to correct internal positioning errors. Each cell in the decomposition has a characteristic or sensor signature, that may or may not be unique to the cell. Adjacent cells share an edge between them. By understanding the adjacency relationship among cells, the robot can locate itself.

We also developing technological-based approaches for positioning and implementing these approaches on an outdoor mobile robot that we are developing in concert with the Naval Explosive Ordnance Division We are developing two systems: one using a linear encoder and the other a camera that looks at well-marked posts. A linear encoder is nothing more than fishing wire on a high-precision wheel. The wire is fastened to a post. We use two of these wheel-wire systems with posts that are a fixed and known distance apart. This system will constitute the first out-door mobile robot that accurately covers an unknown space, on the order of 100 by 100 feet and is far less expensive and more accurate than GPS.

Our funding agents are interested in building a fleet of inexpensive robots so that the cost of losing one robot is minimal. Although their prototype robots were designed to follow a pseudorandom path, we believed that we could build our knowledge of advanced coverage techniques into similarly low-cost robots. To demonstrate this ability, we began construction of our demining robot. The first prototype, designated Finder, uses a simple differential drive mechanism with two castors at the rear; the next version, Slugger, also uses a differential drive with many improvements to the robot design.

Finder carries 16 ultrasonic sensors for obstacle detection and avoidance and a positioning device for coverage. Ultrasound was chosen over infrared for collision detection as Finder must operate outside, where the Sun saturates all infrared sensors. For mine detection, we will equip Finder with a standard metal detector. This may seem a naive choice for the most safety-critical sensor on the robot, but as our focus is on path planning and coverage, we feel justified in leaving more sophisticated mine detectors to others. Finder is in any case upgradeable as improved sensors are developed.

The obstacle sensors, motors, and localization are driven by a set of embedded computers on board Finder. A Pentium single-board computer (SBC) running a custom Linux distribution provides high-level control of the robot, communicating via standard RS-232 serial lines with two Motorola 68HC16 slave microcontrollers. One microcontroller drives the sonar and buffers the distance-to-object values returned by the sonar board; the other handles low-level motor control and servoing (using feedback from the positioning system to follow a specific trajectory). A second Pentium SBC is used by the visual localization system.