# Towards computing low-makespan solutions for multi-arm multi-task planning problems

Source: [Towards computing low-makespan solutions for multi-arm multi-task planning problems](<https://www.sota2.com/research/paper/68fa6fa31e209131cea46d96>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-26T01:24:25.039Z

Authors: Valentin N. Hartmann, Marc Toussaint

Published: 2023-05-27T16:59:13.000Z

## Abstract

We propose an approach to find low-makespan solutions to multi-robot multi-task planning problems in environments where robots block each other from completing tasks simultaneously. We introduce a formulation of the problem that allows for an approach based on greedy descent with random restarts for generation of the task assignment and task sequence. We then use a multi-agent path planner to evaluate the makespan of a given assignment and sequence. The planner decomposes the problem into multiple simple subproblems that only contain a single robots and a single task, and can thus be solved quickly to produce a solution for a fixed task sequence. The solutions to the subproblems are then combined to form a valid solution to the original problem. We showcase the approach on robotic stippling and robotic bin picking with up to 4 robot arms. The makespan of the solutions found by our algorithm are up to 30% lower compared to a greedy approach.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Multi-robot task and motion planning on unordered\_bottles scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-unordered_bottles-scenario.md>): Multi-robot task and motion planning; unordered\_bottles scenario; Initialization Time (s): 5.57.

- [Multi-robot task and motion planning on bottles scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-bottles-scenario.md>): Multi-robot task and motion planning; bottles scenario; Initialization Time (s): 32.45.

- [Multi-robot task and motion planning on unordered\_box\_reor. scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-unordered_box_reor-scenario.md>): Multi-robot task and motion planning; unordered\_box\_reor. scenario; Initialization Time (s): 8.09.

- [Multi-robot task and motion planning on unassigned\_tsp](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-unassigned_tsp.md>): Multi-robot task and motion planning; unassigned\_tsp; Initialization Time (s): 0.97.

- [Multi-robot task and motion planning on unassigned\_cleanup scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-unassigned_cleanup-scenario.md>): Multi-robot task and motion planning; unassigned\_cleanup scenario; Initialization Time (s): 8.14.

- [Multi-robot task and motion planning on simple scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-simple-scenario.md>): Multi-robot task and motion planning; simple scenario; Initialization Time (s): 1.09.

- [Multi-robot task and motion planning on hallway scenario other](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-hallway-scenario-other.md>): Multi-robot task and motion planning; hallway scenario other; Initialization Time (s): 2.92.

- [Multi-robot task and motion planning on three\_agents scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-three_agents-scenario.md>): Multi-robot task and motion planning; three\_agents scenario; Initialization Time (s): 34.13.

- [Multi-robot task and motion planning on triple\_waypoints scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-triple_waypoints-scenario.md>): Multi-robot task and motion planning; triple\_waypoints scenario; Initialization Time (s): 10.76.

- [Multi-robot task and motion planning on welding scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-welding-scenario.md>): Multi-robot task and motion planning; welding scenario; tinit (s): 65.82.

- [Multi-robot task and motion planning on eggcartons scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-eggcartons-scenario.md>): Multi-robot task and motion planning; eggcartons scenario; tinit (s): 5.12.

- [Multi-robot task and motion planning on box\_rearrangement scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-box_rearrangement-scenario.md>): Multi-robot task and motion planning; box\_rearrangement scenario; Initialization Time (s): 14.1.

- [Multi-robot task and motion planning on pyramid scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-pyramid-scenario.md>): Multi-robot task and motion planning; pyramid scenario; Initialization Time (s): 23.99.

- [Multi-robot task and motion planning on mobile\_strut scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-mobile_strut-scenario.md>): Multi-robot task and motion planning; mobile\_strut scenario; Initialization Time (s): 75.37.

- [Multi-robot task and motion planning on three\_robot\_truss scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-three_robot_truss-scenario.md>): Multi-robot task and motion planning; three\_robot\_truss scenario; Initialization Time (s): 24.68.

- [Multi-robot task and motion planning on spiral\_tower scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-spiral_tower-scenario.md>): Multi-robot task and motion planning; spiral\_tower scenario; Initialization Time (s): 196.74.

- [Multi-robot task and motion planning on spiral\_tower two](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-spiral_tower-two.md>): Multi-robot task and motion planning; spiral\_tower two; Initialization Time (s): 14.14.

- [Multi-robot task and motion planning on cube\_four scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-cube_four-scenario.md>): Multi-robot task and motion planning; cube\_four scenario; Initialization Time (s): 117.86.

- [Multi-robot task and motion planning on dep\_piano scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-dep_piano-scenario.md>): Multi-robot task and motion planning; dep\_piano scenario; Initialization Time (s): 1.59.

- [Multi-robot task and motion planning on dep\_box\_stacking scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-dep_box_stacking-scenario.md>): Multi-robot task and motion planning; dep\_box\_stacking scenario; Initialization Time (s): 20.31.

- [Multi-robot task and motion planning on box\_stacking scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-box_stacking-scenario.md>): Multi-robot task and motion planning; box\_stacking scenario; Initialization Time (s): 14.98.

- [Multi-robot task and motion planning on box\_reorientation scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-box_reorientation-scenario.md>): Multi-robot task and motion planning; box\_reorientation scenario; Initialization Time (s): 28.79.

- [Multi-robot task and motion planning on mobile\_wall\_four scenario](<https://www.sota2.com/research/sota/multi-robot-task-and-motion-planning-on-mobile_wall_four-scenario.md>): Multi-robot task and motion planning; mobile\_wall\_four scenario; Initialization Time (s): 29.34.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2305.17527>)

[PDF](<https://arxiv.org/pdf/2305.17527.pdf>)
