Topological Reconfiguration Planning for a Variable Topology Truss

In many applications, trusses are ideal due to their high structural efficiency, as they consist of members that are only in pure tension or compression, resulting in reduced maximum stress [1]. The class of robots commonly known as variable geometry trusses (VGTs) can be obtained by replacing some or all of the members in a truss with linear actuators [2]. There are many applications for this type of robot, including parallel manipulators [3], long-chain actuators, collapsible structures for space applications [4], and locomotion platforms. Figure 1 shows a VGT with a high expansion/compression ratio for octahedral locomotion.

A variable topology truss (VTT) starts from the same truss framework as a VGT: linear actuators form the members (beam elements in the truss) and passive spherical joints connect the members at the nodes in the truss. However, the truss has the additional capability to self-reconfigure, changing its topology by merging or splitting nodes. That is, two separate nodes in the truss can dock to form one single node which connects all of the involved members. Similarly, a single node with a sufficient amount of members can undock into a pair of nodes. In this way, a VTT can be thought of as a chain-type self-reconfigurable robot [5] consisting only of linearly actuated elements and freely movable spherical joints.

While VGTs only have control over the shape or geometry of the truss, a VTT can additionally change the topology of the underlying truss. This brings benefits typically associated with reconfigurable robots; the VTT can select the topology which is most suited to the task at hand. For example, a single VTT may have the capability to self-reconfigure to suit many applications: a collapsible topology for storage, a multi-limbed topology for locomotion, or a long thin topology for an extended antenna application. This task flexibility is not possible with the single fixed topology of a VGT. An example of two structures which might be realizable from one system is shown in Fig. 2.

The additional reconfigurability of a VTT could have applications in space missions as a lightweight adaptable structure, or as versatile structural reinforcement to assist first responders during disaster scenarios. Our prior work [6] explores the challenges of the latter application using an earlier VTT concept. In other related work, we have developed methods for fast local path planning for VTTs. These methods use sampling-based planning [7], grid-based planning [8], or cell decomposition methods to move single nodes [9] or pairs of nodes [10] at a time. In this work, we introduce the hardware design and investigate the topological reconfiguration constraints. This allows us to answer questions about what truss topologies are achievable for a given VTT system and what intermediate topologies the system must pass through in order to reconfigure from one topology to another.

This paper extends a previous conference version of our work [11]. Whereas the previous work focuses on the mechanical design of the members and nodes (shown in Sec. 3) and introduces the concept of a topology network (Sec. 4); after the introduction and background section (Secs. 1 and 2), this new paper adds an analysis on the computational complexity for reconfiguration with explicit enumeration of truss topologies with up to 29 members (Sec. 5). In addition, in the prior conference version, we presented a six-bar VTT joint with a peg-in-hole latching design. In Sec. 3, we present the prototyped twelve-bar VTT joint with a pivoting catch latching system that has a larger area of acceptance.

The Stewart platform is one example of a VGT; it can be thought of as an octahedral truss with six-actuated members [2]. Rhodes and Mikulas investigated the use of VGTs as a collapsable, controllable beam for space applications [12]. The Tetrobot system is another example of a VGT with a variety of configurations, including a six-legged walker [13]. Lee and Sanderson presented dynamic rolling locomotion with an icosahedral Tetrobot [14]. The dynamics and control of general VGTs have been studied as well [15].

Many existing VGTs and families of VGTs are constructed from basic unit cells [2,16,17]. For example, Bolker and Roth claim to enumerate all possible VGTs, specifying that they must be statically determinate and composed of convex polyhedral cells. However, these criteria are too restrictive, as they eliminate many interesting structures. For example, the complete bipartite graph K_5,5 is generically rigid in 3D space [18], but is neither statically determinate nor composed of polyhedral cells. By removing a single edge, it can be made statically determinate; yet, it is still not composed of polyhedral cells. The only criterion we specify for a VTT in this paper is that the truss is a rigid framework. We consider all suitably rigid bar and joint structures, including statically indeterminate ones. Statically indeterminate structures are necessary to allow reconfiguration of the truss, since merging two nodes in a statically determinate truss results in an overdetermined structure.

