A Linking Invariant for Truss Robot Motion Planning

We introduce a new invariant for truss robot motion planning, called the link-augmented graph. This gives you a way to quickly tell if the start and goal configurations of a motion planning query might have a collision-free path between them.

Although this work was developed with Variable Topology Truss in mind, it can apply to any kind of truss robot, and even non-truss robots that have a similarly loopy kinematic structure. It does not consider the reconfiguration aspect of VTT at all, although it can be used in conjunction with a reconfiguration planner for VTT.

This work was motivated by the difficulty of using traditional probabilistic planners with truss robots. For most robots, if you randomly sample two valid configurations, usually there is some way to move from one to the other. It may be difficult to do so, but it’s rarely impossible. With truss robots, this is not the case. Truss robots have a graph-like kinematic structure with many closed loops, and these loops can be tangled up in various ways. Since collisions between the members are not allowed, changing the way these loops are tangled up is not possible.

Even if two truss robot configurations have the same kinematic graph structure, the members may be located in space in such a way that it is impossible to transform from one to the other without cutting a truss member. This is similar to the situation in knot theory: although the trefoil knot is homotopic to the figure-eight knot, the two are not ambient isotopic—there is no way to rearrange the trefoil to form the figure-eight.

Indeed, this work is largely inspired by knot theory and spatial graph theory, which is an extension of knot theory. Theoretically, you could try to solve knot theory problems using probabilistic planning techniques. You could discretize a loop into a set of points connected by edges and try to find a path that takes a trefoil configuration to a figure-eight configuration. However, the state space would be enormous and the planner would never be able to tell you with certainty that a path does not exist. Instead of doing this, knot theorists use invariants to aid their analysis. An invariant is some mathematical quantity that can be calculated from a configuration and doesn’t change after making any allowable motion to that configuration. Tricolorability is one example of a simple invariant for knots. Since the trefoil is tricolorable and the figure-eight is not tricolorable, any path between the two must have some illegal motion. We can say with certainty that no collision-free path exists between the two without needing to run any kind of planner.

We define a new invariant that applies to truss robots: the link-augmented graph. Essentially, this graph captures information about what loops are linked with other loops in the truss.  Given two configurations of a truss robot, you can calculate this graph for both configurations. If the graphs are isomorphic, then there might be a path between them. If not, there is certainly no path and you can skip planning. In the paper, we discuss in detail how to construct this graph and how to use it in planning. In some cases, it turns out that there are multiple ways that you could relabel the truss nodes to search for a path. We also introduce a variant of RRT that can handle this multiple-goal case.

• A. Spinos and M. Yim, “A linking invariant for truss robot motion planning,” Ieee robotics and automation letters, vol. 7, iss. 2, pp. 1424-1430, 2022.
  [Bibtex]

  @article{AS:MY:22,
  author={Spinos, Alexander and Yim, Mark},
  journal={IEEE Robotics and Automation Letters},
  title={A Linking Invariant for Truss Robot Motion Planning},
  year={2022},
  volume={7},
  number={2},
  pages={1424-1430},
  doi={10.1109/LRA.2021.3139941},
  pdf={https://www.modlabupenn.org/wp-content/uploads/2022/08/spinos_linking_invariant_RAL_ICRA2022.pdf},
  publisher={IEEE}
  }