Complete heterogeneous self-reconfiguration: Deadlock avoidance using hole-free assemblies

In this paper, we present a novel approach for heterogeneous self-reconfiguration of a modular robot comprised of heterogeneous cubic modules. We allow an arbitrary number of modules and module classes and show that the proposed self-reconfiguration algorithm can guarantee completion of heterogeneous self-reconfigurations by avoiding so-called hole obstructions. We introduce a hole-detection algorithm to avoid creating holes in connected sets of modules (furthermore called configuration) and an assignment resolution algorithm that prevents deadlocks. Using these algorithms, we show that this approach yields provably successful reconfiguration sequences from any heterogeneous initial configuration to any heterogeneous target configuration as long as the initial and the target configuration are hole and enclosure-free.