hierarchical_macc

Hierarchical Planning for Long-Horizon Multi-Agent Collective Construction
Shambhavi Singh*, Zejian Huang, Akshaya K Srinivasan, Geordan Gutow, Bhaskar Vundurthy, Howie Choset

Accepted at ICRA 2024!

Abstract

We develop a planner that directs robots to construct a 3D target structure composed of blocks. The robots themselves are cubes of the same size as the blocks, and they may place, carry, or remove one block at a time. When moving, robots are also allowed to climb or descend a block. A construction plan may thus build a staircase-like scaffolding of blocks to reach other blocks at higher levels. The order of block placement is important; for example, a block that sits atop other blocks must be placed after the blocks below it, and a block that needs scaffolding cannot be placed until after the scaffolding is. Prior works focus on end-to-end approaches that simultaneously plan for block placement order and inter-robot collisions. Larger structures are either intractable or yield high-cost solutions. A prior approach mitigates this by decomposing the structure into smaller components that can be planned for independently, but the computational challenge remains. We present a hierarchical approach that first (1) uses A* to determine a sequence of block placements and removals while ignoring inter-robot collision, then (2) identifies ordering constraints between block placement and removal actions, and finally (3) computes collision-free paths for multiple robots to perform said actions. Compared to an optimization approach that minimizes the number of timesteps to complete the structure, we observe a 100x reduction in computation time for comparable solutions.

Supplementary Material for ICRA 2024 submission: Experiments and Results

Test Structures

Structure 1 Structure 2 Structure 3
Structure 4 Structure 5 Structure 6
Structure 7 Structure 8 Structure 9
Structure 10 Structure 11 Structure 12

Random Structures in Environment Size 7x7x4

Random Structure 0 Random Structure 1 Random Structure 2 Random Structure 3 Random Structure 4
Random Structure 5 Random Structure 6 Random Structure 7 Random Structure 8 Random Structure 9
Random Structure 10 Random Structure 11 Random Structure 12 Random Structure 13 Random Structure 14
Random Structure 15 Random Structure 16 Random Structure 17 Random Structure 18 Random Structure 19
Random Structure 20 Random Structure 21 Random Structure 22 Random Structure 23 Random Structure 24
Random Structure 25 Random Structure 26 Random Structure 27 Random Structure 28 Random Structure 29
Random Structure 31 Random Structure 32 Random Structure 33 Random Structure 34 Random Structure 35
Random Structure 36 Random Structure 37 Random Structure 38 Random Structure 39 Random Structure 40
Random Structure 41 Random Structure 42 Random Structure 43 Random Structure 44 Random Structure 45
Random Structure 46 Random Structure 47 Random Structure 48 Random Structure 49 Random Structure 50
Random Structure 52 Random Structure 53 Random Structure 54 Random Structure 55 Random Structure 56
Random Structure 57 Random Structure 58 Random Structure 59 Random Structure 60 Random Structure 61
Random Structure 62 Random Structure 63 Random Structure 64 Random Structure 65 Random Structure 66
Random Structure 67 Random Structure 68 Random Structure 69 Random Structure 70 Random Structure 71
Random Structure 72 Random Structure 73 Random Structure 75 Random Structure 76 Random Structure 77
Random Structure 78 Random Structure 79 Random Structure 80 Random Structure 81 Random Structure 82
Random Structure 83 Random Structure 84 Random Structure 86 Random Structure 87 Random Structure 88
Random Structure 89 Random Structure 90 Random Structure 91 Random Structure 92 Random Structure 94
Random Structure 95 Random Structure 96 Random Structure 97 Random Structure 98 Random Structure 99