Multi-Arm Tabletop Multi-Object Rearrangement Planning and Optimization

From June to December 2025 I worked remotely with the Algorithmic Robotics and Control Lab at Rutgers University, advised by Prof. Jingjin Yu. The problem was posed at a high level: several robot arms have to rearrange objects on a tabletop from a start arrangement to a goal arrangement, and a goal position may already be occupied by another object. From that statement I independently developed the formulation and the model, wrote the pseudocode and the implementation, explored the algorithmic approaches, and produced a systematic simulation study of the trade-offs they expose.

The problem

The setting is the tabletop rearrangement problem with overhand grasps [1]: n objects lie on a flat surface, each with a start pose and a goal pose, and an arm can lift any object straight up, carry it above the others, and set it down. That abstraction turns continuous motion into a discrete pick-and-place primitive, so the difficulty of the problem is combinatorial rather than geometric: it is about the order in which objects move and where they go in the meantime.

The order is forced by occupancy. If object B currently sits where object A has to go, A cannot be placed until B has moved. When those constraints form a chain, the plan is a sequence; when they form a cycle, no object in the cycle can be placed first, and one of them has to be set down somewhere temporary. That temporary location is a buffer, and whether an instance can be solved with each object moved once—a monotone instance—or needs buffers— a non-monotone one—is the single most important property of the instance.

Adding arms changes the question from which sequence to which schedule. Each pick-and-place now has to be assigned to an arm, the arms have different reachable regions that overlap only partly, two arms cannot pass through each other or work in the same place at the same time, and an idle arm may execute a later action early if nothing it depends on is still pending. Execution time and arm availability therefore become planning variables in their own right, alongside the number of actions and the amount of buffer space a plan uses.

Where this sits in the literature

Three results frame the work. Han et al. [1] established the structure of single-arm tabletop rearrangement: when start and goal poses do not overlap, minimizing arm travel reduces to a travelling-salesman problem; when they do overlap, minimizing the number of pick-and-place actions reduces to the feedback vertex set problem on the dependency graph, and both reductions run in reverse, which is what makes fast solvers possible despite the hardness. Gao et al. [2] then asked how much temporary space a rearrangement needs at once—the number of running buffers—showed that minimizing it is NP-hard on the dependency graph, and gave algorithms that scale to a hundred densely packed objects. Gao and Yu [3] took the non-monotone problem to two arms and showed that scheduling the pick-and-place sequence across them, with handoffs in the shared workspace, is substantially faster than either arm alone or a naive parallelization of a single-arm plan.

My work sits at the meeting point of the second and third: a formulation for the multi-arm case in which the quantities those papers optimize separately—dependencies, buffer usage, action count, execution time, and arm availability—are represented together as explicit planning variables, so that the trade-offs between them can be studied on the same instances.

Formulation

An instance is a set of objects, their start and goal poses, the tabletop geometry, and the arms with their reachable regions. A solution is a sequence of pick-and-place actions together with the arm assigned to each and its start time. Start and goal poses are modelled as occupied regions of the workspace, and the rule “a goal may be occupied” becomes a precedence constraint between objects. Collecting the constraints gives a directed dependency graph: an edge from B to A whenever B's current pose intersects A's goal.

On an acyclic graph a topological order is a feasible action sequence. On a graph with cycles, the plan must break every cycle by moving one of its objects to a buffer first, which introduces two questions the formulation makes explicit. How many buffers are needed at once depends on the cycle structure of the graph—how many cycles, how long, and how much they overlap—and that number is tracked as a quantity of the plan rather than assumed to be available. And buffers are not free locations: on a bounded table a buffer occupies space that may itself be some object's goal, so buffer placement is a decision the planner makes under the same occupancy constraints as everything else.

Above the dependency layer sits the multi-arm layer. Each arm has a reachable region; where regions overlap, an object that starts in one arm's exclusive region and ends in another's is carried in two actions with a handoff in the overlap. Two arms may not act in the same region at the same time, which is a mutual-exclusion constraint on the schedule. An arm's availability—busy or idle at each moment—is a state variable, and the schedule is built to keep both arms busy whenever the dependencies allow it.

Solver structure

The solver is hierarchical, which keeps the joint search space manageable. The upper level decides the rearrangement order and the buffer usage: it orders the dependency graph, breaks cycles, and chooses which object goes to a buffer and where. The lower level takes that action sequence and decides allocation and timing: which arm executes each action, when it starts, and where a handoff is inserted. I wrote the planning logic from the pseudocode up rather than on top of an existing planning library, and compared several routes through each level—dependency-graph heuristics and search over action sequences at the top, and several allocation strategies at the bottom.

