PaperlayerView exact revision on arXiv

Source-linked AI summary

Long-Horizon Multi-Robot Rearrangement Planning for Construction Assembly

Valentin Noah Hartmann, Andreas Orthey, Danny Driess, Ozgur S. Oguz, Marc Toussaint

arXiv:2106.02489v3cs.RO

TL;DR

Long-horizon task-and-motion planning for heterogeneous multi-robot assembly remains an open challenge. The paper decomposes planning into smaller subproblems and combines manipulation-constraint optimization with space-time path planning. It demonstrates scaling across construction tasks and execution of computed plans on real robots.

  • Problem

    Long-horizon task-and-motion planning with multiple robots remains an open challenge, while previous approaches have limitations in scale, robot complexity, or demonstrated horizon.

    Source: B. Assembly Planning · p. 2

  • Method

    The system decomposes planning into limited-horizon subproblems and combines manipulation-constraint optimization with sampling-based path planning in space-time.

    Source: §I · pp. 1–2

  • Results

    The approach scales across construction tasks with many robots and objects, and a real-robot experiment showed that generated paths could be executed.

    Source: §VII · p. 12

  • Takeaways & Limitations

    Compared with fixed-time task assignments, time embedding is associated with better robot utilization, lower execution time, and lower movement-planning computation time.

    Source: §VII · p. 12

    Multiquery path planning could speed planning, but applying it in dynamic environments is not straightforward and remains future work.

    Source: §VI · p. 11

Abstract

from arXiv · show

Robotic assembly planning enables architects to explicitly account for the assembly process during the design phase, and enables efficient building methods that profit from the robots' different capabilities. Previous work has addressed planning of robot assembly sequences and identifying the feasibility of architectural designs. This paper extends previous work by enabling planning with large, heterogeneous teams of robots. We present a planning system which enables parallelization of complex task and motion planning problems by iteratively solving smaller subproblems. Combining optimization methods to solve for manipulation constraints with a sampling-based bi-directional space-time path planner enables us to plan cooperative multi-robot manipulation with unknown arrival-times. Thus, our solver allows for completing subproblems and tasks with differing timescales and synchronizes them effectively. We demonstrate the approach on multiple case-studies to show the robustness over long planning horizons and scalability to many objects and agents of our algorithm. Finally, we also demonstrate the execution of the computed plans on two robot arms to showcase the feasibility in the real world.

I. INTRODUCTION

Long-horizon multi-robot construction assembly remains difficult because existing task-and-motion planning approaches scale poorly to more robots or have been shown only over short horizons. The paper combines limited-horizon decomposition with optimization and space-time motion planning to coordinate heterogeneous teams.

I. INTRODUCTION

  • Long-horizon team planning remains challenging: prior approaches scale poorly with more robots or have only been demonstrated over short time horizons.Assembly order and object constraints can further amplify dependencies when robots work in parallel.Source: §I · p. 1
  • The paper extends prior assembly-planning work to heterogeneous teams and long horizons, framing the problem as task-and-motion planning with logic-geometric programming.The overall problem is decomposed into limited-horizon subproblems for subsets of robots, while previously planned trajectories remain fixed.Source: §I · p. 1
  • Time-embedded keyframe optimization jointly solves manipulation constraints in limited-horizon subproblems, combining optimization with sampling-based path planning.The approach is demonstrated on construction problems with up to 12 heterogeneous agents, including long-horizon cases with up to 113 parts.Source: §I · p. 2

II. RELATED WORK

  • Construction robotics is growing, but algorithmic planning for multiple robots has only begun to be studied.Prior multi-robot motion-planning approaches include combining individual roadmaps and sequentially prioritizing robot paths.Source: §II · p. 2, A. Multi-Robot Motion Planning · p. 2

A. Multi-Robot Motion Planning

  • A heuristic prioritizes subproblems, and a bidirectional space-time RRT plans between keyframes with unknown arrival times while accounting for previously planned trajectories.The goals for path planning are generated by jointly solving manipulation constraints within each subproblem.Source: A. Multi-Robot Motion Planning · p. 2, §I · p. 2

B. Assembly Planning

The paper situates its approach against assembly-planning work and formulates multi-robot rearrangement as a task-and-motion problem. Its scheduling function maps continuous time to active task assignments, allowing task switches at arbitrary times while preserving their order.

