Master project : Toward Emancipation of Furniture. A Kinematics-Dependent Reconfiguration Algorithm for Chain-Type Modular Robots

Modular robots are complex systems composed of a set of simple robotic units.
These units can rearrange to change the shape of the whole structure. This ability enables the reconfigurable robots to be extremely adaptive to changes in the environment and task. The most common applications of these systems are in space exploration where their versatility is a big advantage.

Our project is very distant from this field. The aim of the project is to use modular robot units to build furniture that could change shape and locomote in various environments.

This project tackles the problem of reconfiguration of a set of modular units: basically, what are the necessary connections and disconnections to reconfigure one shape to another ? This problem is NP-Hard and can be viewed as a graph theory problem, but in this case, we do not take into account the kinematical restrictions of the modules. Thus, the sequences found are not necessarily feasible on the real system. We introduce kinematical information in our model in order to avoid internal collisions and disconnection of the structure.

Tree representations

The main goal of our project is to build the tree of all possible connections and disconnections (ie : each node of the tree is obtained from its parent by making one connection or one disconnection). But in order to connect two modules one have to first move them in contact to one another, which is not always possible or sometimes involves making very complex movements.

To be able to compute only the valid connections we built the tree of all possible servo movements, detecting and avoiding the internal collisions of the structure.
The picture on the left represents an example of this tree. The tree on the left is the Servo Movement Tree and the one on the right is a part of the Moves Tree which represents every possible connections and disconnections.

The problem here is that the number of nodes in this tree (thus the size of the search space) grows exponentially with the number of modules. Its size is proven to be

. Thus, we need ways to guide the searching process in this huge space.

Heuristics

The first heuristic that we designed was based on the following observation: the probability to be able to make new connections is inversely proportional to the mean distance between the modules. For each servo, we have the choice to place it in three positions: -90°, 0° or +90°. Our heuristics automatically selects the position for which the moving modules get the nearest to the rest of the structure. This enables us to decrease the complexity by 2ⁿ.

We further simplified the searching process by removing the duplicates of the search space. This is done by storing a unique key for each successful sequence of servo movements in a hash table. Our algorithm verifies that a node is not already present in this hash table before adding it to the tree.

We get a final complexity of O(2ⁿ), which is still exponential but of a much less order of magnitude than before.
To give an example, one of our test samples would take about 22 hours to complete by explicitly searching the tree while it would take about 5 seconds by using our complexity reduction techniques.

Files

Master thesis (PDF)

Video : a snake to a wheel (AVI)

Video : a H shape to a cross (AVI)

Engineer Diploma Project : IMOROD : Interface for MOdular RObots Design. Conception and Development of a 3D Robotic Interface for the Roombots project.

The Roombots project is meant to be applied in the new Learning Center of the EPFL. Ideally a room would be equipped with Roombots and any user could interact with them, to make them change shape or position.

The precedents project (Master project) aims at automating the reconfiguration process given an initial and a final configuration. This reconfiguration process is transparent to the user.

But the user still has to describe at least the final configuration (the initial one can be considered to be the current one).

This engineer project aims at conceive and develop a simple user interface enabling any user to easily design complex robotic structure by assembling virtual 3D modules.

The main functionalities of this interface would be :

Building, visualizing, saving robot structures
Building full rooms (by positioning previously designed furniture in a virtual room)
Visualizing reconfiguration sequences (importing the sequences and watching the virtual robot change shape)

Furthermore, the final interface should be :

Easy to use for any user
Portable, particularly to UNIX systems
Inter-operable and compatible with Webots and the reconfiguration planning software
Easily extensible : this is even more important that the project is not fully developed yet and might be taken over by some other developer

The interface that we designed is very simple and intuitive, usable almost only with the mouse and contains a few common controls to help the user. We named it IMOROD for Interface for MOdular RObots Design. We used C++ as coding language, OpenGL as graphics library and GLOW as widgets library and C++ wrapper for GLUT and OpenGL.

We wrote a user interface which is a easy to understand, well illustrated, step by step tutorial to master all the functionalities of IMOROD.

We also wrote a developer interface containing all the guidelines for further development of the solution as well as a simplified class reference.

These documents are available below as well as some screenshots of the application.

Screenshots

Files

Project specifications (PDF)

User guide (PDF)

Developper guide (PDF)

IMOROD win32 binary files (ZIP)

IMOROD source code, including Microsoft Visual Studio preconfigured solution (ZIP)