Implementation and evaluation of a collision-avoidance navigational algorithm on a mobile robot

by Woolley, Eileen K.

For my thesis, I implemented and evaluated the VFH fast obstacle-avoidance navigational algorithm on UVA’s mobile robot, Marcus. To do this, I worked with another student, Matthew Davidson, who wrote the part of the program that creates a Cartesian grid of the environment about the robot and then smoothes the grid into a polar histogram. I wrote the part of the program that used the smoothed polar histogram to determine a steering direction for Marcus. Also, I wrote the control for the entire process. First, we interpreted the ambiguous description of the VFH algorithm into specifications. From the specifications, we decided exactly how to break up the program and decided upon data structures to use throughout the program. Once we decided how the program would communicate, we wrote and tested our parts separately. Integration involved resolving unforeseen conflicts. When the program was unified, we tested it on the robot simulator to avoid destroying the robot with unanticipated glitches. During this simulation phase, we determined that there are many inherent flaws with the world representation used with this algorithm. Carefully monitoring each run, we tested our implementation directly on Marcus. The final step to my thesis was the evaluation phase. The first result was that the definition for VFH was ambiguous, which caused some problems in the design and implementation phases. Also, the corporate literature pertaining to Marcus and its simulator was misleading and unsuitable in some cases, making it very hard to work with. The algorithm worked on the simulator in some cases; however, inherent problems with the VFH approach prevented success in many other cases. v