A critical design parameter in improving the usefulness of VGT-type systems is the range of motion of the prismatic joints. In the past work referenced above, all of the actuators were standard single-stage linear actuators with an extension/compression ratio of less than two. Larger extension ratios will allow the systems to have larger workspaces or smaller storage volumes as well as higher dexterity over these larger workspaces.

VGTs and VTTs achieve geometric shape change by actuating member lengths. In a truss with variable member lengths, the nodes must consist of passive revolute joints. In the case of a VTT, where nodes may merge or split, the joints must also be chainable to support the connection and disconnection of an arbitrary number of members at a single node.

The member module pictured in Fig. 3 is the fundamental unit of the VTT. It consists of an active prismatic joint with two passive chainable spherical joints, one attached at each end. Figure 1 has twelve of these member modules joined together with passive (non-reconfigurable) sphere nodes.

The ideal prismatic joint is one with a large extension/compression ratio. Collins and Yim have developed such an actuator called the Spiral Zipper [19], which can be seen in Fig. 3 as the main column of the member module. In other applications, the Spiral Zipper has demonstrated extension ratios in excess of 14:1.

The Spiral Zipper operates both as a prismatic actuator and a structural component. It extends and retracts a rigid, lightweight tube by nesting the features in the top of a band to the matching features on the bottom. The extension ratio is only limited in principle by the amount of stored band and the material strength. The band forms a circular tube which is the optimal shape for stiffness-to-weight ratio under buckling loads, the most likely mode of failure for slender truss beams. The zipping feature interface is strongest in compression, although it can support small torsions and moments. To support tension, the actuator has a reinforcing winched cable on the inside of the tube. Experimentally, we have shown strength-to-weight ratios of approximately 10:1 for a prismatic actuator capable of extending 1 m with a plastic band. Spiral Zipper tubes made of acetal plastic, 1.5 m long, have been shown to support 530 N. We have also shown the tube can be extended as fast as 0.45 m/s.

In the member module, we use enough band to give the column an 8:1 extension ratio. The spherical joints on each end add some additional fixed length to the member, resulting in an overall member extension ratio of about 2.5:1.

To maintain the advantageous decoupling of moments and forces, the system needs passive spherical joints at the nodes of the truss. The joints should satisfy the following:

1. All members joined at a node must be constrained so that their longitudinal axes pass through the node center, but the members should be free to rotate in any of the degrees of rotational freedom about the node center.

2. The node must be able to constrain an arbitrary number of truss members. The number of members at a node may change during topological reconfiguration.

3. The nodes must minimize interference between members as the angles between members change.

To satisfy the first condition in practice, the truss members themselves do not need to physically occupy the node center as long as they share a common virtual center of rotation. Universal joints and spherical ball joints are typical candidates for a truss node; however, they are not chainable to support merging of nodes. Instead, a spherical link chain, made up of links of revolute joints which rotate about the node center, can provide this behavior [20].

A mechanism similar to a concentric multilink spherical (CMS) joint first developed by Hamlin [21] for the Tetrobot Modular Robot satisfies the design, in particular reducing interference. To provide the ability to attach and detach multiple joints at a single node, which was not part of the CMS joint, we add an attachment post and a pivoting catch which can dock to this attachment post. We call this type of spherical joint a VTT joint, it is illustrated in Fig. 4.

There is one additional practical concern that is relevant for terrestrial VTT applications, where the truss may need to apply forces to the environment. It is desirable to have the nodes that touch the environment do so in such a way that all external forces pass through the node center. The simplest way to achieve this is to place a physical sphere in the node center. However, a reconfiguring VTT cannot have a sphere in the center of every node, since this would prohibit merging two nodes that both have spheres. The placement of physical spheres in the truss nodes depends on the application and expected motion plan for a VTT.

The CMS joint is characterized by an offset planar hinge that forms a six-bar linkage. In Tetrobot, this offset allows multiple joints to be connected together manually to a single truss member using a shoulder screw. In the VTT joint, shown in Fig. 4, one end of the linkage is permanently attached to the truss member, along with an alignment post on the longitudinal axis of the member. The distal end of the linkage is a catch that can dock with the alignment posts on other members. When the catch of one member is docked with the alignment post of another member, the two members are constrained to move around the same spherical center. When the endpoints of multiple member modules are brought together, the spherical joints can dock to form a chain of arbitrary length with a free alignment post and catch at either end of the chain. Then, all the members at a node are constrained to move about the same spherical center. Figure 5 shows a chain of three VTT joints around a sphere.

