  We explore minimal navigation strategies for active particles in complex,
dynamical, external fields, introducing a class of autonomous, self-propelled
particles which we call Markovian robots (MR). These machines are equipped with
a navigation control system (NCS) that triggers random changes in the direction
of self-propulsion of the robots. The internal state of the NCS is described by
a Boolean variable that adopts two values. The temporal dynamics of this
Boolean variable is dictated by a closed Markov chain -- ensuring the absence
of fixed points in the dynamics -- with transition rates that may depend
exclusively on the instantaneous, local value of the external field.
Importantly, the NCS does not store past measurements of this value in
continuous, internal variables. We show that, despite the strong constraints,
it is possible to conceive closed Markov chain motifs that lead to nontrivial
motility behaviors of the MR in one, two and three dimensions. By analytically
reducing the complexity of the NCS dynamics, we obtain an effective description
of the long-time motility behavior of the MR that allows us to identify the
minimum requirements in the design of NCS motifs and transition rates to
perform complex navigation tasks such as adaptive gradient following, detection
of minima or maxima, or selection of a desired value in a dynamical, external
field. We put these ideas in practice by assembling a robot that operates by
the proposed minimalistic NCS to evaluate the robustness of MR, providing a
proof-of-concept that is possible to navigate through complex information
landscapes with such a simple NCS whose internal state can be stored in one
bit. These ideas may prove useful for the engineering of miniaturized robots.
