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.