2017/05/10 by Sebastian Brandt, Brandt, Sebastian, Jara Uitto +3
Computer Science · Engineering · #Distributed #Distributed systems and fault tolerance #F.2.2 #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1705.03834
openalex publication_date 2017/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a small group of mobile agents whose goal is to locate a certain cell in a two-dimensional infinite grid. The agents operate in an asynchronous environment, where in each discrete time step, an arbitrary subset of the agents execute one atomic look-compute-move cycle. The protocol controlling each agent is determined by a (possibly distinct) finite automaton. The only means of communication is to sense the states of the agents sharing the same grid cell. Whenever an agent moves, the destination cell of the movement is chosen by the agent's automaton from the set of neighboring grid cells. We study the minimum number of agents required to locate the target cell within finite time and our main result states a tight lower bound for agents endowed with a global compass. Furthermore, we show that the lack of such a compass makes the problem strictly more difficult and present tight upper and lower bounds for this case.