The times they are a-changin’.
This post seems to be older than 14 years—a long time on the internet. It might be outdated.
Go out on the web and find a robot system, real or vitual, that uses one of these techniques. Describe the robot, the implementation of the technique, and both its benefits and drawbacks (i.e., what’s good about the system and what needs work).
The Cye Personal Robot is a commercially available, two-wheeled, autonomous robot. Cye’s center of gravity is placed below the wheel axis, which allows it to be inherently stable and does not require the use of accelerometers or gyroscopes to maintain balance. In fact, the only sensors that Cye uses are wheel encoders. By using data gathered from the encoders, Cye can determine how far it’s traveled and if it’s hit an obstacle. Cye is powered by a 16-bit 16Mhz High Speed I/O Microprocessor (Long n.d.), similar to that of a HC9S12. Additionally, Cye has a radio uplink to a remote PC to perform higher level functions, such as allowing a user to input a map.
Cye uses a combination of techniques to path plan, although the “underlying structure of the planner incorporates a grid based potential field.” (Batavia and Illah 2000) Cye also uses wave-front path planning to determine a path that minimizes path length (while also factoring in traversability).
To begin, the start and goal are placed on the traversability field, which is a grid. Rather than mark a cell as obstructed or not, a traversability field allows each cell to have a range of values that go from completely occupied (and therefore completely untraversable) to unexplored (which could be traversable or not) to known free space (which is guaranteed to be traversable).
Figure 1: Traversability Grid Algorithm
Known obstacles are inserted and the field is grown using a Grassfire transform (see Figure 1), a type of Voronoi Diagram that is used for cell-based path planning methods. One thing that is important to note in this version of the grassfire transform is that the value of each cell indicates the level of traversability, not distance to the nearest obstacle (as is the case in a standard grassfire transform).
From the traversability field, a potential field is generated using a wave-front path planner with four-point connectivity. As Batavia and Illah write:
This method generates a path that is optimal in length, but tends to hug the sides of obstacles. This problem can be alleviated by ‘growing’ the obstacles by a certain amount, guaranteeing a minimum distance. However, this is unsatisfying, as occasionally, to guarantee completion, it may be necessary to take a risk and get very close to an obstacle.
Similarly, the basic wavefront approach cannot handle varying terrain types or any uncertainty in the state of the world. One method for getting around this is to tag all uncertain or unexplored areas as obstacles, and avoid them entirely. Again, this is unsatisfying, as it is worthwhile to explore new areas, if doing so could result in a significant savings in path cost.
As it turns out, using the traversability field as the input to the wave-front path planner helps to overcome the aforementioned issues and, as mentioned before, a path is created based on traversability, rather than just shortest distance. As shown in Figure 2, if a distance is long enough, a route can be plotted through an unknown territory (right image) rather than around it (left image).
Figure 2: Cye opportunistically using unexplored areas to shorten path length
Finally, the global path planning algorithm determines local check points. Cye will navigate to these known locations to help eliminate positioning error. As Batavia and Illah write:
[The] checkpoint closest to the start of the path is found, and a new path is generated from Cye’s current location to the checkpoint. Following this, a new path is generated from the checkpoint to the end goal. Then, the next checkpoint is located, and planned to. If the nearest checkpoint is actually the end goal, then we are done, and Cye moves to the final goal. If it is not, we repeat the process until the final goal is found. Although this algorithm involves additional plan generation, the overall computation time of the planner is low, so this does not add much overhead, but it greatly enhances the performance.
This three stage path planning method has proven to be very robust. In analyzing the path planner, Batavia and Illah only had three failures that required human intervention over a distance of 1100 meters. Additionally, Batavia and Illah reported that, “[there] were six collisions which did not require human intervention. In these cases, Cye was able to plan around the unexpected obstacle, and continue.”
It’s apparent that the methods Cye uses to path plan are mostly complete. The biggest issue is probably the lack of active sensors. Currently, the only way Cye knows about obstacles is through human input (via a mapping tool on the computer) or bumping into them. Cye would greatly benefit from either IR or sonic distance sensors that could be used to determine the traversability of unknown regions before actually attempting to move through the region. Another area of issue is the reliability of the shaft encoders. Currently, Cye needs to dead-reckon from checkpoint to checkpoint. Increased resolution of the shaft encoders, as well as information about the power consumption of the motors, could be used to decrease the dead-reckoning error and increase the distance between checkpoints.
Works Cited
- Batavia, Parag H., and Nourbakhsh Illah. “Path Planning for the Cye Personal Robot.” 2000. http://www.cs.cmu.edu/~illah/PAPERS/cye.pdf (accessed March 24, 2009).
- Long, Dan. Hereee are Long++’s inside peek at Cye Pictures… http://sunsmoke.org/~ldang/long/bot/cye/index.html (accessed March 25, 2009).