Gathering of Asynchronous Mobile Robots in a Tree

Abstract

This paper addresses a robot-based distributed model which makes use of a group of small, inexpensive, identical, oblivious mobile robots placed in nodes of an anonymous and unoriented tree. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbour (Move). Cycles are performed asynchronously for each robot. In this paper, we present a distributed algorithm by which κ robots deterministically gather at a single uniquely marked node in a tree with η nodes. The robots have limited visibility and have no common agreement in coordinate axes.