Reconfiguration

No man is an island; but a robot could become one.

While looking for fully automated robot servants to fulfill our every wish, we put faith in modular robots. Unlike their integrated counterparts, these robots do not have one specified task to acomplish as quickly and optimally as possible, but rather focus on being able to deliver reasonably good results on many different fronts. However, doing the laundry and pushing the swingset are two very different tasks, and our single lonely robot might not be able to do both. But instead of buying another one of these fairly expensive toys, we would like our modular machine to reassemble, and complete any job we throw its way. This is where the problem of reconfiguration comes into play.

Defining the problem

Configuration

A configuration of a robot is a formal specification containing all relevant information about the given robot. That includes module specification (ID, type, components and joints between them, joint parameters) and how are individual modules connected to each other (which RoFIComs are connected using which orientations). A valid configuration enables us to construct the robot without modules colliding, or joints having impossible parameters. We also require a RoFIBot to be connected at all times: every specified module must be connected to all others either directly or indirectly.

Depending on the use case, however, the actual type of configuration might differ depending on what we want it to specify; sometimes we can omit information irrelevant to our problem, or add new information that will help us optimize the solution. For example, if we limit ourselves to only using universal modules and rotations of 90°, we can use the grid system of RoFIBots, and design a voxel-like configuration, which specifies the placement of the bodies of the modules in a 3D grid.

Atomic step

For a RoFIBot, an atomic step can be either changing the parameters of a joint (usually meaning rotating part of a module by a given angle), connecting two adjacent RoFIComs, or disconnecting already connected RoFIComs. We can “execute” or “apply” this step on/to some configuration by changing the configuration, for example rotating a rotational joint by changing its parameters. A step applied to a configuration is valid if the resulting configuration is valid.

The problem of reconfiguration

The problem of reconfiguration can be described as such: given two valid configurations “Init” and “Goal”, find a sequence of valid steps to apply to “Init” in order to gain “Goal” (if such a sequence exists). This sequence is called a reconfiguration plan. This means that for a reconfiguration path to exist, it is necessary for the configurations to have the same amount and types of modules, because a step does not add any new modules, nor can it remove any from the configuration.

Configuration state space

We can think of all possible configurations of a given set of modules as “states”, and atomic steps as transitions between them. Then the problem becomes finding a sequence of transitions to get from the “Init” state to the “Goal” state, given a state space formed by the set of modules in the “Init” configuration. Alternatively, it can be thought of as finding a path in a graph, where states are vertices, and transitions between states are edges.

We would like for the reconfiguration plan to consist of a finite number of discrete, executable, steps. We can achieve this by discretizing the allowed values of joint parameters in a RoFIBot, which might otherwise be indescrete floating point values (e.g. angles expressed in radians). An example could be using the previously mentioned 90° rotations.

Why do we need algorithms for reconfiguration?

For the same reason why we want modular robots - versatility. Finding a reconfiguration plan manually can be very time consuming, or even infeasible to do in a timely fashion. Even with only a small amount of modules, each with a few degrees of freedom, there are millions of relevant possible configurations.

Having an algorithm for finding a reconfiguration plan, we only need to supply it with the “Goal” configuration that it requires to complete the problem we are currently facing (the “Init” configuration being the current state of the robot). For example, the problem could be crossing a gap - we would like the robot to reconfigure into a “snake”, so it can use its body as a bridge. Afterwards, we want it to reconfigure into a “spider” to move quickly over difficult terrain, so we just tell it to reconfigure.

Going further, we would like the robot to be able to automatically recognize the configuration it needs to be in to complete a given task. This might be useful for when we ourselves cannot access the robot, or have limited information about its surroundings; we just let the robot itself decide what to reconfigure into, and worry only about how to specify our command.

The challenges of RoFI reconfiguration

The problem of reconfiguration is not easy to solve (it has been proven to be NP-complete), especially because of the size of the state space. Exploring the whole state space is therefore usually not a viable approach, both for time and memory related reasons.

Therefore, although we have classic path searching graph algorithms such as BFS or DFS at our disposal, we need to consider how to exploit the complexity of the configuration to our advantage. This opens up many doors to explore, such as:

• using various representations of configurations,
• reducing the size of the state space,
• applying complex steps,
• analyzing the geometric properties of the configuration,
• using heuristics to guide the path search

Constraints

Before deciding on how to tackle the problem, it might be useful to consider the purpose of the solution and constraints of the problem:

