Efficient search by optimized intermittentrandom walks

摘要

We study the kinetics for the search of an immobile target by randomly movingsearchers that detect it only upon encounter. The searchers perform intermittentrandom walks on a one-dimensional lattice. Each searcher can step on a nearestneighbor site with probability αor go off lattice with probability 1 — αto movein a random direction until it lands back on the lattice at a fixed distance L awayfrom the departure point. Considering αandLas optimization parameters,we seek to enhance the chances of successful detection by minimizing theprobability P_Nthat the target remains undetected up to the maximal searchtime N. We show that even in this simple model, a number of very efficientsearch strategies can lead to a decrease of P_Nby orders of magnitude uponappropriate choices of a and L. We demonstrate that, in general, such optimalintermittent strategies are much more efficient than Brownian searches andare as efficient as search algorithms based on random walks with heavy-tailedCauchy jump-length distributions. In addition, such intermittent strategiesappear to be more advantageous than Levy-based ones in that they lead to morethorough exploration of visited regions in space and thus lend themselves toparallelization of the search processes.