  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 \leq p \leq 1$,
the agent performs a random movement instead of following the current
instruction.
  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\dots < p < 0.6554\ldots$,
there exists a phase transition on the solvability of the problem.
