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

Award Abstract on the NSF page.

Major Goals of the Project

The project seeks efficient solutions to multi-object manipulation problems by

  1. identifying cases where the extension of recent developments in multi-body motion planning can assist in the resolution of rearrangement challenges, and
  2. developing hierarchical tools, which identify the decomposition of hard rearrangement problems into simpler subproblems that can be addressed by such multi-body planners.

Rearranging objects is essential to the resolution of many manipulation tasks in application domains, from warehouse management to logistics and service robotics. A key challenge in this context is the combinatorial explosion induced by the infinitely many ways with which objects can be placed in the workspace. Thus, an effective method for attacking these combinatorial issues is highly desirable.


2016 - 2017

The project proposed two main research directions:

1. Firmly establishing the intrinsic, fundamental link between multi-object manipulation and (single-) graph-based multi-body motion planning. Quantitatively, the objective is to explore how multi-object manipulation problems may be reduced to a graph-based multi-body planning problem.

2. With efficiency and optimality in mind, delivering a sound algorithmic framework for solving complex multi-object manipulation problems through hierarchical decomposition, in which each unit can be casted as a unique multi-body motion planning problem.

During the initial year of the project, the project research activities have mainly focused on the first direction, as planned.

Significant Results

Focusing on the first of the two planned directions of the project, the team systematically examined the multi-object rearrangement domain and successfully distilled abstractions from multi-body motion planning. Subsequently, structural studies and algorithmic solutions are produced that resolve these high-fidelity problem abstractions. These applications scenarios include:
(1) table-top object rearrangement with overhand grasps,
(2) store shelf merchandize rearrangement (e.g., shelves of soft drinks), and
(3) multi-story autonomous parking.

More specifically, on the topic of table-top object rearrangement with overhand grasps, the research team establishes that the optimal resolution of many seemingly simple tasks is actually computationally intractable. Through establishing an equivalance between table-top object rearrangement problem and classical (hard) combinatorial problems in the CS domain, fast methods have been developed that allow the effective resolution for table-top object rearrangement tasks. The finding is both surprising and satisfactory.

A second significant result achieved during the first year of the project targets stack-based object rearrangement tasks. In this case, a typical scenario involves organizing a shelf of soft drinks in a convenience store. The scenarios is abstracted as the stack rearrangement problem, which also covers application scenarios including multi-story autonomous vehicle parking. The key challenge here is finding the sequence of pick-and-place actions so as to minimize the rearrangment task, under the constraints that only objects in the front of the stacks are available for grasping. The research team characterized the problem and established the lower and upper bounds on what is achievable under the setup. In particular, algorithms were derived that produce action sequences that are within a logarithmic factor of the best possible.

Relevant Publications

  • Azizi, V., Kimmel, A., Bekris, K. E., Kapadia, M. (2017). Geometric Reachability Analysis for Grasp Planning in Cluttered Scenes for Varying End-Effectors. 13th IEEE International Conference on Automation Science and Engineering (CASE 2017).
  • Jingjin Yu and Steven M. LaValle (2016). Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics. 32. (5). IEEE Transactions on Robotics, 32. 1163. Published. Yes. Yes. DOI. 10.1109/TRO.2016.2593448.
  • Jingjin Yu, Shuai D. Han, Wei N. Tang, and Daniela Rus (2017). A Portable, 3D-Printing Enabled Multi-Vehicle Platform for Robotics Research and Education. 2017 IEEE International Conference on Robotics and Automation (ICRA 2017). Awaiting Publication.
  • Shuai D. Han, Nicholas M. Stiffler, Athansios Krontiris, Kostas E. Bekris, and Jingjin Yu (2017). High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods. 2017 Robotics: Science and Systems (RSS 2017). Accepted. - Candidate for Best Student Paper award
  • Shuai D. Han, Nicholas M. Stiffler, Kostas E. Bekris, and Jingjin Yu (2017). Efficient, High-Quality Stack Rearrangement. International Symposium on Multi-Robot and Multi-Agent Systems. Submitted.