The problem of many: efficient multi-arm, multi-object task and motion planning with optimality guarantees

This thesis deals with task and motion planning challenges, specifically those involving manipulating multiple objects using multiple robot manipulators. The contributions range from a new foundational understanding of the problem and the conditions for achieving asymptotic optimality to devising application-oriented and efficient planning algorithms as well as experiments on real systems. A key focus corresponds to overcoming scalability challenges in motion planning and dealing with hybrid planning domains, i.e., those that combine continuous and discrete action spaces, to solve manipulation problems that involve multiple types of actions, such as picks, placements and handoffs. The thesis starts with a review of the theoretical foundations regarding the asymptotic optimality properties of sampling-based motion planners. The work outlines core ideas that motivated relevant algorithmic discoveries, as well as the various avenues of research that have followed since. It then presents a new foundational contribution regarding the theoretical conditions for guaranteeing asymptotic optimality in integrated task and motion planning problems. The work addresses the theoretical gap that existed in modeling interactions with the boundaries of the collision-free space, which invariably arise in task planning for manipulation. The second contribution pertains to the design of an efficient, heuristically guided, scalable and asymptotically optimal sampling-based algorithm specifically for solving high-dimensional multi-robot problems. The dRRT* algorithm extends the idea of a tensor roadmap decomposition of the underlying configuration space and uses efficient single-robot heuristics to solve challenging planning problems involving multiple manipulators in a coupled manner. The third area of impact relates to multi-arm task planning problems. Leveraging the efficient multi-arm planning paradigm provided by dRRT*, a multi-modal task planning approach has been developed to deal with pick-handoff-place problems involving up to $7$ robotic arms. A key benefit of integrated task planning enables every arm to preempt the motions that might be necessary for a sequence of actions. Similar task-planning challenges arise when instead of multiple arms, the number of objects increases, which leads to object rearrangement problems. The combinatorial explosion in this case arises from the choices available for assigning objects to arms, and sequencing such actions makes the problem more challenging. In this context, this thesis provides an efficient solution for dual-arm tabletop rearrangement by decomposing the problem into more efficiently solvable subproblems - weighted edge-matching and the traveling salesperson. The above two lines of work have been extended to address more general multi-arm rearrangement problems, dealing with instances involving up to 9 arms and 4 objects. The key insight is a specially constructed mode-graph with capacity constraints, where an efficiently solvable multi-agent path finding solution for the objects can be mapped to a solution to the task planning problem. The consideration of multiple agents in planning problems can extend to human and robotic agents as well. This thesis includes work in human-robot interaction which relate to legibility of manipulator motions, and different types of robotic pointing. It concludes by highlighting applications of the presented planning methods in important domains, such as solving robotic product packing, dual-arm constrained placement and the use of robots in exposure studies.Ph.D.Includes bibliographical reference