PaperlayerView exact revision on arXiv

Source-linked AI summary

MultiPush: Learning to Rearrange with Teams of Car-Like Pushers

Jeeho Ahn, Christoforos Mavrogiannis

arXiv:2609.27005v1cs.RO

TL;DR

Multi-object pushing by teams of car-like robots is challenging in constrained workspaces because of motion and coordination constraints. MultiPush uses reinforcement learning to schedule and allocate pushing tasks through a constraint-aware traversability graph. In simulation it lowers makespan relative to LNS across tested workspaces and robot counts, and it is demonstrated in a real-world rearrangement task.

  • Problem

    How can teams of car-like robots rearrange multiple objects by pushing in constrained, cluttered workspaces while handling kinematic and coordination constraints?

    Source: §I · p. 1

  • Method

    MultiPush uses reinforcement learning to jointly schedule pushing tasks and allocate them to robots, leveraging a traversability graph that encodes spatial, kinematic, and physics constraints.

    Source: §I · p. 1

  • Results

    LNS requires 2.3 to 2.6 times the planning time of MultiPush, which achieves a lower relative makespan in every workspace and robot count.

    Source: C. Results · p. 7

  • Takeaways & Limitations

    MultiPush was demonstrated with two- and three-robot teams rearranging 12 objects in the real world.

    Source: §I · p. 1

    Evaluation is limited to identical cubic objects, at most 14 per instance, two similar-sized rectangular workspaces, quasistatic pushing, and centralized execution.

    Source: §VII · pp. 7–8

Abstract

from arXiv · show

We focus on the problem of rearranging multiple objects within a constrained workspace via pushing using a team of car-like robots. While the use of multiple robots offers the potential for more efficient execution, the need for conflict resolution and the kinematic constraints arising from physics, robot design, and the workspace boundary make this problem especially challenging. Our key insight is that by exploiting the structure introduced by the car-like kinematics of the domain, we could relax the problem into an ordered assignment of Dubins curves to robots. To this end, we introduce MultiPush, a reinforcement-learning based framework that jointly determines an efficient schedule of pushing tasks and their allocation to available robots by leveraging a constraint-aware traversability graph. Across extensive simulated trials with up to 14 objects and teams of two to four robots, MultiPush reduces the makespan by up to 16% compared to the baselines while requiring up to 2.9 times faster planning time. We demonstrate MultiPush on a real-world scenario involving the rearrangement of 12 objects by two and three robots (1/10-scale racecars) in a constrained space.

I. INTRODUCTION

MultiPush addresses multi-object pushing in constrained workspaces, where clutter, object variability, robot kinematics, and team coordination complicate rearrangement. It uses car-like motion structure to schedule and allocate pushing tasks, with strong simulation results and a real-world demonstration.

I. INTRODUCTION

  • Cluttered, unstructured workspaces make engineered rail grids and specialized grippers impractical, while pushing and team coordination introduce further motion constraints.Under quasistatic pushing, car-like robots must steer within a limited range to maintain stable contact.Source: §I · p. 1
  • Car-like constraints let MultiPush replace a search over continuous multirobot paths with an ordered assignment of Dubins curves to robots.The framework jointly schedules pushing tasks and assigns them to robots using a constraint-aware traversability graph.Source: §I · p. 1
  • The framework formulates robot-task assignment and execution order as an MDP and trains an assignment policy using reinforcement learning.The policy uses features aggregated over robots and tasks and can transfer across robot counts and workspaces.Source: §I · pp. 1–2
  • The learned policy assigns tasks and execution order without invoking the motion planner, while training to minimize makespan and avoid infeasibility.The paper also demonstrates rearrangement of 12 objects by two- and three-robot teams in the real world.Source: §I · pp. 1–2
  • Under equal evaluation budgets, simulation shows the highest success rate and lowest makespan among baselines, with generalization to unseen robot counts and a workspace.Evaluations include up to 14 objects and four robots.Source: §I · p. 2

II. RELATED WORK