To latch two member modules together, the pivot catch on the end of one linkage approaches the central post on the other member module. Once contact is made, guiding features on the catch help align the linkage plane with the axis of the post, increasing the area of acceptance. Next, the linkage extends until the catch is fully aligned with the post, so precise positioning is not required on the part of the linkage actuator. Finally, a sleeve slides upwards and captures the catch. As a result, the catch is free to pivot about the central post, but the post axis is held in the correct position for the truss constraints. This process is shown in Fig. 6.

Two nodes can be brought together and merged by docking their joint chains, and a single node can split into two by undocking in the middle of the joint chain. The order of the members in the chain can be rearranged by docking the ends of the chain to form a closed loop, then undocking at a different point in the loop.

When all of the VTT joints at a node are docked into a loop, the joints are completely passive. They constrain the truss members by virtue of their geometry, and all of the degrees-of-freedom in the VTT are controlled by actuating the lengths of the members. However, in order to autonomously perform the docking process, lightweight actuators are needed to control the position of the free linkage of an open chain. Before a chain is undocked, the actuators would connect to the linkage using a clutch mechanism to control the motion of the linkage. Once docking is complete, these actuators disconnect to return the joint to its typical passive state. We omit these actuators for simplicity in our current prototype and move the free linkages by hand as a proof-of-concept.

The other distinguishing feature of the VTT joint is the number of bars in the linkage. The main limitation of the six-bar linkage in the CMS joint is the relationship between the maximum angle and the size of the physical sphere that could fit at the virtual center. The sphere diameter needs to be at least as large as the actuator diameter to be a useful environmental contact, and with a six-bar linkage, the central pin joint collides with the sphere at moderate angles. Our novel 12-bar linkage has the same spherical motion and offset properties as the six-bar linkage, but the additional links allow a larger range of motion over the sphere surface with shorter link lengths. Figure 4 shows the VTT joint in its fully extended collision-free position at 165 deg. If there is no physical sphere, the joint can extend further, to about 175 deg. In fact, any even number of additional links can be used to extend the six-bar mechanism with a repeated series of rhombuses, in a similar way to a pantograph or scissor mechanism. If the total number of links is a multiple of four, then it is possible to replace the central rhombus section with a kite-shaped section while still preserving the spherical motion property. This kite-shaped section can be most clearly seen in Fig. 4, and it greatly improves the clearance over the sphere.

We have built a simple VTT, shown in Fig. 7, to demonstrate this reconfiguration capability. This truss has 18 members, 12 of which form an outer octahedron. The remaining six members form two internal tetrahedra. The internal nodes associated with these six members can merge and split according to the process described in Sec. 3.2.

To reduce the manufacturing burden, some of the external members use a fixed-length aluminum extrusion instead of the typical Spiral Zipper. The internal nodes use the reconfigurable VTT joints, while the external nodes use non-reconfigurable CMS joints for simplicity. Since these external nodes need to contact the environment and do not reconfigure, we place a physical sphere at each of their centers. To keep the physical spheres in place, we pin them to one arbitrary member at each node.

A VTT has the capability to change from one truss topology to another by merging or splitting nodes. Yet, there are limitations on which topologies can be reached by a given VTT. For example, trusses shown in Figs. 13(a) and 13(b) have the same number of nodes and members, but there is no way to reconfigure from one into the other. This section discusses the rules that govern possible reconfiguration actions.

We give the term configuration the standard definition in robotics: a set of parameters that describes the complete specification of all of the points in a robot system. A VTT consists of some fixed number of member modules, so the configuration must encode both the spatial locations of all of the members as well as a description of how the members are connected to one another. We call the description of the connections between the members the connectivity of the truss. The natural choice to describe the connectivity is a simple graph with labeled edges, with each graph edge corresponding to a truss member. Then, to fully specify the physical locations of the members, one choice is to provide an embedding of this graph, which is a specification of the point in 3D space of each node in the graph. The member lengths can be unambiguously determined from the node locations, while the reverse is not true. Using a graph embedding to represent the full configuration space greatly simplifies the kinematics.