B. Assembly Planning

  • Assembly planning traditionally seeks valid assembly sequences; symbolic approaches factorize task decisions into skeletons executed by lower-level planners.The paper focuses on integrated task-and-motion planning for robotic assembly.Source: B. Assembly Planning · p. 2
  • Prior multi-robot work has not resolved long-horizon task-and-motion planning at scale, while this approach targets heterogeneous teams, more objects, and unsynchronized actions.Earlier work included long-horizon planning for one or two agents, as well as smaller or simpler multi-robot settings.Source: B. Assembly Planning · p. 2

III. MULTI ROBOT REARRANGEMENT PLANNING NOTATION AND PROBLEM FORMULATION:

  • The formulation represents robot and object configurations along a path, with each robot’s task assignment determining which constraints are active.The discrete task-state sequence is drawn from valid sequences induced by a first-order logic language.Source: §III · p. 3
  • The scheduling function maps continuous time to indices for each robot’s task sequence, allowing finitely many task switches at any time while keeping their order.The sequence of discrete states and the scheduling function are among the quantities the formulation seeks to determine.Source: §III · p. 3

A. Assumptions

The formulation assumes known object endpoints and manipulable configurations, monotonic object handling with re-grasping allowed, and no force or torque constraints. The method solves the overall planning problem through coordinated subproblems and a keyframe-and-path-planning workflow.

A. Assumptions

  • Objects have known initial and final positions, and the formulation assumes a method is available to sample configurations for manipulating them.Source: A. Assumptions · p. 3
  • Each object is handled once, although re-grasping such as handovers is allowed.Source: A. Assumptions · p. 3
  • Force and torque constraints are omitted; under the light-parts assumption, each object can be manipulated by a single robot.Source: A. Assumptions · p. 3

IV. METHOD

  • The overall problem is decomposed into simpler subproblems whose solutions together form a feasible solution to the original problem.The subproblems cover subsets of robots and assigned tasks, account for time-embedded scenes and cooperative constraints, and generate manipulation keyframes for space-time path planning.Source: §IV · p. 3
  • A heuristic selects each subproblem; the method finds feasible keyframes, then repeatedly samples time embeddings and attempts to connect them into a path.Source: Figure 3 · p. 4, §IV · p. 4

A. Decomposition into Time-Embedded, Limited Horizon Subproblems with a Subset of Agents

The planner incrementally selects an object and a subset of robots, then optimizes their plans while treating prior trajectories and other agents as part of the time-varying scene. Active degrees of freedom and planning horizons reflect when existing plans end and when the selected robots and object satisfy their constraints.

A. Decomposition into Time-Embedded, Limited Horizon Subproblems with a Subset of Agents

B. Time-Embedded Keyframes Optimization to Jointly Solve for Sequential Transition Constraints

The method combines discrete sequence search, nonlinear optimization, and sampling-based path planning to solve nonconvex subproblems. Optimization generates keyframes that jointly satisfy transition constraints, and randomized time embeddings and initial configurations provide varied candidate solutions.

B. Time-Embedded Keyframes Optimization to Jointly Solve for Sequential Transition Constraints

  • The planner combines valid-sequence search, nonlinear optimization, and sampling-based motion planning to address a nonconvex subproblem.Source: B. Time-Embedded Keyframes… · p. 5
  • The optimizer generates keyframes at transitions between task states, jointly satisfying interdependent constraints such as consistent pick-and-place hand positions.Source: B. Time-Embedded Keyframes… · p. 5
  • Uniformly sampled transition times and randomly sampled optimizer initializations generate varied keyframes, helping address local optima.The resulting feasible keyframes serve as goals for bidirectional path planning.Source: B. Time-Embedded Keyframes… · p. 5

C. Bi-directional Space-Time Path Planning to Connect Keyframes

The path planner connects keyframes sequentially in space-time, with candidate arrival times that can expand to accommodate waiting and time-dependent obstacles from prior plans. Bidirectional RRT extensions find paths, which are then shortcut and smoothed without altering fixed portions.

C. Bi-directional Space-Time Path Planning to Connect Keyframes

  • Path planning advances through the action sequence one keyframe at a time, while the optimizer supplies later keyframes consistent with those already planned.Solving for remaining mode-switch configurations can exclude a locally feasible keyframe that would make a later step infeasible.Source: C. Bi-directional Space-Time Path… · pp. 5–6
  • Candidate arrival times are sampled and their range is extended during planning, allowing longer time spans or waiting when arrival times are unknown.Source: C. Bi-directional Space-Time Path… · p. 6
  • The planner searches combined robot configuration and time space toward goal keyframes with varying arrival times, while accounting for moving obstacles and agents on prior plans.Source: Path-Planning · p. 6
  • The bidirectional space-time RRT uses keyframe goals, time-dependent collision queries, and time-bounded configuration sampling; its distance metric disallows backward-time or over-speed connections.Source: Path-Planning · p. 6
  • Shortcutting replaces path segments with straight connections only when constraints remain satisfied, and smoothing uses the original constraints and cost function.Previously fixed path portions cannot be altered during either postprocessing step.Source: Path-Planning · p. 6