Prior work leaves continuous, nonmonotone rearrangement by multiple nonholonomic pushers relatively underexplored. The paper frames this setting as assigning tasks and collision-free trajectories to robots while minimizing total completion time.

II. RELATED WORK

  • Prior approaches address single pushers, monotone or discretized multirobot pushing, or navigation without physics-based manipulation; MultiPush targets continuous, nonmonotone rearrangement by multiple constrained pushers.Related methods include MAPF coordination and kinematic navigation, while the paper identifies manipulation constraints as a gap in those settings.Source: §II · p. 2

III. PROBLEM STATEMENT

  • The model considers identical car-like robots with flat bumpers pushing rigid polygonal objects in a shared workspace.Objects are assumed static once placed at their goals, and each task can be executed by one robot acting alone.Source: §III · p. 2
  • The objective is to choose an ordered sequence pairing each task with a robot, alongside collision-free robot trajectories, to minimize makespan.Makespan is the completion time of the entire rearrangement.Source: §III · p. 2

IV. MULTIPUSH: A FRAMEWORK FOR MULTIROBOT NONPREHENSILE REARRANGEMENT PLANNING

MultiPush combines a push-traversability graph with a learned policy to generate and verify multirobot task assignments, then executes the best feasible plan.

IV. MULTIPUSH: A FRAMEWORK FOR MULTIROBOT NONPREHENSILE REARRANGEMENT PLANNING

  • The framework expands a single-robot task sequence into a pseudo-schedule, uses it to construct candidate assignments, then verifies candidates with prioritized planning.The best feasible plan is selected for execution.Source: Figure 2 · p. 3
  • The push-traversability graph represents start and goal poses as vertices and feasible Dubins-curve transfers as edges for searching rearrangements.Graph search is used at each task assignment to find feasible rearrangements while seeking a low-makespan assignment sequence.Source: Figure 3 · p. 3
  • MultiPush combines the graph with reinforcement learning to generate an efficient assignment sequence for multiple robot pushers.The learned policy jointly generates the task assignment sequence; the graph describes kinematically feasible object transfers.Source: §IV · pp. 2–3

A. Task Representation

The task representation builds on a single-robot plan and its Dubins paths, then uses that structure to schedule tasks across multiple robots.

A. Task Representation

  • Tasks comprise transit motion without pushing and transfer motion while pushing, with optimal robot paths analytically derived using Dubins curves.The paths move each object from its initial pose to its goal pose.Source: A. Task Representation · p. 3
  • The Push-Traversability graph connects pushing poses at objects’ initial and goal placements with edges representing Dubins curves between poses.The graph supports extracting a nominal single-robot assignment sequence of object-transfer paths.Source: A. Task Representation · p. 3
  • The single-robot sequence provides structure for determining an efficient task schedule that accommodates multiple robots.Source: A. Task Representation · p. 3

B. Assignment Sequence as a Markov Decision Process

The assignment sequence is modeled as an episodic MDP whose reward favors low-makespan feasible schedules and penalizes infeasibility; a pseudo-schedule estimates assignments before full path planning.

B. Assignment Sequence as a Markov Decision Process

  • The MDP has one action per task, assigning that task to a robot, and its completed episode forms the assignment sequence.The state stores assignments made so far, and the transition appends the selected assignment.Source: B. Assignment Sequence as a Markov… · p. 3
  • Feasible assignment sequences are rewarded by negative makespan, while infeasible sequences receive a penalty that ranks their degree of constraint violation.The makespan is computed from collision-free trajectories and normalized by the greedy allocation’s makespan; the penalty is kept below feasible rewards and reflects when infeasibility first occurs.Source: B. Assignment Sequence as a Markov… · pp. 3–4
  • Assignments are admissible only when conflicting tasks ordered earlier in the single-robot sequence have already been assigned; admissibility does not ensure feasibility.The planner evaluates feasibility only after the full sequence is completed.Source: B. Assignment Sequence as a Markov… · p. 4
  • The pseudo-schedule estimates task completion and robot availability from seed transit times and task durations without planning paths or modeling robot interactions.Its timetable tracks delivered objects, robot resting locations and availability, and scheduled path occupancy; transit times ignore other robots.Source: B. Assignment Sequence as a Markov… · p. 4, Table I · p. 4

