More Like this

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

   Wang, Rui ; Gao, Kai ; Nakhimovich, Daniel ; Yu, Jingjin ; Bekris, Kostas E ( May 2021 , IEEE International Conference on Robotics and Automation (ICRA))

   null (Ed.)

   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. 

   more » « less
2. Fast, High-Quality Two-Arm Rearrangement in Synchronous, Monotone Tabletop Setups

   https://doi.org/10.1109/TASE.2021.3055144  

   Shome, Rahul ; Solovey, Kiril ; Yu, Jingjin ; Bekris, Kostas ; Halperin, Dan ( January 2021 , IEEE Transactions on Automation Science and Engineering)

   null (Ed.)

   Rearranging objects on a planar surface arises in a variety of robotic applications, such as product packaging. Using two arms can improve efficiency but introduces new computa- tional challenges. This paper studies the problem structure of object rearrangement using two arms in synchronous, monotone tabletop setups and develops an optimal mixed integer model. It then describes an efficient and scalable algorithm, which first minimizes the cost of object transfers and then of moves between objects. This is motivated by the fact that, asymptotically, object transfers dominate the cost of solutions. Moreover, a lazy strategy minimizes the number of motion planning calls and results in significant speedups. Theoretical arguments support the benefits of using two arms and indicate that synchronous execution, in which the two arms perform together either transfers or moves, introduces only a small overhead. Experiments support these claims and show that the scalable method can quickly compute solutions close to the optimal for the considered setup. 

   more » « less
3. Minimizing running buffers for tabletop object rearrangement: Complexity, fast algorithms, and applications

   https://doi.org/10.1177/02783649231178565  

   Gao, Kai ; Feng, Si Wei ; Huang, Baichuan ; Yu, Jingjin ( June 2023 , The International Journal of Robotics Research)

   For rearranging objects on tabletops with overhand grasps, temporarily relocating objects to some buffer space may be necessary. This raises the natural question of how many simultaneous storage spaces, or “running buffers,” are required so that certain classes of tabletop rearrangement problems are feasible. In this work, we examine the problem for both labeled and unlabeled settings. On the structural side, we observe that finding the minimum number of running buffers (MRB) can be carried out on a dependency graph abstracted from a problem instance and show that computing MRB is NP-hard. We then prove that under both labeled and unlabeled settings, even for uniform cylindrical objects, the number of required running buffers may grow unbounded as the number of objects to be rearranged increases. We further show that the bound for the unlabeled case is tight. On the algorithmic side, we develop effective exact algorithms for finding MRB for both labeled and unlabeled tabletop rearrangement problems, scalable to over a hundred objects under very high object density. More importantly, our algorithms also compute a sequence witnessing the computed MRB that can be used for solving object rearrangement tasks. Employing these algorithms, empirical evaluations reveal that random labeled and unlabeled instances, which more closely mimic real-world setups generally have fairly small MRBs. Using real robot experiments, we demonstrate that the running buffer abstraction leads to state-of-the-art solutions for the in-place rearrangement of many objects in a tight, bounded workspace.

    

   more » « less
4. Skill Generalization with Verbs

   Ma, Rachel ; Lam, Lyndon ; Spiegel, Benjamin ; Ganeshan, Aditya ; Patel, Roma ; Abbatematteo, Ben ; Paulius, David Paulius ; Tellex, Stefanie ; Konidaris, George ( October 2023 , Proceedings of the 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems)

   It is imperative that robots can understand natural language commands issued by humans. Such commands typically contain verbs that signify what action should be performed on a given object and that are applicable to many objects. We propose a method for generalizing manipulation skills to novel objects using verbs. Our method learns a probabilistic classifier that determines whether a given object trajectory can be described by a specific verb. We show that this classifier accurately generalizes to novel object categories with an average accuracy of 76.69% across 13 object categories and 14 verbs. We then perform policy search over the object kinematics to find an object trajectory that maximizes classifier prediction for a given verb. Our method allows a robot to generate a trajectory for a novel object based on a verb, which can then be used as input to a motion planner. We show that our model can generate trajectories that are usable for executing five verb commands applied to novel instances of two different object categories on a real robot. 

   more » « less
5. Local Neural Descriptor Fields: Locally Conditioned Object Representations for Manipulation

   https://doi.org/10.1109/ICRA48891.2023.10160423  

   Chun, Ethan ; Du, Yilun ; Simeonov, Anthony ; Lozano-Perez, Tomas ; Kaelbling, Leslie ( January 2023 , IEEE International Conference on Robotics and Automation)

   A robot operating in a household environment will see a wide range of unique and unfamiliar objects. While a system could train on many of these, it is infeasible to predict all the objects a robot will see. In this paper, we present a method to generalize object manipulation skills acquired from a limited number of demonstrations, to novel objects from unseen shape categories. Our approach, Local Neural Descriptor Fields (LNDF), utilizes neural descriptors defined on the local geometry of the object to effectively transfer manipulation demonstrations to novel objects at test time. In doing so, we leverage the local geometry shared between objects to produce a more general manipulation framework. We illustrate the efficacy of our approach in manipulating novel objects in novel poses – both in simulation and in the real world. 

   more » « less