A Fast Configuration Space Algorithm for Variable Topology Truss Modular Robots

Variable topology truss (VTT) is a modular robotic system which is composed of multiple edge modules including a linear actuator as the truss member plus the two ends of the member that attach or detach from other ends to form the node. A VTT usually has at least 18 actuated degrees-of-freedom (DOFs) and typically more than 21 DOFs. Thus motion planning for these systems involves high dimensions with some physical constraints. Also members forming a variable topology truss generally span the workspace in a very non-uniform manner as the truss configuration creates a complicated configuration space.

As a modular robotic system, a VTT can reconfigure itself into different morphologies. There are two different types of reconfiguration motion: geometry reconfiguration and topology reconfiguration. Geometry reconfiguration involves changing the length of member modules in a VTT resulting in the motion of corresponding nodes. Topology reconfiguration involves changing the connectivity among members. In general, any topology reconfiguration also requires geometry reconfiguration in order to enable the connectivity changes. This work focuses on geometry reconfiguration and presents a fast algorithm to compute configuration space of a node in a VTT, including its free space and obstacle region.

In a VTT, it is shown that the obstacle region for a given node is fully defined by members not constructing this node. There are three cases in total shown in Fig. 1. For a given node in a VTT, its whole obstacle region can be computed by looking for the these area generated by every neighbor node and every member not constructing this node.

Fig. 1 Three cases of obstacle region of node . If lies in any blue region or ray, there will be collision happening.

With this obstacle region, we present a fast algorithm to compute the boundary of the free space containing the current position of the node. For path planning of this node, we decompose this free space into multiple convex cells and Dijkstra algorithm or other efficient graph search algorithm can be applied to find an optimal path. An example using a simple VTT is shown in Fig. 2.

Fig. 2 From left to right: The obstacle region of node is computed first, and then the boundary of the free space of node containing its current position can be searched efficiently. This free space is then decomposed into multiple convex cells and path planning for this node can be done using Dijkstra algorithm.

When changing the shape of  a VTT, motions of multiple nodes are usually involved. The efficiency of single-node planning makes it applicable to simplify the planning of multiple nodes. Given a multiple node planning task, these nodes will be moved in a sequential manner to achieve the shape morphing goal. For example, we can achieve the shape morphing tasks in Fig. 3 efficiently. 

Fig. 3 Left: A VTT in cubic shape can be reconfigured into a tower. Right: A VTT with an arm can be reconfigured into a tower.