Abstract
Long-range olfactory search is an extremely difficult task in view of the sparsity of odor signals that are available to the searcher and the complex encoding of the information about the source location. Current algorithmic approaches typically require a continuous memory space, sometimes of large dimensionality, which may hamper their optimization and often obscure their interpretation. Here, we show how finite-state controllers with a small set of discrete memory states are expressive enough to display rich, time-extended behavioral modules that resemble the ones observed in living organisms. Finite-state controllers optimized for olfactory search have an immediate interpretation in terms of approximate clocks and coarse-grained spatial maps, suggesting connections with neural models of search behavior.