Provably Manipulable 3D Structures using Graph Theory

Abstract

We identify barriers to broader application of multi-robot systems to construction and deconstruction tasks, which represent important real-world problems such as repair of critical infrastructure of roads and levies after a disaster. We frame these tasks as instances of the parallel bricklayer problem, where independent agents must coordinate to concurrently manipulate aspects of a 3D environment without deadlocks. Extracting desirable properties of graphs representing natural 3D structures, we sketch a graphical representation to model and reason about structures composed of discrete, cuboid blocks. We present a sample algorithm sketch on a non-trivial structure utilizing our model.'

Publication
Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems