Dispersion of Mobile Robots Tolerating Faults

Abstract

The dispersion problem on graphs asks k ≤ n robots initially placed arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration with each robot on a distinct node. This problem is of interest due to its relationship to many fundamental robot coordination problems, such as exploration, scattering, load balancing, relocation of self-driven electric cars (robots) to recharge stations (nodes), etc. The objective of this problem is to minimize simultaneously (or provide trade-off between) two fundamental performance metrics: (i) time to achieve dispersion and (ii) memory needed at each robot. The literature solved this problem on arbitrary graphs considering fault-free robots.