Provably Manipulable 3D Structures using Graph Theory

We identify barriers to a broader application of multi-robot systems to construction and deconstruction tasks, which represent important real-world problems, such as repairing 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. We extract desirable properties of graphs representing natural 3D structures and sketch a graphical representation to model and reason about structures composed of discrete cuboid blocks. We present a sample algorithm sketch for a non-trivial structure utilizing our model.

Authors

• John Harwell
• London Lowmanstone University of Minnesota
• Maria Gini

Keywords

• Multi-robot systems
• Swarm Robotics
• Construction
• Graph Theory