We are attempting to construct and program a robot capable of moving through a semi-arbitrary maze to locate a candle, and then extinguish said candle. The primary objectives of this project are building this robot and devising candle-finding and candle-extinguishing strategies. The secondary objectives of this project are to introduce us to both the Handyboard platform (in particular) and to implementation issues in robotics (in general).
This project has 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 are 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, Rodney A. Achieving Artificial Intelligence Through Building Robots). 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 timeline 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, Ian. The Polly System). 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.
To find the candle, we intend to primarily employ a wall-following strategy. By following the walls of the maze, we will eventually be able to find the candle, except in certain pathological cases. Those cases will be dealt with by further refinement of the candle-finding algorithm.
This wall-following method was chosen because it seemed the most practical. Without a sophisticated vision system, it is difficult to actually map the maze. Lacking such a map, it is difficult to undertake a systematic search — but, wall-following allows us to do this (or a close approximation of it).
To extinguish the candle, we will opt for the tried-and-true strategy, viz., using a fan. While we briefly considered using more exotic methods (compressed air rather than a fan, shaving cream as an extinguishing agent, or simply directly snuffing the candle), we believed that actually locating the candle would be more problematic than extinguishing it; thus, we should choose the simplest extinguishing method, and devote most of our energies to finding the candle. Should we finish ahead of schedule, we may attempt to revisit our extinguishing method.