When performing high-level planning and design, we often would like to disregard the labels from the labeled graph representation of the connectivity. This yields the topology of the truss, which is an isomorphism class of truss connectivity. The truss topology can be represented by an unlabeled graph. In other words, two trusses are said to have the same topology if there is a graph isomorphism between their graph representations. The truss topology provides the most general specification that corresponds to the tasks a particular robot configuration is suited to perform.

We call the motion that only moves the position of the nodes a geometric reconfiguration, and a motion that merges or splits nodes a topological reconfiguration. Figure 8 shows a simple 2D example. Any single topological reconfiguration action necessarily changes the number of nodes in the graph representation, but the total number of edges must remain the same. The edges correspond to physical actuators; they cannot vanish or reappear, nor can two actuators occupy the same location. Consequently, nodes that are first-order neighbors—nodes directly connected by an edge—cannot merge. If first-order neighbors in a graph were to combine, the edge between them would be deleted. Similarly, nodes that are second-order neighbors—the neighbor of a neighbor—also cannot merge. If second-order neighbors were to combine, two edges would collapse to a single edge. Therefore, the valid list of node merges for a given connectivity is restricted to the list of third or greater order neighbors.

A VTT configuration can be fully represented by a graph G(V, E) and an embedding function $P(V)↦R3$ where V is the set of truss nodes and E is the set of members in the truss. We use n = |V| as the total number of truss nodes and m = |E| as the total number of members in the truss. The embedding function P specifies the location of each truss node in 3D space. This combination of graph and embedding (G, P) is typically called a framework [22].

A VTT is required to be a rigid structure to maintain its shape. This means at all times, the truss must be a rigid framework. In order to maintain controllability of every node on a VTT robot, it is necessary for the truss to satisfy the stronger condition of infinitesimal rigidity. Infinitesimal rigidity is the property that no infinitesimal motions can be assigned to the nodes of the truss without violating the distance constraints imposed by the member lengths, aside from the motions that correspond to the six degrees-of-freedom of a rigid body [22]. However infinitesimal rigidity is a property that depends on the specific embedding of a framework. A more general property is generic rigidity, a property of the graph G alone (or equivalently, a property of the topology alone). A generically rigid graph is rigid “almost everywhere,” and if it is rigid with one embedding, it is rigid in some neighborhood of that embedding [22]. Similarly, a graph that is generically non-rigid will be flexible “almost everywhere.” There may be embeddings where a generically rigid graph becomes infinitesimally flexible, and these correspond to singularity configurations of a VTT. Figure 9 gives one such example in 2D space.

We use the fact that if a graph has at least one infinitesimally rigid configuration, then the graph is generically rigid. A random embedding is assigned to a graph, and infinitesimal rigidity is checked by computing the rank of the rigidity matrix. If the graph is not infinitesimally rigid, then the embedding is perturbed to ensure its position is not singular. Since generic (non-singular) configurations occur “almost everywhere,” this method works well in practice.

Truss topologies that are not generically rigid have no infinitesimally rigid configurations, so these topologies must be avoided during topological reconfiguration. Any merging or splitting of nodes must preserve the generic rigidity of structure. Additionally, singular configurations of generically rigid topologies must be avoided during geometric reconfiguration.

Minimally rigid structures are frameworks that have precisely the number of members to guarantee rigidity; the removal of any member results in flexibility. The above constraint inequality becomes an equality, and in this case, the number of members must be a multiple of three. These structures are statically determinate and as such are much easier to control than overconstrained structures.

Every three members we add to a minimally rigid truss allows us to add one extra node. As we will see in Sec. 4.5, the complexity of a graph is heavily dependent on the number of nodes, and the number of possible truss topologies will grow rapidly for every three members added.

Given a truss topology, we can enumerate all of the possible reconfiguration actions that preserve the generic rigidity of the structure. There are two basic reconfiguration actions: merging two nodes, and splitting a node. In this section, we will describe how to enumerate all possible ways of performing a merge or a split.

