Dispersion of Mobile Robots on a Graph

Notice: this seminar was originally scheduled for Wednesday, December 5, but is rescheduled to Thursday, December 6 due to the closure of UH.

When: Thursday, December 6
Where: PGH 550
Time: 11:00 AM

Speaker: Dr. William Moses Jr., Technion – Israel Institute of Technology

Host: Prof. Gopal Pandurangan

Mobile robots coordinating with one another to solve some global problem is an area of interest in recent times. In this talk, we introduce a new problem into the domain of mobile robots, which we call dispersion of mobile robots on a graph, and study it in a synchronous system. The problem asks that n robots initially arbitrarily placed in an n node graph coordinate and reach a configuration, as quickly as possible, where there is exactly one robot per node. This problem is motivated by situations where multiple robots may need to access a shared pool of resources but the cost of sharing an individual resource is much more than simply finding another available resource. Furthermore, this problem has relevance to the well-studied problems of scattering on a graph, multi-robot exploration of a graph, and load balancing on a graph.

In the first part of this talk, we study dispersion on static graphs where robots use message passing to coordinate with one another. We look at the trade-offs between memory required by the robots and the time taken to achieve dispersion. Specifically, we show how even a few extra bits of memory is sufficient in some cases to allow rapid speedup in achieving dispersion.

In the second part of this talk, we study dispersion on dynamic rings where robots use a look-compute-move paradigm to coordinate with one another. Here, the types of dynamism we consider are (i) vertex permutation and (ii) 1-interval connectivity. We study the ability of robots to achieve dispersion when robots are chiral/achiral and have full visibility/no visibility.

The first part of the talk is based on joint work with John Augustine, an initial version of which was published at ICDCN 2018 (19th International Conference on Distributed Computing and Networking). The second part of the talk is based on joint work with Ankush Agarwalla, John Augustine, Madhav Sankar K., and Arvind Krishna Sridhar which was also published at ICDCN 2018.

Bio:

William K. Moses Jr. is currently a postdoc at the Technion in Haifa, Israel. He is interested in research related to algorithms and especially distributed algorithms, with his current focus on the intersection of distributed algorithms and game theory. He has in the past worked on problems related to SINR networks and mobile robots.