Triangle-Decomposable Graphs for Isoperimetric Robots
Nathan Usevitch, Isaac Weaver, James Usevitch
AI summary
Problem
Isoperimetric robots have only been demonstrated in a single 3D shape due to strict geometric constraints that limit viable configurations. This paper addresses the fundamental design question of which graph structures can be partitioned into unique triangles to form functional isoperimetric robots.
Approach
The authors develop graph-theory-based algorithms, including exhaustive search and integer programming, to test triangle partition feasibility. They also enumerate all minimally rigid decomposable graphs up to nine nodes and provide a constructive method to combine smaller partitioned graphs into larger structures.
Key results
- Novel algorithms to partition arbitrary graphs into unique triangles
- Complete enumeration of all minimally rigid triangle-decomposable graphs up to 9 nodes
- Constructive method for combining partitioned subgraphs to build arbitrarily large robots
- Workspace analysis and rigidity characterization for enumerated configurations
Why it matters
Provides a systematic design framework for engineers and researchers to create diverse, large-scale, human-safe inflatable robots for space exploration and soft robotics.
Abstract
Isoperimetric robots are large scale, untethered inflatable robots that can undergo large shape changes, but have only been demonstrated in one 3D shape- an octahedron. These robots consist of independent triangles that can change shape while maintaining their perimeter by moving the relative position of their joints. We introduce an optimization routine that determines if an arbitrary graph can be partitioned into unique triangles, and thus be constructed as an isoperimetric robotic system. We enumerate all minimally rigid graphs that can be constructed with unique triangles up to 9 nodes (7 triangles), and characterize the workspace of one node of each of these robots. We also present a method for constructing larger graphs that can be partitioned by assembling subgraphs that are already partitioned into triangles. This enables a wide variety of isoperimetric robot configurations.