To enumerate the possible ways to merge two nodes, we need to generate all possible pairs of nodes on the truss and determine which are third- or greater order neighbors. First-order neighbors can be determined from the adjacency matrix, which can be built in O(n²) time, where n is the number of nodes. The second-order neighbors can be determined from nonzero entries of the square of the adjacency matrix, which takes O(n³) time via matrix multiplication. Any remaining pairs of nodes will be third-order or greater, and there may be O(n²) such pairs in general. We need to check that the result of merging each of them is rigid. Updating the graph data structure to merge two nodes takes O(n) time, which is negligible compared to checking rigidity. We check rigidity by calculating the rank of the rigidity matrix, which takes O(mn) time. Checking rigidity for each candidate pair of nodes is the most computationally complex step, so the whole procedure is O(mn³).

To enumerate the possible ways to split a node in a truss, we need to enumerate all of the ways of picking a set of members from each node. Since it is a necessary condition that a rigid graph has minimum node degree three, we only need to be concerned about splitting nodes that have six or more members, and we only need to pick sets of minimum size three. Additionally, we can ignore any trusses that are minimally rigid. In an n-node truss, any given node may have a maximum degree d = n − 1. Since choosing a set of members is identical to choosing its complement, we can designate one of the members to always be in the set. There are at most $(d−13)+(d−14)+⋯+(d−1d−3)$ choices, which is O(2ⁿ). Once again, checking rigidity takes O(mn) time, so the total time is O(mn2ⁿ). Although this term is exponential, for the trusses investigated in this paper n is small enough that this procedure is fast in practice.

This process enumerates all of the possible reconfiguration actions, however, we are often only interested in the non-isomorphic results. Since we have a large number of graphs, pairwise isomorphism testing is inefficient. Instead, for each resulting graph, we compute a canonical representation of the graph. Isomorphic graphs will have identical canonical representations, so it serves as an identifier that can be directly compared. Although computing a canonical representation is very difficult in general, the well-known nauty program is very efficient for small graphs (<100 nodes) [24].

In Sec. 4.5, we enumerate a list of all reconfigurable truss topologies with up to 29 members. From this list, we can summarize their reconfiguration capabilities with the statistics given in Table 1. The table gives the maximum and average number of merges and splits for m-member reconfigurable truss topologies. For example, among all 24-member trusses, the maximum amount of merges that any given truss topology that can perform is six. The average given is the median among all trusses that can perform such an action. For example, among all 24-member truss topologies that can perform a merge, in the median case, there is only one way to perform a merge. This table shows both the total number of ways to apply a reconfiguration action, which results in many different truss connectivities, and how many of these actions result in distinct (non-isomorphic) truss topologies. Using 24-member trusses as an example again: although there are trusses with six different ways of picking pairs of nodes to merge, these choices never result in more than five non-isomorphic truss topologies. This table can be thought of as the true “worst cases” and “average cases” of the theoretical bounds given above.

We can see that for most small trusses, if a truss topology can perform a merge, there is typically only one way to merge two nodes. On the other hand, if a truss topology can perform a split, there are typically many distinct ways to split a node. In Sec. 5, we will see the implications of this on the space of reachable topologies for any given VTT.

From the restrictions on reconfiguration, we can determine the minimal reconfigurable trusses.

As we will see in Sec. 4.5 where we enumerate all reconfigurable topologies with 18 members, only trusses with seven or eight nodes are possible, since the complete graph with six nodes only contains 15 members, and a truss of 9 nodes would violate the constraint inequality (2). There are five non-isomorphic graphs with seven nodes and 18 edges [25], and they are pictured in Fig. 10. All of them are generically rigid in 3D. One of the five graphs (Fig. 10 (1)) corresponds to the complete graph with six nodes with one additional node connected by three edges. This graph is incapable of splitting any node without losing generic rigidity. The remaining four graphs correspond to the four 18-member VTTs that are capable of topological reconfiguration.

Since reconfiguration is achieved by node splitting and merging, the number of members is preserved throughout topological reconfiguration of a VTT. Given a prescribed number of members with which to construct a VTT, what choices exist for putting them together such that they can reconfigure? For relatively small trusses, it is feasible to enumerate all possible truss topologies that can reconfigure in some way. In this paper, we consider trusses with up to 29 members in detail.

