A rapid method for planning paths in three dimensions for a small aerial robot

This paper describes a path planning method for a small autonomous aerial v ehicle to be used for inspecting overhead electricity power lines. A comput ational algorithm is described which converts a standard three dimensional array representation of one or more obstacles in the vehicle's environment into an octree and a connectivity graph. This achieves a significant reduct ion in computer memory usage and an increase in execution speed when the gr aph is searched. Path planning is based on a three-dimensional extension of the distance transform. Test results demonstrate rapid and effective opera tion of the planner within different workspaces.