What: In this tutorial, we provide an extensive survey of the work on dispersion of mobile robots, introduced by Augustine and Moses Jr. [ICDCN 2018]. The problem of dispersion of k robots, initially arbitrarily placed on the nodes of an n node graph, requires the robots to autonomously move around to reach a configuration such that there are at most $\lceil k/n \rceil$ robots on each node. Typically, the metrics used to gauge solutions to this problem are the time until dispersion is achieved and the memory requirement per robot. Although this problem was introduced recently, much work has been done on it in the setting it was originally introduced in, as well as extensions to new settings. We will provide an overview of the techniques and results until now as well as possible future work. Our presentation will be in two parts. In the first part, we will present the foundations of the dispersion problem and some fundamental results. In the second part, we discuss various extensions to different settings and recent developments.
When: Friday, July 29th, 2022. From 9:00 am - 12 pm CEST (GMT +2) with a 30 minute coffee break in between.
Where: This tutorial will be held as part of PODC 2022.
Model of computation and formulation of the dispersion problem.
Fundamental works in the synchronous setting.
State of the art in the asynchronous setting.
Variations in communication between robots.
Handling faulty robots.
Dynamism of the underlying graph.
Use of randomness.