Efficient multi-robot search for a moving target

This paper examines the problem of locating a mobile, non-adversarial target in an indoor environment using multiple robotic searchers. One way to formulate this problem is to assume a known environment and choose searcher paths most likely to intersect with the path taken by the target. We refer to this as the multi-robot efficient search path planning (MESPP) problem. Such path planning prob-lems are NP-hard, and optimal solutions typically scale exponen-tially in the number of searchers. We present an approximation al-gorithm that utilizes finite-horizon planning and implicit coordina-tion to achieve linear scalability in the number of searchers. We prove that solving the MESPP problem requires maximizing a non-decreasing, submodular objective function, which leads to theoreti-cal bounds on the performance of our approximation algorithm. We extend our analysis by considering the scenario where searchers are given noisy non-line-of-sight ranging measurements to the target. For this scenario, we derive and integrate online Bayesian measurement updating into our framework. We demonstrate the performance of our framework in two large-scale simulated environments, and we further validate our results using data from a novel ultra-wideband ranging sensor. Finally, we provide an analysis that demonstrates the rela