We constructed and programmed a robot capable of moving through a semi-arbitrary maze to locate and extinguish a candle. The primary objectives of this project were building the robot and devising candle-finding and candle-extinguishing strategies. The secondary objectives of this project were to introduce us to both the Handyboard platform (in particular) and to implementation issues in robotics (in general).
This project had been done many times in years past. Many solutions from previous years were mentioned in class. These included a variety of both candle-finding and candle-extinguishing strategies.
In a broader sense, this project touches on many of the fundamental problems of robotics. Thus, we were faced with challenges of:
The extinguishing problem is difficult for a variety of reasons, both mechanical and theoretical. On the mechanical side, the robot must navigate the maze without becoming stuck or falling apart — this will necessitate sturdy construction, intelligent placement of sensors, and few parts that are liable to get caught on something. On the theoretical side, the robot must use its sensors to find the flame in a variety of mazes without entering an infinite loop; ideally the strategy it employs will lead it to the candle in a minimal amount of time. All this must be accomplished using the available sensors, motors, Legos, and Handyboard.
Many other robots have been constructed for various tasks, including extinguishing bots by past CS154 teams. Some strategies for finding the candle include wall following or random walking until the candle is seen, then use of light sensors to get close enough to extinguish it; once the candle is found, it can be snuffed out, put out by a fan, shaving cream, or knocking it over (all of which have their own problems and benefits).
Our solution will be on a specific application of the general extinguishing problem. We will assume a maze built with entirely right angles, and a reasonably smooth ground surface such as carpet or tiling. We will assume walls that are at least high enough to trigger all of our sensors, as well as high enough to conceal the flame from any but a direct view. We will assume the flame is a candle mounted at a height in line with our extinguishing method, and that there is nothing else in the maze other than the candle and walls.
A more "realistic" extinguishing robot might employ a sophisticated subsumption system to determine behaviors [Brooks]. While we are not going that far, in a sense we will be using a two-level subsumption system: the robot will, when not in sight of the candle, wall-follow through the maze. When it sees the candle, however, its candle-finding routine will be subsumed by its candle-extinguishing routine.
It would also be possible (although not within the time-line of this project) to build a robot that has a far more sophisticated world model. It could wander around a the maze while mapping it and keeping track of its location using visions sensors. In a sense, this would be similar to the Polly System developed by the MIT Artificial Intelligence laboratory to give tours to visitors [Horswill]. The higher level behaviors, putting out fires, could be triggered by vision sensors, infrared, or smoke detectors, among other things, much like Polly's tour-giving behavior was triggered by seeing people's legs. Once in this mode, the robot would seek out the fire as quickly as possible and attempt to put it out using a fire extinguisher or some other method.
Conceptually, we divided this task into two parts: finding the candle and extinguishing the candle. A summary appears in the following picture. The text below explains in more detail, while the code here is, of course, the most comprehensive (but the least readable).
To find the candle, we employed a pseudo-wall-following strategy. By following the walls of the maze, we will eventually be able to find the candle, except in certain pathological cases. However, we found that true wall-following was difficult given the limitations of the Lego sensors. There were three sensors on each side of the robot: one in front, pointing forward; one in the front, pointing to the side; and one on the side, also pointing to the side. When the robot bumped into something head-on, it would back up and turn away from the object. If it felt something on it's front side, it would turn about 20 degrees away from it, and if it felt something on its side, it would turn about 10 degrees away.
It should be noted that wall-following would be considerably simplified by improved sensing. For example, if we had a camera which could view the entire area (like [Vaughan]), the task would be almost trivial. Similalry, if we had equipped the bot with side sonar, like DERVISH [Nourbakhsh], it would be much easier to detect walls. However, even given these improved sensors, using Monte Carlo Localization [Dellaert] would have been overkill, and probably have required more processing power than our Handyboard could provide.
Occasionally, the robot would stop navigating and perform a 360 degree visual scan for the candle (i.e., a sufficiently bright light). If it did not find the candle, it would continue navigating. If it did, however, it would enter extinguish mode.
(One major difficulty we ran into is what to do if the robot bumps into a wall while it is spinning around looking for the candle. While we felt it would be ideal if it could move away from the wall and search again, it was found that this was too difficult, especially given that the robot could not accurately judge how far it had turned. In the end, if it bumped into something, it would turn the approximate distance back to where it started turning and continue navigating.)
Once the robot was in extinguish mode, it would advance slowly towards the candle, waiting for it to get close enough (bright enough) so that its fan would be useful. Unfortunately, we found that on lower speeds, the imbalance in our motors was exacerbated, and the robot would tend to drift off course. This was rectified by having the robot re-acquire the candle after having moved towards it for a period of time. The re-acquiring involved searching a 90 degree arc for the brightest point, rather than the entire 360 degrees.
Once the robot was very close to the candle, it would turn on its fan. In addition, it would move much more slowly, so as to avoid knocking the candle over. Originally, it left its fan on, and periodically checked to see if the candle was out. However, we found that the candle would be dim enough that it would be below the threshold for "lit-ness", but still be lit. This resulted in the robot declaring that the candle was out and turning off its fan — after which, of course, the candle would flare up again. We solved this problem in two ways. First, after 5 seconds, we would turn off the fan, wait for 1 second, and re-acquire the candle (in the same way described above). We would then see if the candle was out. This pause would allow the candle to flare up, if it was still lit, alerting the robot to the fact that it needed to continue blowing on it. If things were still dim after the pause, then we assume that the candle is truly out.
We found the robot to be able to put out the candle more often than not. The primary failure was, as mentionned, falsely believing the candle was extinguished. The other issues were exiting the maze and, less commonly, failing to detect the candle and consequently knocking it over.
| Photo Gallery | |
|---|---|
| Shiny new bumper. Before, we had dual rods sticking out for left- and right-front bump sensors. Unfortunately, they tended to get stuck on things. Thus, this smooth bumper. |
 |
| Come back, robot! If the maze has an exit, it's not unlikely that the robot will leave the maze, never to return... |
 |
| Searching... The robot is spinning around, looking for the candle. At that distance, it is unlikely that it will find it. |
 |
| Closer... The robot has seen the candle, and is moving slowly towards it. It will re-acquire the candle periodically, to compensate for its inability to move simultaneously straight and slowly. |
 |
| Success! The robot has extinguished the candles. (We found that the additional brightness of having two candles aided our sensors enough to outweigh the increased difficulty of extinguishing them.) |
 |
Overall our system performed fairly well. We encountered many small challenges to its functionality, but were able to overcome these problems using a variety of hardware and software approaches. (Compared to the challenges faced by the Stanford Cart [Moravec], we consider ourselves lucky!) Modifying the turning amounts caused by various bump sensors eliminated much of the problem of getting stuck in loops, while adding a bumper helped the robot avoid getting its front bump sensors stuck while turning. Various additions to the extinguishing functionality increased the chance that the robot would successfully put out the candle when it was found.
Though our robot can usually put out the candle given enough time, a few areas could still be significantly improved. Mainly, the searching method of the robot could be much more robust. Adding sensors like sonar, a compass, or GPS would allow the robot to map its environment, and find the candle much more efficiently. Secondly, once the candle is found, a stronger fan would help ensure that the robot is able to put it out.
Working on this project has suggested that further investigation into locating and mapping environments would be beneficial. In addition, its performance would be improved by improving some of the hardware — specifically, making the motors of equal power and improving the fan's performance.