  In many practical scenarios, a flying insect must search for the source of an
emitted cue which is advected by the atmospheric wind. On the macroscopic
scales of interest, turbulence tends to mix the cue into patches of relatively
high concentration over a background of very low concentration, so that the
insect will only detect the cue intermittently and cannot rely on chemotactic
strategies which simply climb the concentration gradient. In this work, we cast
this search problem in the language of a partially observable Markov decision
process (POMDP) and use the Perseus algorithm to compute strategies that are
near-optimal with respect to the arrival time. We test the computed strategies
on a large two-dimensional grid, present the resulting trajectories and arrival
time statistics, and compare these to the corresponding results for several
heuristic strategies, including (space-aware) infotaxis, Thompson sampling, and
QMDP. We find that the near-optimal policy found by our implementation of
Perseus outperforms all heuristics we test by several measures. We use the
near-optimal policy to study how the search difficulty depends on the starting
location. We discuss additionally the choice of initial belief and the
robustness of the policies to changes in the environment. Finally, we present a
detailed and pedagogical discussion about the implementation of the Perseus
algorithm, including the benefits -- and pitfalls -- of employing a reward
shaping function.
