M.Sc Student | Lihi Cohen |
---|---|

Subject | Exploring an Infinite Space with Finite Memory Scouts |

Department | Department of Industrial Engineering and Management |

Supervisors | Professor Emek Yuval |

Professor Louidor Oren | |

Full Thesis text |

Consider a small
number of scouts exploring the *d-*dimensional infinite grid *Z ^{2}*
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 *Z ^{2}*. The first proposition shows
that if this is the case the two scouts must meet infinitely often with
probability

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.

.