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

在许多自主机器人操作应用中，一个关键的挑战是多个对象的重新排列。有两种情况会出现这样的需求：(i)操作任务本身是重新排列物体，（ii）遮挡物品必须重新排列以允许机器人访问目标物体。这种场景的例子可能出现在仓库和工业装置中，机器人必须在许多其他类似物体的存在下频繁地选择、挑选和转移产品、包装和托盘。另一个例子来自服务机器人，在人类空间工作的机器人助手必须经常检索或重新排列放置在狭窄空间内的多个物品，例如架子上的物品。本项目研究了在多体运动规划中哪些类别的多目标操作规划可以有效地解决，并开发了一套强大的新型计算解决方案。关键的洞察力是，对于许多现实世界的重排任务，忽略抓取方面，解决问题的物体运动序列看起来类似于多体运动规划的解决方案，特别是对于类似大小的物体。对这一环节的研究表明，可以将某些多目标操作问题转化为“图上的卵石运动问题”，这在算法理论和多体运动规划中都有很好的研究。总体目标是为多目标操作提供具有完备性和最优性保证的严格方法，对于当前方法面临固有组合复杂性问题的问题表现出良好的可扩展性和效率。这种方法也可以作为具有附加约束的任务的指导启发式，例如非平凡的动力学和不确定性。

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.