Non-isomorphic connected graphs with a specified number of nodes can be generated efficiently with programs such as geng [24]. From the list of all non-isomorphic connected graphs up to certain size, we can check each graph for rigidity and check whether it has any reconfiguration actions available. The results can be found in Table 2. Since the number of members is preserved throughout reconfiguration actions, the table is organized by number of members. Recall, for an n-node truss, the minimum number of members is 3n − 6 to satisfy the rigidity condition, and the maximum is n(n − 1)/2 for the complete graph. In the table, combinations of m and n that result in minimally rigid trusses are marked with an asterisk.

For 27- to 29-member trusses, there are too many 11-node graphs to check all of them for rigidity in a reasonable amount of computer time. In these cases, we start with the much smaller number of reconfigurable ten-node graphs and enumerate all of the non-isomorphic ways to perform a node split. This gives the correct result for the number of reconfigurable 11-node graphs, but does not reveal how many non-reconfigurable connected graphs are rigid or flexible.

We can see some interesting results in Table 2. The total number of connected simple graphs increases roughly exponentially in the number of nodes. Similarly, the number of rigid graphs and reconfigurable graphs grow exponentially in the number of nodes. This explains the large jump in the number of reconfigurable graphs every three members, since this results in an additional possible node. As the trusses get larger, the proportion of rigid trusses that are reconfigurable increases. Additionally, trusses that are overconstrained by three or more members are highly likely to be reconfigurable. This trend can be seen in Fig. 11, which combines the exhaustive data in Table 2 with additional sampled data for trusses that are too large to exhaustively enumerate. Thus far, sampling results indicate that all rigid trusses overconstrained by four or more members are reconfigurable, and all rigid trusses with at least 48 members (or equivalently, at least 18 nodes) are reconfigurable. This is promising for the practical application of VTT systems. If we have a way to generate desired goal topologies, then for larger systems, they will always or almost always be reconfigurable.

To describe the reconfiguration capability of a VTT, we introduce the topology network of a VTT. The topology network can be thought of as a “graph describing the relationships of graphs.” In the topology network, each vertex corresponds to a truss topology. This correspondence is one-to-one; a network vertex can be uniquely labeled by the canonical graph representation of the truss topology. Two vertices in the network are connected by an edge if a single topological reconfiguration action can take a VTT configuration in the first topology to the second topology. Figure 12 shows an example network of three truss topologies, which captures the reconfiguration capability of the VTT described in Sec. 3.3.

To keep the terminology of a network distinct from that of an individual truss, we refer to the elements of a topology network as vertices and edges. In contrast, the topology of a truss is a graph describing an arrangement of nodes and members. We avoid the use of the term “graph” to describe the topology network to reduce ambiguity.

The topology network for a VTT can be generated by starting with some initial truss topology, computing its canonical form, and adding it as the first unexplored vertex in the topology network. For each unexplored vertex, we can discover the adjacent vertices by applying all valid topological reconfiguration actions as described in Sec. 4.3. After applying a valid topological reconfiguration action to the current truss, the resulting truss connectivity is put into its canonical form to check if it is isomorphic to any of the existing truss topologies in the topology network. If it is a new truss topology, then it is added as a new unexplored vertex to the topology network. An edge is then added between the current vertex and the vertex corresponding to the new truss topology. This process is repeated for any new unexplored vertices until the graph is fully explored.

Figure 13 shows two more complicated examples of VTTs and their associated topology networks. We can see that these networks feature dense clusters of vertices with a small number of paths connecting the clusters. This corresponds to the results we discussed in Sec. 4.3. Recall, trusses that are overconstrained enough to split a node can typically do so in many different ways to arrive at many different topologies. This also matches our expectations from Sec. 4.5; splitting a node increases the number of nodes in a truss, and in general, the number of unique truss topologies increases exponentially with the number of nodes.

