Solving the ANTS Problem with Asynchronous Finite State Machines

摘要

Consider the Ants Nearby Treasure Search (ANTS) problem introduced by Feinerman, Korman, Lotker, and Sereni (PODC 2012), where n mobile agents, initially placed in a single cell of an infinite grid, collaboratively search for an adversarially hidden treasure. In this paper, the model of Feinerman et al. is adapted such that each agent is controlled by an asynchronous (randomized) finite state machine: they possess a constant-size memory and can locally communicate with each other through constant-size messages. Despite the restriction to constantsize memory, we show that their collaborative performance remains the same by presenting a distributed algorithm that matches a lower bound established by Feinerman et al. on the run-time of any ANTS algorithm.