Navigating an Infinite Space with Unreliable Movements

Anders Martinsson, Jara Uitto

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


We consider a search problem on a 2-dimensional infinite grid with a single mobile agent. The goal of the agent is to find her way home, which is located in a grid cell chosen by an adversary. Initially, the agent is provided with an infinite sequence of instructions, that dictate the movements performed by the agent. Each instruction corresponds to a movement to an adjacent grid cell and the set of instructions can be a function of the initial locations of the agent and home. The challenge of our problem stems from faults in the movements made by the agent. In every step, with some constant probability 0

This paper provides two results on this problem. First, we show that for some values of p, there does not exist any set of instructions that guide the agent home in finite expected time. Second, we complement this impossibility result with an algorithm that, for sufficiently small values of p, yields a finite expected hitting time for home. In particular, we show that for any p <1, our approach gives a hitting rate that decays polynomially as a function of time. In that sense, our approach is far superior to a standard random walk in terms of hitting time. The main contribution and take-home message of this paper is to show that, for some value of 0.01139... <p <0.6554..., there exists a phase transition on the solvability of the problem.

Original languageEnglish
Title of host publicationProceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete AlgorithmsJanuary 2020
PublisherCurran Associates, Inc.
Number of pages10
ISBN (Print)9781713807384
Publication statusPublished - Jan 2020
MoE publication typeA4 Article in a conference publication
EventACM-SIAM Symposium on Discrete Algorithms - Salt Lake City, United States
Duration: 5 Jan 20208 Jan 2020
Conference number: 31


ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
Country/TerritoryUnited States
CitySalt Lake City


Dive into the research topics of 'Navigating an Infinite Space with Unreliable Movements'. Together they form a unique fingerprint.

Cite this