Rearranging objects on a planar surface arises in a variety of
robotic applications, such as product packaging. Using two arms can im-
prove efficiency but introduces new computational challenges. This paper
studies the structure of dual-arm rearrangement for synchronous, mono-
tone 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. Theoreti-
cal 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 sup-
port these points and show that the scalable method can quickly compute
solutions close to the optimal for the considered setup.
more »
« less
Fast, High-Quality Two-Arm Rearrangement in Synchronous, Monotone Tabletop Setups
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
- Award ID(s):
- 1734419
- NSF-PAR ID:
- 10219059
- Date Published:
- Journal Name:
- IEEE Transactions on Automation Science and Engineering
- ISSN:
- 1545-5955
- Page Range / eLocation ID:
- 1 to 14
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We examine an important combinatorial challenge in clearing clutter using a mobile robot equipped with a manipulator, seeking to compute an optimal object removal sequence for minimizing the task completion time, assuming that each object is grasped once and then subsequently removed. On the structural side, we establish that such an optimal sequence can be NP-hard to compute, even when no two objects to be removed have any overlap. Then, we construct asymptotically optimal and heuristic algorithms for clutter removal. Employing dynamic programming, our optimal algorithm scales to 40 objects. On the other hand, for random clutter, fast greedy algorithms tend to produce solutions com- parable to these generated by the optimal algorithm.more » « less
-
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 DFS DP 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. DFS DP 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
-
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
-
Picking an item in the presence of other objects can be challenging as it involves occlusions and partial views. Given object models, one approach is to perform object pose estimation and use the most likely candidate pose per object to pick the target without collisions. This approach, however, ignores the uncertainty of the perception process both regarding the target’s and the surrounding objects’ poses. This work proposes first a perception process for 6D pose estimation, which returns a discrete distribution of object poses in a scene. Then, an open-loop planning pipeline is proposed to return safe and effective solutions for moving a robotic arm to pick, which (a) minimizes the probability of collision with the obstructing objects; and (b) maximizes the probability of reaching the target item. The planning framework models the challenge as a stochastic variant of the Minimum Constraint Removal (MCR) problem. The effectiveness of the methodology is verified given both simulated and real data in different scenarios. The experiments demonstrate the importance of considering the uncertainty of the perception process in terms of safe execution. The results also show that the methodology is more effective than conservative MCR approaches, which avoid all possible object poses regardless of the reported uncertainty.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1109/TASE.2021.3055144
