| Motion planning is an important challenge in robotics research. Efficient generation of collision-free motion is a fundamental capability necessary for autonomous robots.; In this dissertation, a fast and practical algorithm for moving a convex polygonal robot among a set of polygonal obstacles with translations and rotations is presented. The running time is {dollar}O(c((n + k)N + n{dollar}logn)), where c is a parameter controlling the precision of the results, n is the total number of obstacle vertices, k is the number of intersections of configuration space obstacles, and N is the number of obstacles, decomposed into convex objects. This dissertation exploits a simple 3D passage-network to incorporate robot rotations as an alternative to complex cell decomposition techniques or building passage networks on approximated 3D C-space obstacles.; A common approach in path planning is to compute the Minkowski difference of a polygonal robot model with the polygonal obstacle environment. However such a configuration space is valid only for a single robot orientation. In this research, multiple configuration spaces are computed between the obstacle environment and the robot at successive angular orientations spanning {dollar}pi .{dollar} Although the obstacles do not intersect, each configuration space may contain intersecting configuration space obstacles (C-space obstacles). For each configuration space, the algorithm finds the contour of the intersected C-space obstacles and the associated passage network by slabbing the collision-free space. The individual configuration spaces are then related to one another by a heuristic called "proper links" that exploit spatial coherence. Thus, each level is connected to the adjacent levels by proper links to construct a 3D network. Dijkstra's algorithm is used to search for the shortest path in the 3D network. Finally, the path is projected onto the plane to show the final locus of the path. |
