RI: Small: Taming Combinatorial Challenges in Multi-Object Manipulation

点击翻译按钮获取中文摘要

A key challenge in many autonomous robot manipulation applications isthe rearrangement of multiple objects. There are two situations wheresuch needs arise: (i) the manipulation task itself is to rearrangeobjects, and (ii) occluding items must be rearranged to allow therobot access to the target object(s). Examples of such scenarios canarise in warehouses and industrial setups, where a robot has tofrequently select, pick and transfer products, packages and pallets inthe presence of many other similar objects. Another example comes fromservice robotics, where a robotic assistant that operates in a humanspace has to frequently retrieve or rearrange multiple items placed innarrow spaces, such as objects in shelves.This project investigates which classes of multi-object manipulationplanning can be efficiently addressed given progress in multi-bodymotion planning and develops a powerful suite of novel computationalsolutions. The key insight is that for many real-world rearrangementtasks the sequence of object motions to solve the problem, ignoringgrasping aspects, look similar to solutions of multi-body motionplanning, especially for similar sized objects. The study of this linkreveals it is possible to cast certain multi-object manipulationproblems as a "pebble motion problem on a graph", which is wellstudied in algorithmic theory and multi-body motion planning. Theoverall objective is to provide rigorous methods with desirablecompleteness and optimality guarantees for multi-object manipulation,which exhibit good scalability and efficiency for problems wherecurrent methods face issues with the inherent combinatorialcomplexity. Such methods could also be used as guiding heuristics fortasks with additional constraints, such as non-trivial dynamics anduncertainty.