C. Learning an Assignment Policy

Because exact assignment search is impractical, MultiPush learns a stochastic policy from candidate-assignment features, trains it on planner-evaluated groups, and verifies candidates at inference.

C. Learning an Assignment Policy

  • Exact search is impractical because an instance can have up to m! n^m assignment sequences, each requiring multirobot trajectory planning.The policy is trained by reinforcement learning because optimal assignment sequences are unavailable for imitation.Source: C. Learning an Assignment Policy · p. 4
  • Candidate features summarize pseudo-schedule extension, robot-availability balance, and geometric or ordering risks that could make remaining tasks infeasible.The policy scores admissible candidates with a shared multilayer perceptron, allowing the candidate set to vary across steps and instances and the policy to apply to any robot count.Source: C. Learning an Assignment Policy · p. 4, Table II · p. 4
  • Policy-gradient training evaluates groups of sampled assignment sequences with the path planner and uses each group’s mean reward as a shared baseline.Subtracting the group mean removes the instance-wide reward offset, without requiring a value network.Source: C. Learning an Assignment Policy · p. 4
  • At inference, the prioritized planner verifies sampled assignment candidates, and the feasible plan with the minimum makespan is selected for execution.Source: C. Learning an Assignment Policy · p. 4

D. Prioritized Multirobot Path Planning

After assigning tasks, MultiPush plans robot trajectories sequentially, prioritizing robots with tasks and treating earlier trajectories as dynamic obstacles. Its evaluation assesses solution quality, planning efficiency, and generalization.

D. Prioritized Multirobot Path Planning

  • Task-assigned robots receive highest priority, and Hybrid A* plans trajectories that respect car-like kinematics while recording robot and object poses in a shared timetable.Each new plan accounts for already planned trajectories as dynamic obstacles.Source: D. Prioritized Multirobot Path Planning · pp. 4–5
  • Because fixed object goals and resting robots can block later tasks, prioritized planning is incomplete in this setting.A resting robot after a push may obstruct a later task, unlike in well-formed infrastructures.Source: D. Prioritized Multirobot Path Planning · p. 5
  • The planner first delays for a moving obstruction or moves an idle robot to safe parking; unresolved conflicts make the assignment sequence infeasible.Both remedies are checked for conflicts within the timetable’s time horizon.Source: D. Prioritized Multirobot Path Planning · p. 5

V. EVALUATION

  • The simulation evaluation assesses solution quality, planning efficiency, and generalization to robot counts and a workspace unseen in training.Experiment footage is also referenced by the authors.Source: §V · p. 5

A. Experiment Design

The experiments evaluate rearrangement scenarios across object counts, robot teams, and two workspace shapes. MultiPush is compared with GREEDY, RANDOM, and LNS using solution, feasibility, and planning-efficiency metrics.

A. Experiment Design

  • Scenarios contain 8, 10, 12, or 14 cubic objects and teams of 2–4 car-like robots, evaluated in a trained 4.5 × 5.5 m2 workspace and an unseen 5.0 × 5.0 m2 workspace.The minimum turning radius for stable pushing is 1.43 m; the policy is trained only in the first workspace and used unchanged elsewhere.Source: A. Experiment Design · p. 5
  • GREEDY, RANDOM, LNS, and MultiPush each evaluate K′ = 20 candidate assignment sequences per instance, with MultiPush also evaluating GREEDY.LNS starts from GREEDY; RANDOM samples task–robot assignments uniformly, while MultiPush samples from its learned policy.Source: A. Experiment Design · p. 5
  • Evaluation reports success rate, relative makespan over instances solved by every method, planning time over all instances, and the fraction of infeasible planner evaluations.Relative makespan is normalized per instance against GREEDY.Source: A. Experiment Design · p. 5

B. Implementation

The implementation combines a C++ planner with a small learned score network, trained on three-robot instances and evaluated across robot counts and workspaces. The supplied figures and table describe qualitative plans, training validation, and held-out test coverage.

