Planning Practical Paths in High-Dimensional Space

Unlike traditional manipulator robots which tend to have small numbers of degree of freedom (DOF), tentacle robots utilize redundant DOFs in order to enhance their ability to deal with complex environments and tasks. However, it also makes the planning and control of such devices extremely difficult. One of the fundamental tasks robots have to perform is planning their motions while avoiding collisions with obstacles in the environment, which is known to be PSPACE-complete in the robot's DOF. As a consequence heuristic sampling-based approaches have been developed to solve high-dimensional real-world path planning problems. A shortcoming of the current sampling-based algorithms is that they can obtain highly non-optimal solutions since they rely upon randomization to explore the search space. Although these planners may find a valid solution, the solutions found are often not practical in that they do not take into account soft application-specific constraints.

This thesis integrates soft constraints in addition to the basic geometric or hard constraints in the general path planning process for high DOF robots. The practicality of paths are formulated based on the notion of soft constraints found in the Planning Domain Definition Language 3 (PDDL3). A range of optimization strategies are developed targeted towards user-preferred qualities by integrating soft constraints in the pre-processing (i.e. sampling), planning and post-processing phases of the sampling-based path planners. An auction-based resource allocation approach coordinates competing optimization strategies. This approach uses an adaptive bidding strategy for each optimizer and in each round the optimizer with the best predicted performance is selected. This general coordination system allows for flexibility in both the number and types of the optimizers to be used. Experimental validation with real and simulated tentacle robots demonstrate the effectiveness of the approach.