Game-theoretic Self-Reconfiguration

This project aims to  formulate the homogeneous two- and three-dimensional self-reconfiguration problem over discrete grids as a constrained potential game. We develop a game-theoretic learning algorithm based on the Metropolis-Hastings algorithm that solves the self-reconfiguration problem in a globally optimal fashion. Both a centralized and a fully decentralized algorithm are presented and we show that the only stochastically stable state is the potential function maximizer, i.e. the desired target configuration. These algorithms compute transition probabilities in such a way that even though each agent acts in a self-interested way, the overall collective goal of self-reconfiguration is achieved. Simulation results confirm the feasibility of our approach and show convergence to desired target configurations.

In general, self-reconfigurable systems are comprised of individual agents which are able to connect to and disconnect from one another to form larger functional structures. A system with agents or modules that have distinct capabilities, shapes, or sizes, is called a heterogeneous system. Alternatively, a system with identical and interchangeable modules is referred to as a homogeneous system. In this project we will present algorithms that reconfigure homogeneous systems and treat self-reconfiguration as a two- and three-dimensional coverage problem. However, minor modifications to the core algorithm could extend its applicability to heterogeneous systems as well.

Self-reconfiguration in this work tries to solve the following problem. Given an initial geometric arrangement of cubes (called a configuration) and a desired target configuration, the solution to the self-reconfiguration problem is a sequence of primitive cube motions that reshapes/reconfigures the initial into the target configuration. A full sequence from an initial to a target configuration is shown below together with convergence times for configurations of various sizes.

Our approach to homogeneous self-reconfiguration is fully decentralized such that no central decision maker is required. In such a decentralized setup, even though each agent acts as a purely self-interested individual decision maker with local information only, our method guarantees convergence to the global target configuration. Decision making requires no (in the two-dimensional case) or limited communication (in the three-dimensional case). Each agent computes transition probabilities for all actions possible at the current time step (according to a fixed motion model). An agent then selects an action based on these probabilities and accepts/rejects it according to an acceptance probability. The key to guarantee global convergence to the target configuration lies in these acceptance probabilities that are computed according to the Metropolis-Hastings algorithm and ensure that the only stochastically stable state is the target configuration.

An example of a full reconfiguration sequence from a random 2D initial configuration to a random 2D target configuration.
Convergence times for four scenarios of varying configuration sizes. The scenarios differed in the dimensionality of the initial and the target configuration (for example a 2D initial configuration to a 2D target configuration).
Example of a reconfiguration from a random initial configuration to a rectangular cuboid shape.

Related Publications