Multi-Agent Collective Construction (MACC)

@ Biorobotics Lab, CMU [IROS 2026 Under Review]

Introduction

Most multi-robot construction planners can only build solid, blocky structures using identical cubic blocks. This work breaks that limitation — enabling robots to build hollow geometries like roofs, bridges, and cantilevers by introducing elongated cuboid blocks. The catch: cuboids are no longer rotationally symmetric, they collide with the environment in ways cubes don't, and path planning becomes dramatically more constrained.

We present a three-level hierarchical planner that stays tractable under these constraints: high-level abstract action sequencing via A*, an interface layer encoding action dependencies, and a modified Conflict-Based Search for collision-free multi-robot pathfinding. Validated on 200 randomly generated structures. IROS 2026 under review.

Methods

1. High-Level Planner: Abstract Action Sequencing

Before assigning robots to tasks, the planner needs to figure out what order blocks should be placed and removed to build the target structure — without getting the robots stuck. A* search computes this sequence while ensuring every action remains physically reachable before committing to it. The main cost driver is scaffolding: temporary blocks robots must place to reach higher levels, then remove when done. We developed heuristics specifically targeting this bottleneck.

2. Interface Layer: Action Dependency Graph (ADG)

Not every construction step needs to happen in strict order — some can run in parallel across multiple robots. The interface layer figures out which steps depend on each other by analyzing conflicts between candidate robot paths, then encodes those dependencies into a directed acyclic Action Dependency Graph. This determines how much parallelism the multi-robot system can actually exploit.​

3. Low-Level Planner — Multi-Agent Pathfinding with Constraints

With dependencies established, robots need collision-free paths to execute their assigned actions — while the world around them is actively changing as other robots place and remove blocks. We use a modified Conflict-Based Search with three new conflict types — cell-set, action-world, and edge-world — designed specifically to handle this dynamic environment.

Results

Construction Validation

The planner successfully assembled complex heterogeneous structures in 134 of 200 randomly generated test cases within a 1000-second limit. The remaining failures split between RAM exhaustion during high-level search (42 cases) and timeout at the low level (24 cases) — both pointing to well-defined bottlenecks with clear paths to improvement.​

Runtime Behavior

Low-level pathfinding dominated runtime in roughly 75% of successful cases. Critically, runtime variance correlated with structural geometry — not block count. Narrow corridors, internal cavities, and layered overhangs produced dramatically longer solve times than simpler structures of identical size.

Discussion

The clearest finding: two structures with the same number of blocks can differ by over 100x in solve time depending on their geometry. This means block count is a poor proxy for planning difficulty — spatial configuration is what matters, and geometry-aware heuristics are the most promising path to improving scalability.

The three novel CBS conflict types are the core technical contribution. They allow robots to plan paths optimistically in a changing world — treating actions by other robots as "pending" rather than unknown — which keeps the search tractable without sacrificing correctness guarantees.

My Contributions

First author. Led problem formulation, algorithm design, implementation, and experimental validation.

  • Designed the three-level hierarchical planning pipeline connecting abstract sequencing, dependency reasoning, and multi-robot pathfinding.

  • Developed and implemented three novel CBS conflict types enabling planning in a dynamically changing world state.

  • Built the benchmarking framework and ran evaluation across 200 randomly generated structures.

  • Led runtime analysis identifying structural geometry as the primary driver of planning complexity.