However, any truss topologies that have the maximum number of nodes for their member count can only reconfigure by merging two nodes. As we saw in Sec. 4.3, for moderate numbers of members, most of these truss topologies only have one non-isomorphic way to merge two nodes. This implies that if we arrived at this truss topology by splitting a truss node, the only thing to do is merge that truss node right back together again. These truss topologies are peripheral vertices in the topology networks, forming the clusters around the more overconstrained trusses, which have fewer nodes. It is the smaller number of truss topologies that have multiple ways to merge truss nodes that form the “bridge” vertices in the topology networks. When designing search algorithms for VTT topological reconfiguration, it may be beneficial to prune these peripheral vertices, since they won’t be part of any shortest path unless they correspond to the start or goal topology. As the total number of members (and hence nodes) increases, we expect the average truss to have more ways of merging those nodes. For large trusses, their topology networks will likely have a larger proportion of bridge nodes to fewer peripheral nodes.

In Fig. 13, these particular topology networks only contain topologies with 8 or 9 truss nodes, with the eight-node trusses forming the centers of clusters of nine-node trusses. For VTTs with more members, there may be more hierarchical levels of clustering. For example, the topology network of the 24-member VTT in Fig. 15 contains truss topologies with 8, 9, or 10 truss nodes. In that case, the eight-node trusses form the center of clusters of nine-node trusses, which in turn form centers of clusters of ten-node trusses.

Any given topology network can also be thought of as a single connected component in a universal topology network, an infinite graph that describes the relationship between all truss topologies. If we start the above procedure with all of the enumerated reconfigurable graphs with m-members (generated using the procedure from Sec. 4.5), we can generate the complete topology network for all m-member trusses. This procedure only takes a single pass through the list of starting trusses to build the topology network, because the result of any reconfiguration action is guaranteed to already be in the starting set. We could also consider all rigid trusses to be part of the starting set, in which case any rigid but non-reconfigurable trusses would form isolated vertices in the topology network.

Given start and goal truss configurations, the topology network can be used to quickly eliminate unreachable goal configurations. If the topology of the goal configuration does not lie in the same connected component as the topology of the start configuration, then there is no path through configuration space that connects the start and goal configurations. However, these graphs do not consider self-collisions or actuator constraints, so the existence of a path through the topology network does not guarantee that a path through configuration space exists. A more sophisticated planning procedure would be required to find a path that satisfies all of the physical constraints.

In prior work, we have proposed several constraint-aware methods for local VTT reconfiguration planning [7–10]. These methods are effective for finding shorter paths with a few topological reconfiguration actions between the start and the goal. However, these methods are not aware of the structure of the topology network. By combining the local planners with some guidance from the topology network, it may be possible to achieve effective path planning for more complicated reconfiguration sequences.

As a practical matter, it is easier to manufacture VTTs with smaller numbers of members, so it is useful to explore the smaller number of member systems exhaustively. Recall the five non-isomorphic graphs with seven nodes and 18 edges from Fig. 10, which include the four smallest reconfigurable trusses. Figure 14 shows the topology networks of the five trusses. They form five separate connected components, which implies none of these trusses can reconfigure into any of the other four. The 14 additional vertices (6–19) in the network represent the topologically unique trusses that can be obtained by splitting nodes from the 18 member and seven-node trusses. This is also reflected in our enumeration results from Table 2. There are 658 non-isomorphic connected graphs with eight nodes and 18 members. Of those, 284 are non-rigid, 360 are rigid but incapable of reconfiguration, and the 14 shown here are reconfigurable.

A similar process can be applied for 19- and 20-member structures. There are two 19-member topologies with seven nodes, each of which can reach three eight-node topologies. There is only one 20-member topology with seven nodes, and it can reach two eight-node topologies.

With 21 members, rigid nine-node trusses become possible, and the connected components of the topology networks begin to exhibit more interesting organization. Figure 13 shows two such examples. There is only one 21-member truss topology with seven nodes, which corresponds to K₇—the complete graph on seven nodes. It can reconfigure by splitting into an eight-node topology, but this eight-node topology cannot reconfigure further. Therefore, all other reconfigurable trusses with 21, 22, or 23 members involve merges and splits between eight and nine-node topologies.

Rigid ten-node truss topologies become possible with 24 members, and again, there is a jump in complexity of the topology networks. The maximum size of the topology networks increases rapidly with the maximum number of nodes in the truss. Figure 15 gives an example of a VTT with 24 members and ten nodes. Here, the reachable connected component has 38,217 topologies.

We have applied this same procedure to generate the topology network for all VTTs up to 29 members. Beyond this becomes expensive to compute. There are several interesting properties that emerge, summarized in Table 3.

