Planning algorithms for complex manipulation tasks

Solving manipulation tasks requires planning not only robot motions but also various interaction such as grasps (robot-object) and placements (object-environment). This indispensable interaction imparts extra complexity to the problems such that solving complex manipulation tasks, which require a number of regrasping operations, remains elusive. In this thesis, we advance the state of the art by presenting novel unimanual and bimanual manipulation planning algorithms capable of planning manipulation motions with multiple regrasping. First, we introduce a unimanual manipulation planner that explores the composite configuration space efficiently and systematically, thanks to the guidance of the novel high-level grasp-placement graph. Unlike existing methods, the graph construction does not require heavy pre-processing and is specific to only the gripper and the manipulated object. Next, we present two bimanual manipulation planners. The first one addresses specific, yet challenging, cases when bimanual grasps remain the same throughout. With the novel characterization of configuration space with closed-chain constraints, the proposed planner can plan motions across different closed-chain connected components. The second one addresses more general cases when the object can be moved only when grasped by both robots. We present a planner with certified completeness property, which guarantees that when a certificate is available for a given object and environment, the planner will find a solution to any bimanual manipulation query whenever one exists. The hardware experiment demonstrates the planner's capability and is, to the best of our knowledge, the first to illustrate such regrasping capability, solving complex bimanual manipulation task on an actual system. Furthermore, we also present two improvements to motion planning, which indeed is a crucial component in any manipulation planning algorithm. The first improvement is an algorithm for generating time-optimal second-order trajectories subject to velocity, acceleration, and minimum-switch-time constraints. The latter constraint helps prevent concentrated acceleration switching in trajectories. The second improvement is a new bidirectional motion planner called AVP-BiRRT. The integration of the Admissible Velocity Propagation (AVP) algorithm, which enables a geometric path planner to find dynamically feasible paths, into a bidirectional planner is made possible by our newly proposed extension, AVP-Backward.Doctor of Philosophy (MAE