M.Sc Thesis
M.Sc Student Cohen Lihi Exploring an Infinite Space with Finite Memory Scouts Department of Industrial Engineering and Management Professor Yuval Emek Professor Oren Louidor

Abstract

Consider a small number of scouts exploring the d-dimensional infinite grid Z2 with the aim of hitting a hidden target point. Each scout is controlled by a probabilistic finite automaton with finite state space that determines its movement (to a neighboring grid point) based on its current state.

The scouts, that operate under a fully synchronous schedule, communicate with each other (in a way that affects their respective states) when they share the same grid point and operate independently otherwise. Our main research question is: How many scouts are required to guarantee that the target admits a finite mean hitting time?

Recently, it was shown that d 1 scouts is an upper bound on the answer to that question for any dimension equal or larger than 1.  The primary technical contribution in this work is to show that d is also a tight bound for d=2. It turns out that the line of arguments leading to this proof also includes, in passing, a proof for the secondary result of this thesis: 1 scout cannot guarantee each grid point admits a finite mean hitting time for d=1.

We prove the tight bound in a top-down fashion. The argumentation relies on three non-trivial propositions all proven by first assuming towards a contradiction that two scouts are enough to guarantee that each grid point admits a finite mean hitting time on Z2.  The first proposition shows that if this is the case the two scouts must meet infinitely often with probability 1 and the distribution of time between successive meetings must have a stretched-exponentially decaying upper tail. The second proposition, which strongly relies on the first one, focuses on the meetings between the two scouts. Its proof shows that if each grid point admits a finite mean hitting time, after a random finite time the scouts meetings will occur only inside a ball of finite deterministic radius around some random grid point. Finally, the third proposition shows that between successive meetings each scout must be in a finite deterministic subset of the whole grid.

The combination of the last two propositions establishes the tightness of the upper bound d for d=2 since it leads to the conclusion that there must exists some grid point that will not be reached by either one of the scouts with positive probability. And that, by the tail formula for expectation, immediately shows the mean hitting time of this grid point in infinite.

.