D. Prioritization of Subproblems and Search over Skeletons

The planner incrementally selects objects, robot teams, and task sequences for limited-horizon subproblems. When no feasible choice is found, it rewinds earlier placements and searches again.

D. Prioritization of Subproblems and Search over Skeletons

  • Object ordering matters because parts need sufficient support, and placing an object too early can obstruct later placements.Source: D. Prioritization of Subproblems and… · p. 7
  • The search state tracks already rearranged objects and the times through which each robot has an assigned trajectory.Previously planned robot trajectories remain part of the planning state.Source: D. Prioritization of Subproblems and… · p. 7
  • Each planning step selects an unplanned object subject to ordering constraints, a robot subset, and a feasible task-assignment sequence leading to placement.A failed robot assignment prompts another choice; if none works, the planner backtracks over earlier placements.Source: D. Prioritization of Subproblems and… · p. 7

1) and 2) Selection of Object and Robots:

The planner prioritizes object and robot choices, then searches assignments and paths for a feasible subproblem. When infeasibility is uncertain, it can revisit rejected choices before backtracking.

1) and 2) Selection of Object and Robots:

  • Object choices are prioritized by a heuristic while excluding objects that violate application-specific constraints, such as stability or deflection limits.Source: 1) and 2) Selection of Object and Robots · p. 7
  • Robot subsets are prioritized by the latest busy time among their members, conservatively assuming work starts only when all are free.The text also notes estimated subproblem finishing time as an alternative prioritization.Source: 1) and 2) Selection of Object and Robots · p. 7

3) Path Planning and Action Sequence/Robot Rejection:

  • For each discrete choice, the planner checks action sequences and lower-bound subproblems, such as placement poses and mode-switch configurations, before solving the full path problem.Action-sequence feasibility is checked with breadth-first search; infeasible lower bounds guarantee infeasibility of the full problem.Source: 3) Path Planning and Action… · p. 7
  • Non-convex optimization and finite path-planning runtime prevent proving some assignments infeasible, so rejected choices may be revisited in deprioritized order.The text states this preserves eventual discovery of a solution if one exists.Source: 3) Path Planning and Action… · p. 7
  • If all robot and task assignments fail, the planner backtracks because previously placed objects may prevent the selected part from being placed.Source: 4) Backtracking · p. 7, 3) Path Planning and Action… · p. 7

4) Backtracking:

The demonstrations examine long-horizon construction, multi-robot coordination, and a real-robot experiment. The setup spans four models from a 15-piece tower to a 113-part pavilion, under stated structural and objective assumptions.

V. DEMONSTRATIONS & RESULTS

  • The demonstrations cover long-horizon scenarios, a coordination case requiring handovers, a real-robot experiment, and comparison with a modified classical TAMP solver.Source: §V · p. 8

A. Setup

  • The test models are a 15-piece sequential tower, a 36-brick wall for parallelization, a 52-piece well for scalability, and a 113-cassette pavilion for scalability.Source: A. Setup · p. 8
  • The setup treats placed parts as rigidly joined to neighboring parts and omits fastening and the structural support otherwise needed.The planning objective is feasibility (c = 0), except the real-robot smoothing step minimizes acceleration.Source: A. Setup · p. 8

1) Robots:

Across the experiments, the proposed method outperforms fixed-time sampling in speedup and computation-time scaling, while the tower’s congestion limits parallel gains. The evaluations also describe the robot models, task rules, ordering heuristic, and runtime patterns.

1) Robots:

  • The mobile manipulator, KUKA arm on a mobile base, and crane are holonomic; manipulation is modeled as gripping-by-touch unless otherwise stated.Source: 1) Robots · p. 8

2) Task Assignments:

  • Every place task must be followed by retract, preventing a robot from remaining where it could block another agent’s placement configuration.Source: 2) Task Assignments · p. 8

3) Ordering Heuristic:

  • The ordering heuristic favors parts with the most previously placed neighbors, while the placement constraint requires a connection to at least one placed part.No backtracking was required in the experiments, so the examples do not demonstrate or report backtracking frequency.Source: 3) Ordering Heuristic · p. 8