• Do we need the modules to be in a certain place of the robot, or does only the shape of the “Goal” configuration matter?
• Is the robot rigidly affixed to the surface by some of its parts?
• Are there obstacles around the robot?
• Do we care about finding the optimal (shortest) plan, or will any valid plan suffice?
• What is the required success rate of finding a plan if it exists?
• Do we need to always find the same plan, or can we use a nondeterministic approach? The answers to these questions might influence the optimal solution to use. Some algorithms are quick but unreliable, others might be optimal and complete, but slower, while some are only usable in certain situations.

Simple state space exploration

The most straightforward way to solve this problem is to explore the state space of configurations using a simple BFS or DFS algorithm. This approach is optimal and complete, meaning that if there are any reconfiguration plans for the “Init” and “Goal” configurations, we are guaranteed to find the shortest possible one. Unfortunately, because of the sheer number of all possible configurations, this has proven to be computationally infeasible for random configurations containing more than 2 or 3 universal modules. Therefore, we will need to either use a different approach, such as a guided search, or reduce the state space of the configurations.

State space reduction

Under certain constraints, we might be able to significantly reduce the size of the state space by using equivalence classes. This can be done when we do not need the resulting configuration of the reconfiguration plan to match the “Goal” exactly, but we only require it to have some attribute. For example to have a certain shape or topology, such as a “snake” or a “four legged spider”. In such a case, we do not care whether the “head” module of the snake has ID 1 or 2, or if the snake is “bent” - it would still be a robot snake with the same abilities.

By grouping configurations with the required attributes into equivalence classes, and defining appropriate configurations and appropriate steps between them, we are able to greatly reduce the size of the state space. Then we are not looking for one specific configuration, but any configuration in the same equivalence class as the “Goal” configuration. This can lead to shorter length of reconfiguration plans we create, because it is possible some configurations in the equivalence class we seek will be “closer” to our “Init” configuration in the state space.

For RoFIBots, we introduce three possible equivalence classes so far which we deem useful: Configurations, Shapes, and Topologies. This new, smaller, state space can then be explored much more quickly, and allows us to apply search algorithms with increased efficiency.

Advanced algorithms for state space exploration

To further reduce the amount of configurations we need to explore in order to find a reconfiguration plan, we can explore the state space more methodically. Some configurations are “obviously” further from the “Goal” than others. Additionally, if there is at least one valid plan, there are going to be many more, so we do not neccessarily need to explore every configuration.

A*

Classic algorithm for a guided search in a graph is the A* algorithm. Besides being given the “Init” and “Goal” configurations, it also requires a heuristic function. Given some configuration, this function estimates the number of steps we need to apply to this configuration before reaching the “Goal” configuration. We can use this estimation to make preferences when choosing the next state to explore - we simply choose the configuration that seems to be the closest to the “Goal” configuration.

If the heuristic function also never overestimates the number of steps (such a heuristic is called admissible), then this algorithm also finds the optimal (shortest) path. However, it might be a valid approach to use a non-admissible, but more effective, heuristic. In some cases, when we do not need to conserve energy or time for reconfiguration, we would probably prefer finding a path of length 40 in a few seconds, rather than one with a length of 30 in a matter of minutes.

Some possible heuristics for RoFIBots include comparing the difference between joint parameters, positions in space, number of modules of certain shapes, or distance of positions occupied by the robot. Using this algorithm has proven to be very viable, and can cut down time of finding a reconfiguration plan from minutes to mere seconds even for configurations of several modules.

RRT

Another algorithm, which is frequently used in motion planning, is called RRT. This algorithm tries to randomly take samples from the unexplored part of the state space, and connects them by a shortest path to already explored states. Using this approach, it grows a tree whose branches ideally cover the whole state space equally (meaning that every unexplored region of the state space is roughly equal in size). Since there are going to be multiple paths from one state to another, we do not need to explore every single configuration. RRT tries to skip exploring states which are similar to already explored states, and therefore probably not required to find a working path.

Adding a heuristic on top of this enables us first explore regions with higher probability of containing the goal state, reducing the total amount of states we explore on average. However, it is an algorithm based on randomness, and therefore does not guarantee either optimality or, depending on the implementation, even completeness, and the effectivity might differ drastically between runs even for the same start and goal configurations.

We have attempted to use this algorithm with mixed results; sometimes, RRT finds a path very quickly, other times it does not find any at all. The reason for this might be that RRT is better used for higher level motion planning, rather than reconfiguration, or we have implemented it incorrectly.