Two supporting components make the study systematic. A random instance generator produces problems by object count, tabletop density, and dependency complexity, so that the same method can be examined as the instances grow harder. A feasibility checker verifies every output plan independently of the planner against all dependency and space constraints, so that a schedule is never counted as a result unless it is one.

Evaluation

The simulation study characterizes the trade-offs among completion time, buffer usage, action count, and resource allocation. Each plan is measured by its makespan, its number of actions, its peak buffer occupancy, the idle fraction of each arm, the parallel efficiency of the schedule, and the planner's success rate and solve time. The methods were run across randomized instances of increasing object count and density, with one and two arms, and ablated against one another: buffers allowed or forbidden, parallel execution allowed or serialized, and one allocation strategy against another.

The picture that emerges is a set of trade-off surfaces rather than a single winner. A plan that uses less buffer space tends to need a longer schedule; minimizing the number of actions does not minimize execution time; and an allocation that is locally best for one arm can constrain what the other arm is able to do next. The value of the formulation is that these are visible and attributable: for any plan, the objective or the constraint responsible for a decision can be traced.

The settings the model has to cover

Most of the work went into the axes along which this problem changes, because a formulation that only handles one set of assumptions is not worth building. Each axis below is a switch in the model rather than a separate program, and each one changes which plans are feasible and which are cheap.

How the arms share the table

At one extreme both arms can reach anywhere. Nothing has to be handed over, every action is available to either arm, and the only thing keeping them apart is that two arms cannot occupy the same place at the same moment—a clearance constraint between two actions that are in flight together, which depends on the paths rather than on the objects. At the other extreme each arm owns a region and the regions meet in a band. Reachability then decides who can do what, an object that starts in one arm's territory and ends in the other's cannot be moved by either arm alone, and the plan has to introduce a handoff in the shared band—one action becomes two, with a precedence between them. The same instance can be routine under one assumption and unsolvable by a single arm under the other, so reachability belongs inside the model rather than in a description of the hardware. Either way the arms are on a rail and cannot pass through one another, so two actions that are in flight together have to preserve the arms' left-to-right order—which is why adding arms does not reduce makespan indefinitely.

How the arms are driven in time

Asynchronous execution lets each arm begin its next action as soon as its own precedences are met and it is free; the schedule is a list schedule and the arms drift out of phase. Synchronous execution advances both arms in rounds: the actions chosen for a round start together, and the round ends when the slowest of them finishes, so an arm with nothing to do waits and an arm with a short action idles until its partner is finished. Synchronous is the honest model when the arms are commanded as one system, and rounds normally cost makespan that an asynchronous schedule does not pay. It is not a strict ordering, though: both schedulers are greedy, so on a particular instance the round packing can happen to make a better arm assignment than the list schedule does. Holding the action sequence fixed and switching only the timing model is what makes that cost measurable at all.

What an instance is allowed to look like

The literature this builds on assumes discs of one size, which keeps the geometry out of the way while the combinatorics is studied. Real objects are not discs, so occupancy has to be decided by an overlap test between arbitrary footprints at arbitrary orientations rather than by a distance between centres. The combinatorial structure survives that change—the dependency graph is built the same way— but which arrangements are dense, and therefore how many dependencies appear at all, changes completely with the shapes.

A second axis is whether the objects are labeled. If every object has its own goal, the dependency graph is fixed by the instance. If the goals are interchangeable, choosing the assignment is part of the planning problem, and the assignment determines the graph: a different matching produces different occupancy, different cycles, and a different buffer requirement. Assigning for minimum total travel is a matching problem that can be solved exactly, and settling it before the ordering stage often dissolves cycles that a labeled instance would have been stuck with.

The third is that a start arrangement need not be flat. Objects can rest on one another, which adds a second kind of constraint alongside goal occupancy: an overhand grasp can only take an object with nothing on top of it, so a stack has to come apart from the top down whatever its members' goals are. Support constraints are acyclic by themselves, but they interleave with the occupancy constraints and can hold back an object that is otherwise ready to move, which changes both the ordering and where the buffers have to go.

Demonstration

The demonstration below runs the formulation on random instances in the browser, with each of the settings above exposed as a control. Objects start at the solid footprints and must reach the dashed ones; the graph beside the table is the dependency graph, with solid edges for goal occupancy, dashed edges for support, and cycles marked. The planner builds the order, breaks cycles with buffers along the table edge, chooses the goal assignment when the objects are unlabeled, inserts a handoff when a move crosses between arm regions, and schedules the result either asynchronously or in synchronous rounds. The timeline underneath is that schedule, one row per arm. It is an illustration of the formulation written for this page, not the original research code.