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.
Related Publications
- [1] Pickem, D., Egerstedt, M. & Shamma, J. S., “A game-theoretic formulation of the homogeneous self- reconfiguration problem”, IEEE Conference on Decision and Control (CDC), 2015, pp. 2829-2834 (Student Best Paper Finalist)