1) Execution Time:

  • For the tower and wall, adding agents yields diminishing execution-time speedup sooner in the tower, where placements occur in close proximity.Figure 8 reports medians and interquartile ranges across 10 runs.Source: 1) Execution Time · p. 8, Figure 8 · p. 8

2) Computation time:

  • Computation time scales approximately linearly with agent count; the tower scales worse than the wall, and keyframe solving consumes most planning time.The wall’s wider spatial distribution reduces agent interference.Source: 2) Computation time · pp. 8–9, Table I · p. 9

C. Comparison to fixed-time-sampling

  • In the seven-agent tower comparison, fixed-time sampling is sensitive to its time interval and cannot schedule otherwise feasible placements at slightly different times.The proposed method achieves better utilization in the example; the later-block parallelization of fixed-time sampling occurs by coincidence.Source: C. Comparison to fixed-time-sampling · p. 9
  • The method achieves better speedup with more robots and better computation-time scaling than fixed-time sampling, whose keyframe generation becomes restart-heavy in the congested tower.On the wall, fixed-time sampling achieves similar speedup because more space is available.Source: C. Comparison to fixed-time-sampling · p. 9

D. Demonstrations

The demonstrations span long-horizon mobile-agent assembly, heterogeneous-robot handovers, and open-loop execution on real robot arms.

1) Long horizon assembly:

  • The well used 6 agents (14.1 min computation; 2150 execution steps), while the 8-agent pavilion used 43.2 min and 3867 steps.The pavilion schedule illustrates the coordination involved in the long-horizon assembly.Source: 1) Long horizon assembly · p. 9, Figure 10 · p. 10

2) Handover scenario:

  • Three mobile KUKA arms and a tower crane required handovers to place the tower’s final three parts because each robot type had reach limits.The crane could not reach pieces on the floor, while the arms could not reach the tower top.Source: 2) Handover scenario · pp. 9–10, Figure 14 · p. 10

3) Real robot experiments:

  • Two Panda arms successfully stacked six boxes in an open-loop real-robot experiment, despite imperfect alignment.The execution relied on an accurate simulation model so the trajectories could run without adaptations.Source: 3) Real robot experiments · p. 10

VI. DISCUSSION & LIMITATIONS

The discussion reports scaling and execution results while identifying runtime, uncertainty, optimality, and modeling boundaries. It also states conditional properties of the search and path-planning procedures.

VI. DISCUSSION & LIMITATIONS

  • The algorithm is currently too slow for online replanning, with keyframe computation taking most of the time.The authors identify learned optimizer initializations and fewer sampled goal states as possible ways to reduce computation.Source: §VI · pp. 10–11
  • Execution under uncertainty in space or time may be more challenging than the demonstrated execution in a controlled environment.The paper suggests safe corridors or maximizing path clearance as possible ways to account for uncertainty.Source: §VI · p. 11

A. Discussion of Theoretical Properties

  • Depth-first search over assignments and action sequences explores possibilities; a feasible action sequence is guaranteed only if each object can reach its goal in finitely many actions.The path-planning methods cannot prove infeasibility, so the algorithm continues exploring nodes labeled infeasible.Source: A. Discussion of Theoretical Properties · p. 11
  • Each path segment is asymptotically complete only under uniform keyframe coverage and infinitely many returns to the subproblem.Joint keyframe sampling reduces, but does not eliminate, the risk of rejecting a sequence after finding a segment with no feasible continuation.Source: A. Discussion of Theoretical Properties · p. 11
  • Fixed paths must not block feasible later pick or place configurations, including those needed by resting agents.Source: A. Discussion of Theoretical Properties · p. 11

VII. CONCLUSION

  • The system factors assembly into subset-agent, single-object subproblems, then combines them using sampling-based path planning, joint mode-switch optimization, and a bidirectional space-time RRT.The space-time planner plans between keyframes amid moving objects and robots that were planned earlier.Source: §VII · p. 11
  • Across construction tasks, the approach scaled to many robots and objects; time-embedding versus fixed-time assignment yielded better robot utilization and lower execution and motion-planning computation times.The paper also reports that generated paths were executable in a real-robot experiment.Source: §VII · p. 12
  • Greedy decomposition sacrifices global optimality; real-construction deployment also needs richer models, including exact static-stability constraints.Source: §VII · p. 12
Loading 2106.02489v3…