Modular robots are usually composed of multiple blocks with uniform docking interfaces that can be transformed into different configurations. It is a significant challenge to recognize modular robot configurations composed of hundreds of modules. Given a new configuration, it is important to match it to an existing configuration and, if true, map each module to the module in this matching configuration when applying many modular robot control schemes. An efficient algorithm is presented to address this matching and mapping problem by making use of distributed information from each module and new structure to design the configuration library. The cluster is discovered and the root module is determined first. Then the matching and mapping problem is solved simultaneously in polynomial time.

#### Modular Robots Configuration Library

The library is a collection of modular robot configurations and the representation of each configuration contains:

- Rooted graph with root of its center;
- Topology connection between modules;
- The total number of modules of connected to each module via every connector.

An example is shown in the following figure. The left is a SMORES configuration constructed with three modules and the right is its graph representation with center module 2.

#### Recognition Algorithm

The algorithm contains three parts: configuration discovery, root module search and matching and mapping. When a modular robot configuration is constructed, a fully autonomous modular robotic system has to be able to figure out the configuration topologyby itself, then the graph representation can be discovered to represent its current configuration. This discovery process is affected by the hardware design and we present an algorithm in linear time for SMORES modular robotic system. Then the root module can be determined in linear time by dynamic programming. In the end, matching and mapping algorithm is able to check if this configuration is matched to any existing configuration in the library and, if so, compute all possible mappings in quadratic time.

For example, thirteen modules construct a walker configuration shown in the left and the right is a configuration in the library. Their graph representations are also shown accordingly. The algorithm can return the result that the new configuration can be matched to this walker configuration in the library and there are 8 different mappings in total, such as {10→5, 7→4, 3→1, 9→7, 2→6, 1→0, 8→9, 4→8, 0→2, 5→11, 12→10, 13→13, 6→12, 11→3}.

- C. Liu and M. Yim, “Configuration recognition with distributed information for modular robots,” in Ifrr international symposium on robotics research, 2017.

[Bibtex]
```
@inproceedings{CL:MY:17,
title = {Configuration Recognition with Distributed Information for Modular Robots},
author = {Liu, Chao and Yim, Mark},
booktitle={IFRR International Symposium on Robotics Research},
year={2017}
}
```