This thesis introduces new concepts and algorithms that can be used to solve the simultaneous task and motion planning (STAMP) problem. Given a set of actions a robot could perform, the STAMP problem asks for a sequence of actions that takes the robot to its goal and for motion plans that correspond to the actions in that sequence. This thesis shows how to solve the STAMP problem more efficiently and obtain more robust solutions, when compared to previous work. A solution to the STAMP problem is a prerequisite for most operations complex robots such as mobile manipulators are asked to perform. Solving the STAMP problem efficiently thus expands the range of capabilities for mobile manipulators, and the increased robustness of computed solutions can improve safety.
A basic sub-problem of the STAMP problem is motion planning. This thesis gen- eralizes KPIECE, a sampling-based motion planning algorithm designed specifically for planning in high-dimensional spaces. KPIECE offers computational advantages by employing projections from the searched space to lower-dimensional Euclidean spaces for estimating exploration coverage. This thesis further develops the original KPIECE algorithm by introducing a means to automatically generate projections to lower-dimensional Euclidean spaces. KPIECE and other state-of-the-art algorithms are implemented as part the Open Motion Planning Library (OMPL), and the practical applicability of KPIECE and OMPL is demonstrated on the PR2 hardware platform.
To solve the STAMP problem, this thesis introduces the concept of a task motion multigraph (TMM), a data structure that can express the ability of mobile manipulators to perform specific tasks using different hardware components. The choice of hardware components determines the state space for motion planning. An algorithm that prioritizes the state spaces for motion planning using TMMs is presented and evaluated. Experimental results show that planning times are reduced by a factor of up to six and solution paths are shortened by a factor of up to four, when considering the available planning options. Finally, an algorithm that considers uncertainty at the task planning level based on generating Markov Decision Process (MDP) problems from TMMs is introduced.