Walking Drosophila navigate complex plumes using stochastic decisions biased by the timing of odor encounters

How insects navigate complex odor plumes, where the location and timing of odor packets are uncertain, remains unclear. Here we imaged complex odor plumes simultaneously with freely-walking flies, quantifying how behavior is shaped by encounters with individual odor packets. We found that navigation was stochastic and did not rely on the continuous modulation of speed or orientation. Instead, flies turned stochastically with stereotyped saccades, whose direction was biased upwind by the timing of prior odor encounters, while the magnitude and rate of saccades remained constant. Further, flies used the timing of odor encounters to modulate the transition rates between walks and stops. In more regular environments, flies continuously modulate speed and orientation, even though encounters can still occur randomly due to animal motion. We find that in less predictable environments, where encounters are random in both space and time, walking flies navigate with random walks biased by encounter timing.