IRIS-98-363

Slice-Based Path Planning

Michael McHenry

This study addresses the problem of incremental path planning. A novel algorithm called Slice-Based Path Planning is described. This algorithm is based on constraining the search for a collision free path to lie within a slice, a two-dimensional non-planar manifold of the robot's full configuration space. Constraining the search space in this way allows the algorithm to scale to problems which would otherwise be infeasible. In addition, the smaller search space allows the application of a global (with respect to a slice) path planning method such as dynamic programming. The slice is adapted to a particular set of workspace obstacles and goal positions using an iterative optimization procedure. The slice-based approach offers two significant advantages. First, an existing slice can incrementally adapt to changes in the locations or number of obstacles. Secondly, the global intra-slice path planner can find a satisfactory free path quickly which is then continually improved upon as the slice optimization proceeds. The implementation uses a grid-based representation of a slice which makes the algorithm well suited to a massively parallel implementation. The algorithm has been evaluated using three sets of problems. The first set measures the basic algorithm's performance in environments with static obstacles. The second set measures the advantage of incrementally updating an existing slice when new obstacles are added to the workspace. The third set evaluates the algorithm's ability to continually adapt slices in environments with moving obstacles. The planner has also been demonstrated performing a simple reaching and grasping task using a Belgrade/USC hand mounted on a PUMA 560 manipulator.