A 2-D and 3-D robot path planning algorithm based on quadtree and octree representation of the workspace

A 2-D and 3-D path planning algorithm for robot navigation and manipulation is developed in this thesis. This method is of particular interest for robotic systems which require both 2-D navigation to reach the work site and 3-D path planning for on-site manipulation and inspection. This study extends the approach of 2-D path planning to 3-D with minimal effort. The quadtree and octree structures are used for 2-D and 3-D workspace representation, respectively. The quadtree and octree is generated from brightness image of the workspace obtained using a camera mounted on a robot. Path generation is based on the A* algorithm. The spatial length and the clearance space available for the robot are used as constraints in the path generation. The distance transform is used as a measure to compute the clearance space along the path. A methodology is developed to compute the distance transform of the free nodes in the 3-D workspace that is represented by an octree. The results of this approach are illustrated through an experimental system setup on a robotic workstation.