Decentralized adaptive search using the noisy 20 questions framework in time-varying networks

•Decentralized algorithm for stochastic search based on adaptive querying and local information sharing in time-varying networks.•Stability and asymptotic consistency proof of the proposed algorithm using a novel technique based on martingale techniques combined with spectral graph theory.•Asymptotic convergence guaranteed despite the asynchronous nature of information collection and information sharing across the network.•Large performance gains over case of no information sharing; performance close to synchronous and centralized counterparts of algorithms.

This paper considers the problem of adaptively searching for an unknown target using multiple agents connected through a time-varying network topology. Agents are equipped with sensors capable of fast information processing, and we propose a decentralized collaborative algorithm for controlling their search given noisy observations. Specifically, we propose decentralized extensions of the adaptive query-based search strategy that combines elements from the 20 questions approach and social learning. Under standard assumptions on the time-varying network dynamics, we prove convergence to correct consensus on the value of the parameter as the number of iterations go to infinity. The convergence analysis takes a novel approach using martingale-based techniques combined with spectral graph theory. Our results establish that stability and consistency can be maintained even with one-way updating and randomized pairwise averaging, thus providing a scalable low complexity method with performance guarantees. We illustrate the effectiveness of our algorithm for random network topologies.