Reconfiguration as state space exploration

The problem of RoFIBot reconfiguration can be reduced to a state space search, with configurations as states, and atomic steps (joint rotations, module connections, and module disconnections) as transitions between them. We can also compare the shapes of different RoFIBot configurations by using the shape comparison algorithm introduced in another article, which deconstructs the RoFIBots into sets of landmark points, and attempts to align them so they match.

This allows us to group configurations with the same shape into one state - we define an equivalence relation on the set of all configurations: configurations A and B belong to the same class when their shapes are equal. Then the size of the state space is reduced exponentially by using the shape classes as states instead of individual configurations; every RoFIBot shape can be described by a lot of different configurations, which differ only in the concrete permutations of modules, components, docks, and connection orientations. In case the only important factor in the current reconfiguration task is the overall shape of the robot, not the actual goal configuration, the smaller shape state space can be used to find shorter reconfiguration plans, and possibly find them more effectively than by searching through all possible configurations.

However, we must define how to represent shapes in the state space in a way that preserves the existence of reconfiguration plans between any two configurations in the original state space. We would also like the resulting reconfiguration plan to be a sequence of configurations which differ only by an atomic step, and not have to also permute the components.

Representing shapes

Although a shape can be represented by its landmarks (points on the surface of the object uniquely defining its shape), using only a set of points would complicate the application of atomic steps: when we rotate a joint, how should the landmark points rearrange? Without additional information, this is difficult to determine. The simplest solution is to use an arbitrary configuration with the desired shape, and compare individual states by comparing the shapes of their underlying configurations. The transitions between the shapes can then still be atomic steps.

Neighbours of shapes

Each configuration has a number of neighbouring configurations in the state space - the configurations gained by joint rotation or module reconnection (one atomic step away). Similarly, each shape has neighbouring states in the state space, formed by groups of configurations with the same shape; these neighbours must be reachable by atomic steps from the first shape. However, using configurations to represent shapes leads to more possible representatives of each shape, and therefore different neighbours for each representative. For the shape state space to be correctly defined, the choice of the representative must not matter; the neighbours neigh(A) and neigh(B) of two different configurations A and B with equal shape must form the same set of shapes.

This is indeed the case: if configuration A and B have an equal shape, then there is a pairing between their components which can be used to “rename” components of A so the configuration is strictly equal to B and vice versa. If A+ is a descendant of A gained by applying an atomic step, then we can gain configuration B+ with shape equal to A+ by first renaming the components of B, and then executing the same atomic step. Even after renaming components, the connections, disconnections and $\gamma$ rotations of any and all modules can be executed without limits, and $\alpha$ and $\beta$ rotations are limited in the same manner even after renaming takes place.

To find a pairing between configurations A and B with the same shape, we can utilize the transformations T_a and T_b used to align their landmarks; these transformations can be found using an approach described here. First, pair up every component of A with its absolute position within the configuration. Then apply T_a and the inverse of T_b (which is invertible because it is a combination of an isometric scaling, rotation, translation, and a reflection) to these positions. The component of B with the same type in the resulting position is the one that the initial component should be paired with.

Modifying the reconfiguration plan

A RoFIBot requires well-defined instructions on what to do when reconfiguring, preferably in the form of steps - which joint to move by what angle, or which connectors to connect or disconnect. If we use the shape state space to find a reconfiguration plan, it might happen that the result will be a sequence of shapes one atomic step apart, but individual configurations representing these shapes will require a remapping of components in addition to the application of the steps. To avoid having to remap the components after every step, we can modify the shape reconfiguration plan into a more appropriate form, where even adjacent individual configurations will be one atomic step away in the sequence.

To get a configuration plan that does not remap components in between steps, the following approach can be used: Suppose we have a sequence C_1, C_2, …, C_n where only the shapes of the adjacent configurations are one atomic step apart, but not the configurations themselves. Then to create a sequence of configurations one atomic step apart configuration-wise, we generate neighbours of C_1, find the neighbour D_2 with the same shape as C_2, and use D_2 as the second configuration. Then we do the same for D_2, and use its neighbour D_3 with the same shape as C_3 as the third configuration, and so on, until we replace the last configuration C_n in the initial configuration plan and get a sequence of C_1, D_2, D_3, …, D_n. This new sequence surely moves by only one atomic step at a time, but at the same time, it can be used to reconfigure RoFIBots with respect to their shapes.