# Uniform Object Rearrangement: From Complete Monotone Primitives to Efficient Non-Monotone Informed Search

arXiv: https://arxiv.org/abs/2101.12241 · HTML: https://mlsanity.com/paper/2101.12241/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 34 references that are in the map.
- First posted on arXiv 28 Jan 2021.

## Builds on (most cited first, 6 of 6)

- [Mechanical Search: Multi-Step Retrieval of a Target Object Occluded by Clutter](https://mlsanity.com/paper/1903.01588/) (2019)
- [Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps](https://mlsanity.com/paper/1711.07369/) (2017)
- [Fast and resilient manipulation planning for target retrieval in clutter](https://mlsanity.com/paper/2003.11420/) (2020)
- [Fast, High-Quality Dual-Arm Rearrangement in Synchronous, Monotone Tabletop Setups](https://mlsanity.com/paper/1810.12202/) (2018)
- [Toward Fast and Optimal Robotic Pick-and-Place on a Moving Conveyor](https://mlsanity.com/paper/1912.08009/) (2019)
- [Planning for target retrieval using a robotic manipulator in cluttered and occluded environments](https://mlsanity.com/paper/1907.03956/) (2019)

## Built on by (most cited first, 9 of 9)

- [SG-Bot: Object Rearrangement via Coarse-to-Fine Robotic Imagination on Scene Graphs](https://mlsanity.com/paper/2309.12188/) (2023)
- [Structural Concept Learning via Graph Attention for Multi-Level Rearrangement Planning](https://mlsanity.com/paper/2309.02547/) (2023)
- [Efficient and High-quality Prehensile Rearrangement in Cluttered and Confined Spaces](https://mlsanity.com/paper/2110.02814/) (2021)
- [Toward Efficient Task Planning for Dual-Arm Tabletop Object Rearrangement](https://mlsanity.com/paper/2207.08078/) (2022)
- [Smart Explorer: Recognizing Objects in Dense Clutter via Interactive Exploration](https://mlsanity.com/paper/2208.03496/) (2022)
- [Grasp, See, and Place: Efficient Unknown Object Rearrangement with Policy Structure Prior](https://mlsanity.com/paper/2402.15402/) (2024)
- [ORLA*: Mobile Manipulator-Based Object Rearrangement with Lazy A Star](https://mlsanity.com/paper/2309.13707/) (2023)
- [Lazy Rearrangement Planning in Confined Spaces](https://mlsanity.com/paper/2203.10379/) (2022)
- [Planning for Complex Non-prehensile Manipulation Among Movable Objects by Interleaving Multi-Agent Pathfinding and Physics-Based Simulation](https://mlsanity.com/paper/2303.13352/) (2023)

## Abstract (arXiv)

Object rearrangement is a widely-applicable and challenging task for robots. Geometric constraints must be carefully examined to avoid collisions and combinatorial issues arise as the number of objects increases. This work studies the algorithmic structure of rearranging uniform objects, where robot-object collisions do not occur but object-object collisions have to be avoided. The objective is minimizing the number of object transfers under the assumption that the robot can manipulate one object at a time. An efficiently computable decomposition of the configuration space is used to create a "region graph", which classifies all continuous paths of equivalent collision possibilities. Based on this compact but rich representation, a complete dynamic programming primitive DFSDP performs a recursive depth first search to solve monotone problems quickly, i.e., those instances that do not require objects to be moved first to an intermediate buffer. DFSDP is extended to solve single-buffer, non-monotone instances, given a choice of an object and a buffer. This work utilizes these primitives as local planners in an informed search framework for more general, non-monotone instances. The search utilizes partial solutions from the primitives to identify the most promising choice of objects and buffers. Experiments demonstrate that the proposed solution returns near-optimal paths with higher success rate, even for challenging non-monotone instances, than other leading alternatives.