B. Implementation

  • The C++ implementation includes the prioritized Hybrid A* planner and Dubins and Reeds–Shepp primitives; the score network has one hidden layer of eight units and is trained in Python.The authors state that they will release the implementation code upon publication.Source: B. Implementation · p. 5
  • Fig. 4 presents test scenarios with 8, 10, 12, and 14 objects and MultiPush trajectories for 1–4 robots, with trajectories colored by robot.Start poses are yellow and goal poses are white.Source: Figure 4 · p. 6
  • Training uses three robots and proceeds through behavior cloning followed by REINFORCE; the training set contains 10,400 instances across four object counts.Behavior cloning stops after 13 epochs when validation cross-entropy no longer improves.Source: B. Implementation · pp. 6–7
  • Validation selects the policy with the lowest relative makespan, while Fig. 5 plots validation makespan relative to GREEDY across training and marks the selected policy.The figure’s shaded band is the standard error of the mean.Source: B. Implementation · p. 7, Figure 5 · p. 7
  • Testing uses 400 instances per workspace and evaluates each with 2, 3, and 4 robots, including counts unseen during training.The two workspace test sets are generated independently and share no nominal instances.Source: Table III · p. 6, B. Implementation · p. 7

C. Results

MultiPush achieves lower relative makespan than LNS across the reported workspaces and robot counts, while RANDOM does not improve on GREEDY. Its advantage also appears in unseen settings, alongside fewer infeasible planner evaluations.

C. Results

  • MultiPush has lower relative makespan than LNS in every workspace and robot count, and LNS takes 2.3 to 2.6 times MultiPush’s planning time.Table III reports performance against the baselines.Source: C. Results · p. 7
  • RANDOM does not improve on GREEDY in any workspace or robot count, supporting the conclusion that gains follow from the learned policy rather than the evaluation budget.Source: C. Results · p. 7
  • MultiPush maintains its advantage over LNS in the unseen workspace and at the two- and four-robot evaluations, supporting generalization beyond the training workspace and robot count.Source: C. Results · p. 7
  • MultiPush has a smaller fraction of infeasible planner evaluations than LNS and RANDOM; these failed searches consume the most planning time and contribute to MultiPush’s planning-time advantage.Table IV reports the fraction of infeasible evaluations.Source: C. Results · p. 7, Table IV · p. 7

VI. HARDWARE DEMONSTRATIONS

Hardware demonstrations rearrange 12 objects with two and three MuSHR racecars. The stated evaluation is bounded by the seed planner and a narrow object and workspace scope.

VI. HARDWARE DEMONSTRATIONS

  • The hardware demonstration rearranges 12 objects using two and three 1/10th-scale MuSHR racecars fitted with flat bumpers.Each robot tracks its planned trajectory using an overhead motion-capture pose; objects are manipulated open loop, without state feedback during execution.Source: §VI · p. 7
  • Planned trajectories resolve robot and object conflicts, so the tracking controller performs path tracking without collision avoidance.Robots receive only their own pose from an overhead motion-capture system.Source: §VI · p. 7

VII. LIMITATIONS

  • Instances must be solvable by ReloPush-BOSS because the seed fixes each task’s transfer path; its lower success rate on larger instances also bounds evaluation to 14 objects.Pushing is modeled as quasistatic, bounding steering by the minimum turning radius for stable pushing while leaving slipping and other dynamic effects unmodeled.Source: §VII · p. 7
  • Evaluation covers identical cubic objects, at most 14 per instance, and two similarly sized rectangular workspaces; adding a fourth robot reduces makespan less than adding a third.The passage attributes diminishing returns to longer waits from conflict resolution as congestion increases.Source: §VII · p. 7
  • MultiPush is centralized, with robots assigned trajectories they execute independently; future work targets decentralized execution, varied object properties, and contact uncertainty.The passage also notes that other reinforcement-learning frameworks could replace the one used in the implementation.Source: §VII · pp. 7–8
Loading 2609.27005v1…