Using hexagonal metamorphic robots to form temporary bridges

Abstract

This paper presents algorithms to plan the concurrent and collision-free movement of n hexagonal metamorphic robots (modules) over a contiguous surface in a hexagonal grid. The problem is complicated by the fact that the surface may include "non-concurrently traversable" segments, where narrow passages between surface cells may result in module collision, regardless of the space separating moving modules. We present a new algorithm to identify unoccupied cells that, when filled with modules, form bridges to span all non-concurrently traversable segments of the surface. Our bridging algorithms have the added benefit of reducing the overall traversal time for a given surface. Additionally, we show that four modules are sufficient to bridge any contiguous non-concurrently traversable segment, allowing concurrent module movement with minimal inter-module spacing. Finally, we present the results of simulating our algorithms using a discrete event simulator.