So this is pretty cool. My partner and I designed a wooden robot for a course in robotics. Its purpose is to search an enclosed area for pieces of ferrous metal. Just take a look at this puppy:
My partner deserves full credit for the wooden chassis. He initially built it for a previous collaboration we did, making a robot that would follow a line drawn on the floor. Using a lathe in his garage, he custom built the chassis and wheels out of blocks of wood. We adapted this design to our metal-detecting robot.
There are two main components of this robot: the mechanism used to detect metal and the algorithm used to navigate the physical search space.
My partner deserves all the credit for building the metal-detecting apparatus. In fact, I have little beyond a theoretical understanding of how it works, but work it does. In our tests, it detected the ferrous metal every time and had few false positives. It worked so well, in fact, that it didn't detect pieces of non-ferrous metal (such as aluminum) that we placed to fool it.
In the pictures above, the circuit is encased in the middle wooden block. It was powered by a separate 9-volt battery (pictured sticking out of the middle of the robot). It had wires running from its circuitry to its main detecting mechanism at the front of the robot. You can also see on the top of the main circuitry enclosure a small white knob which we used to control the sensitivity of the detector.
The basic premise for its operation is relatively straightforward: a change in magnetic field (called magnetic flux) will induce a current in a conducting element (such as our piece of metal). That current, in turn, will affect the inducing magnetic field, changing the voltage required to power that field by a detectable amount.
In our robot, the main detecting element was a large coil of wire that generated our magnetic field. When it moved over a piece of conducting metal, it detected the interplay of magnetic fields which turned on an LED, alerting us to the presence of metal.
The problem is not unsimilar to the kind of problem a Roomba has to solve. We want to maximize our coverage of area while minimizing time. So in designing our algorithm, we based it off of the observed pattern of Roombas. The exact algorithm the Roomba uses is of course proprietary, but in observing its behavior we eventually came up with our final design.A long-exposure photograph of a Roomba cleaning a room at Signal Theorist
Our algorithm is rather simple. We assume the robot will start in the middle of the search space. It begins by turning in a complete circle (one wheel moving at full speed and the other stationary) and slowly expands its search, the stationary wheel slowly speeding up. This results in a nautilus spiral pattern.A nautilus shell by Chris 73 at Wikipedia
However, since this expanding search quickly results in gaps, we stop the spiral movement after the robot has moved a certain distance away from its start position and begin again, this time searching the gaps we missed as the first spiral expanded. Doing this four times results in an thoroughly-searched area of roughly 8 feet by 8 feet. If the robot bumps into anything at any time, it will stop, back up, turn roughly 30 degrees away from the object it hit, and head off straight regardless of what it was doing. If the robot goes straight for 8 feet without hitting anything, we assume that we are in a wide-open area and begin the spiral pattern again to maximize area covered. Otherwise, we will keep going straight and bump into things.
If at any time the robot detected a piece of ferrous metal, it ceased movement and a red LED came on before it continued its search. In our tests, the robot quickly found the majority of the pieces of metal within 8 feet of its initial position. After it bumped into something or exhausted its initial 4 spiral search, it took much longer to find the other pieces of metal in the 16 by 16 foot search space. I don't have hard numbers, but I would estimate that it would take no more than 10 minutes before it searched the entire space. For perspective, its initial 4 spiral search took about 1 minute.