Centralised and Distributed Shape Formation with a Linear-Strength Model

Abstract

This thesis is in the area of algorithmic robotic systems, where the main objective is to investigate the fundamental possibilities and limitations of different centralised and distributed algorithms related to shape formation, including the domain of small-scale robotics, such as programmable matter. It aims to combine current formalisms and develop a new theoretical model that is expected to promote the hardware and practical achievements while also enhancing the deployment and implementation of energy-efficient systems. It consists of three main parts. First, we introduced a new linear-strength model of a discrete system of entities residing on a two-dimensional square grid. Each entity is modelled as a node occupying a distinct cell, and the set of all n nodes forms initially a connected shape A on the grid. Entities are equipped with a linear-strength pushing mechanism that can push a whole line of entities in parallel in a single time-step on one position in a given (one of the four possible) direction of a grid. A target connected shape B is also provided and the goal is to transform A into B via a sequence of line moves. Existing models of individual movements – such as rotating or sliding a single node – can be shown to be special cases of the present model, therefore their (inefficient, quadratic time) universal transformations carry over. We present an efficient centralised algorithmic framework that can universally transform any pairs of shapes in sub-quadratic worst-case transformations. The second part focuses on designing centralised transformations aiming at minimising the total number of moves subject to the constraint of preserving connectivity of the shape throughout the transformation. That is, in each intermediate configuration we always guarantee that an associated graph induced by the occupied nodes is connected. We introduce very fast connectivity-preserving transformations for the case in which the associated graphs of A and B contain a Hamiltonian path. In particular, our transformation completes in a number of moves, which is asymptotically equal to the best known running time of connectivity-breaking transformations. Our most general result is then a connectivitypreserving universal transformation that can transform A into B (and B into A), through a sequence of sub-quadratic moves in a worst-case transformation. The last part establishes a corresponding distributed model where nodes are simple indistinguishable devices called agents, which act as finite-state automata. Each gent has constant memory and can observe the states of nearby agents in a Moore neighbourhood. Our main contribution is the first distributed connectivity-preserving transformation that exploits line moves within sub-quadratic moves, which is asymptotically equivalent to that of the best-known centralised transformations. The algorithm solves the line formation problem that allows agents to form a final straight line from any shape, whose associated graph contains a Hamiltonian path.