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.

In demining, a robot must pass a mine-detecting sensor over all points in the region that might conceal a mine. To do this, the robot must traverse a carefully planned path through the target region. Conventional path planners are inadequate for demining because they only produce paths between two points and pay no attention to the intervening area. Coverage-path planning, as its name suggests, specifically emphasizes the space swept out by the robot's sensor. Integrating the robot's footprint (detector range) along the coverage path yields an area identical to that of the target region.

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.

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 (pictured above). The first prototype, designated Finder, uses a simple differential drive mechanism with two castors at the rear; the next version will be somewhat more sophisticated.

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.

In order for any robot to work in a large scale environment (in our case up to 50 meters on a side), it must know its location accurately. Without this knowledge, a robot cannot perform complete or intelligent probabilistic coverage, making random coverage and similarly unsophisticated algorithms the only options. To address the problem of acquiring accurate position knowledge on a mobile robot, we have developed several novel positioning technologies: linear encoder-based, range-based with fixed landmarks, and range-based using the topology of the region.

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 (details); 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 (details).