Localization

Determining module locations from noisy observations

 

One of the first tasks for a modular robot is to understand where its modules are located relative of one to another. This knowledge is very useful: For example, motion planning and control will often shift many modules from one location to another, and knowing the module locations helps robot properly allocate the resources. The knowledge of module locations will also be useful to identify a human user.

In order to determine their locations, the modules need to rely on noisy observations of their immediate neighbors. These observations are obtained from sensors onboard the modules, such as short-range IR sensors. Unlike many other systems, a modular robot may not have access to long distance measurements, such as wireless radio or GPS. Furthermore, the robot's modules will often form irregular, non-lattice structures. Therefore, the robot needs to employ sophisticated probabilistic techniques to estimate the location of each its module from noisy data.

Our contribution is an algorithm that lets the modules estimate their locations in a fully distributed manner. The algorithm has a number of attractive properties: It can handle errors that arise from uncertain observations. As we scale the ensemble to increasingly finer resolutions, the accuracy of the localization remains roughly constant. Furthermore, the algorithm is sufficiently simple that it permits a distributed implementation. Therefore, the locations are estimated directly by the modules themselves, without relying on an external, centralized processing unit.

On the technical side, our algorithm leverages two insights. One key idea is to hierarchically decompose the ensemble into smaller parts. The parts are localized first, and the partial solutions are then merged to obtain an estimate for the entire ensemble. Importantly, the ensemble is split in such a way that the partial solutions do not accumulate too much error. Thus, when the partial solutions are merged, the algorithm only needs to exercise a minimal effort to compute an accurate overall solution.

The second key idea employed in our work is to limit the amount of communication sent between the modules. Much like in a flock of birds, each module needs to communicate information about itself to others in the ensemble, but should avoid communicating with everybody. In our case, many operations in the algorithm are implemented by communicating aggregate statistics about progressively larger parts of the ensemble. In this manner, the communication complexity of our algorithm scales logarithmically with the size of the ensemble.

Publications and Documents