First is the number of connected components in the topology network, and the size of the largest one. We can see that the number of connected components is correlated with the total number of reconfigurable trusses, but it does not increase as quickly. For larger trusses, these connected components are very non-uniform in size. There are many small components with only a handful of topologies, but the vast majority of truss topologies belong to a small number of connected components. Additionally, it seems that these largest connected components tend to coalesce into a single component as the number of members increases. For example, for 24-, 25-, and 26-member trusses, about half of the truss topologies are in the largest connected component. For 27-, 28-, and 29-member trusses, over 99.9% of reconfigurable truss topologies are in the largest connected component. This is promising for planning, since it is likely that two randomly selected reconfigurable trusses with the same number of members have a connecting path. Table 3 lists the probability of this occurring, up to 29 members.

We might imagine that at some point, the number of connected components in the topology network will begin to decrease, and perhaps all sufficiently large VTTs are in the same component—provided they have the same number of members. Since the number of truss topologies increases exponentially, it is unlikely we will ever arrive at this answer by exhaustively computing the topology networks.

Another interesting property is the graph diameter of the connected components in the topology network, also listed in Table 3. This is the maximum length of the shortest path between every pair of vertices in the network. It can equivalently be considered as the maximum eccentricity, where the eccentricity of a vertex is the maximum length of the shortest path to every other vertex in the network. For 18- to 26-member trusses, the diameter was determined exactly by computing the eccentricity of every vertex. For 27- to 29-member trusses, we can only compute the eccentricity of a random sample of vertices. The diameter is bounded below by the maximum eccentricity of the sampled vertices and bounded above by twice the minimum eccentricity of the sampled vertices, so we provide upper and lower bounds for the true diameter. We can see that this increases very slowly with the size of the trusses. For example, although there are over 200,000 reconfigurable 24-member truss topologies, the worst-case diameter of any 24-member connected component in the topology network is 22. This means if two topologies are in the same connected component, then you can reconfigure from one to the other with only 22 reconfiguration actions. If we can find an effective search heuristic, then it may be possible to efficiently find paths between very large truss configurations, despite the large and highly connected search space.

Finally, we can return to the tower and dome example from Fig. 2. Both of these topologies have 27 members, and both are rigid and reconfigurable. Given the statistics from Table 3, it is no surprise to find that they are in the same connected component. A simple breadth-first search in the topology network starting at the tower topology gives a shortest path to the dome topology, which passes through ten intermediate topologies. This sequence is shown in full in Fig. 16. The embeddings of the intermediate steps were generated using a force-directed graph embedding algorithm, so the geometry of a real collision-free path may look very different.

Variable topology trusses are a novel extension to the class of robots known as variable geometry trusses. The ability to topologically reconfigure expands the capabilities of the robot system. A hardware design that implements the motion and reconfiguration of a VTT was presented. Constraints on reconfiguration and the allowable truss topologies were introduced, leading to the derivation that 18 members are required for topological reconfiguration and to a procedure for enumerating reconfigurable trusses. By exhaustively exploring reconfiguration options, the relationship between all of the topologically distinct reconfigurable structures for 18 up to 29 members were characterized. Topology networks were introduced as a way to visualize the potential for different configurations to reconfigure to each other and the steps to achieve this reconfiguration.

Future work includes performing a comprehensive study of structures with more members and identifying promising configurations for common robotics tasks. The motion and reconfiguration planning problems for VTTs also need to be further developed. These problems might be tackled by combining our prior work in local planning with the global methods described in this work. We suspect that topological reconfiguration can be used to move past singular configurations and avoid obstacles, expanding the workspace of VTTs.

This work was supported by the Air Force Office of Scientific Research (AFOSR) contract FA2386-17-1-4656 and the Korean Ministry of Trade, Industry, and Energy (MOTIE). The authors would like to thank our collaborators Frank Park, Jongwon Kim, Sumin Park, and Eugene Park at the Seoul National University and TaeWon Seo at Hanyang University, as well as previous Univ. of Penn. GRASP Lab members Thulani Tsabedze and Daniel Edgar.

There are no conflicts of interest.

The datasets generated and supporting the findings of this article are obtainable from the corresponding author upon reasonable request.