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.
Figures & tables
Fig. 1 : Overview of the MultiPush framework. The single-robot task sequence produced by ReloPush-BOSS [ 3 ] is expanded into Seed of resting poses, transit times, task durations, and path traces, which parameterizes a pseudo-schedule : a free-space approximation of the multirobot timetable. A learned policy constructs candidate assignment sequences by rolling out against this pseudo-schedule, without invoking the motion planner, and the prioritized multiagent planner verifies them together with the greedy allocation. The best feasible plan is executed. η denotes the number of possible actions at each step.
Fig. 2 : The push-traversability graph. (a) Each vertex represents a start pose or a goal pose at the objects’ initial or goal poses, respectively. Each edge represents a feasible transfer path (or a series of partial transfer paths) between the start/goal poses, which are composed of Dubins curves. (b) Feasible rearrangements can be found over graph search at each assignment of tasks to robots. Our goal is to find a feasible assignment sequence with a low makespan.
Component
Description
States from the seed (one set per instance)
Resting poses
robot initial poses and the pose where each task’s final transfer path ends
Transit times
free-space Reeds–Shepp [ 31 ] time from each resting pose to each task’s pushing pose
Task durations
each task’s busy time in the seed
Path traces
sampled waypoints of each task’s paths; used for geometry only
Precedence relations
task pairs kept in seed order because a start or goal placement blocks a transfer
TABLE I: The geometry, durations, and precedence relations fixed by the seed, and the pseudo-schedule Γ^h advanced over them (Sec. IV-B ). The upper block is computed once per instance from the seed and the robots’ initial poses, and the lower block is updated at each assignment. Transit times ignore the other robots, which is the surrogate’s central approximation.
Feature
Description
max(0,C^a−C^max)
extension of the pseudo-schedule
max(0,C^max−C^a)
margin ahead of C^max
transit
free-space time to the pushing pose
C^i−mini′C^i′
delay behind the earliest free robot
maxiC^i+−miniC^i+
spread of availabilities
∑jblockagej
objects on the corridor
TABLE II: Features of ϕ(sh,ah) , evaluated for every candidate assignment from the seed and Γ^h , without path planning. The availability C^i is the time robot i completes its last assigned task in Γ^h , and C^max=maxiC^i before the assignment. The prediction C^a adds the candidate’s transit time and task duration from the seed to its robot’s availability, and C^i+ are the availabilities after the assignment. Clearance is the smallest boundary distance over the candidate’s pushing poses, normalized by the turning radius r (one at the boundary, zero at r or more). The last feature counts earlier-ordered tasks in σ0 whose undelivered objects obstruct the non-push segments of the candidate task in the seed.
Fig. 3 : Qualitative results. The first column shows four scenarios drawn from the test set involving respectively m∈{8} , 10, 12, and 14 objects; objects’ start poses are drawn in yellow, and goal poses in white. The remaining columns show the resulting trajectories planned by MultiPush for n=1 , 2 , 3 , and 4 robots, colored by robot.
4.5×5.5 m 2 (trained workspace)
5.0×5.0 m 2 (unseen workspace)
Rel. Makespan
Rel. Makespan
n
Method
vs. GREEDY
vs. BOSS
Planning (s)
Success (%)
vs. GREEDY
vs. BOSS
Planning (s)
Success (%)
1
BOSS
–
1.000
–
100.0
–
1.000
–
100.0
MultiPush+BOSS
–
0.947 (0.044)
5.1 (4.7)
100.0
–
0.945 (0.047)
5.0 (5.2)
100.0
2
GREEDY
1.000
0.602 (0.064)
–
96.0
1.000
0.593 (0.056)
–
93.0
RANDOM
1.024 (0.133)
0.613 (0.078)
11.9 (8.2)
92.5
1.026 (0.130)
0.606 (0.076)
11.5 (9.5)
92.5
TABLE III : Relative makespan, planning time, and success rate with n robots on the held-out test set for the trained and an unseen workspace. Each workspace column covers 400 test instances, 100 per object count m∈{8,10,12,14} . The test instances appear in neither the training nor the validation set, and ReloPush-BOSS solves every instance. The relative makespan is measured against GREEDY and against the single-robot makespan of BOSS, both averaged over the instances solved by every method. At n=1 , MultiPush+BOSS verifies the BOSS solution in addition to the K′ candidates in place of the GREEDY allocation.
Fig. 4 : Mean makespan, relative to that of GREEDY, on the validation set across training, warm-started with behavior cloning. Each point averages the relative makespan of the best feasible of the K′ sampled candidates over the validation instances the policy solves. The star marks the policy selected for inference. The shaded band is the standard error of the mean. The standard deviation across the solved instances is 0.10 to 0.12 at every epoch.
Planner evaluations that returned infeasible (%)
Trained workspace
Unseen workspace
Method
n=2
n=3
n=4
n=2
n=3
n=4
All
RANDOM
40.6
37.7
36.3
37.7
35.3
33.6
36.9
LNS
38.7
42.0
43.4
36.4
40.6
43.2
40.7
MultiPush
31.2
28.3
26.5
29.1
26.7
24.6
27.7
TABLE IV : Fraction of planner evaluations that returned infeasible on the test set of Table III .
Non-prehensile manipulation with mobile robots has primarily targeted placement in coarse goal regions. Precision placement has been studied with manipulators on benchmarks such as Push-T, where an omnidirectional end effector can readily re-approach an object from any side. For a mobile robot, correcting the same placement errors may require wide repositioning maneuvers around the object. We formalize multi-object pushing with a mobile robot as a multi-target assignment problem at tight tolerances. We propose a diffusion planner with a causal factorization: each robot denoising step is followed by an object step conditioned on the current clean robot estimate. This factorization allows us to sample multiple object outcomes for a single robot plan, capturing the multi-modality of pushing. We also design a set of pushing-specific costs for mobile robots, used for both guidance and best-of-N sampling at inference. On Push-T, our planner attains the highest success rate of the methods we compare, while having the lowest rate of implausible object motion. Across three multi-box pushing environments resembling warehouse scenarios, it raises the fraction of boxes placed by 21.5 percentage points over an unguided baseline, and replans 1.8× faster than a planner that denoises the two trajectories together. Lastly, we deploy the guided planner on a TurtleBot 3 Burger with object shapes absent from the training data, where it places 85.0% of objects within tolerance against Diffusion Policy's 37.5%.
Lance Pharand, Megnath Ramesh, Mark Chiu +2
Electrical and Computer Engineering Department at the University of Waterloo, ON, Canada
This paper introduces Embodied Scene Rearrangement Planning (ESRP), a novel task requiring embodied agents to rearrange furniture in 3D scenes to match a target configuration using only egocentric observations and a top-down target layout. Unlike prior rearrangement tasks, ESRP precludes global state access and introduces mutual object occlusions, reflecting the practical constraints of real-world robotic deployment. These factors make aligning partial egocentric observations with the global target layout particularly challenging for long-horizon planning. To facilitate research, we present ESRP-Bench, a comprehensive benchmark built on OmniGibson featuring over 5,400 scene pairs and 8,200 objects. We define three multi-level metrics to evaluate rearrangement quality and provide four baselines: a hierarchical task-and-motion planning method, a vision-language-model-based method, and two learning-based approaches (IL and RL). Experimental results demonstrate that current methods struggle to complete the task efficiently, highlighting ESRP as a challenging frontier for embodied agents in scene understanding and long-horizon task planning. This work serves as a stepping stone toward deploying intelligent agents in real-world scenarios. Project page: https://pie-lab.cn/ESRP/.
Canzhi Chen, Zan Wang, Siqi Zhu +3
School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
Most multi-robot task allocation methods rely on communication to resolve conflicts and reach consistent assignments. In environments with limited bandwidth, degraded infrastructure, or adversarial interference, existing approaches degrade sharply. We introduce a learning-based framework that achieves high-quality task allocation without any robot-to-robot communication. The key idea is that robots coordinate implicitly by predicting teammates' bids: if each robot can anticipate competition for a task, it can adjust its choices accordingly. Our method predicts bid distributions to correct systematic errors in analytical mean-field approximations. While analytical predictions assume idealized conditions (uniform distributions, known bid functions), our learned approach adapts to task clustering and spatial heterogeneity. Inspired by Smart Predict-then-Optimize (SPO), we train predictors end-to-end to minimize Task Allocation Regret rather than prediction error. To scale to large swarms, we develop a mean-field approximation where each robot predicts the distribution of competing bids rather than individual bids, reducing complexity from O(NT) to O(T). We call our approach FORMICA: Field-Oriented Regret-Minimizing Implicit Coordination Algorithm. Experiments show FORMICA substantially outperforms a natural analytical baseline. In scenarios with 16 robots and 64 tasks, our approach improves system reward by 17% and approaches the optimal MILP solution. When deployed on larger scenarios (256 robots, 4096 tasks), the same model improves performance by 7%, demonstrating strong generalization. Training requires only 21 seconds on a laptop, enabling rapid adaptation to new environments.
Antonio Lopez, Jack Muirhead, Carlo Pinciroli
Dept. of Robotics Engineering, Worcester Polytechnic Institute, Worcester MA 01609, USA