Collective search-and-capture under competing assignment policies

Abstract

We study a minimal lattice model of active search-and-capture in which persistent random walkers locate and irreversibly capture immobile targets through a finite-range, mutually exclusive assignment rule. We measure the collective completion time $T_c$ as a function of the walkers' reorientation rate $\alpha$ and the search radius $R$. The dependence $T_c(\alpha)$ is non-monotonic, with a minimum at intermediate persistence whose depth decreases as $R$ grows. Capture kinetics show that $T_c$ is not a typical capture time but is governed by the extreme, late-time tail of the capture process, while the bulk of targets are captured much earlier; this tail is controlled mainly by the free-exploration phase rather than by the final directed approach. We then compare the baseline single-round assignment rule with cascading reassignment and with maximum-cardinality matching on a candidate graph. The two greedy policies (single-round and cascading) agree at very small $R$, whereas maximum-cardinality matching already produces a strong speedup at moderate $R$: improved matching reduces $T_c$ by factors of several at large $R$, and by more than an order of magnitude at moderate $R$. Thus, in this collective, depletion-coupled search problem, the assignment policy can control the capture time more strongly than the walkers' persistence.