Searching for multiple targets using Probabilistic Quadtrees

Abstract

We consider the problem of searching for an unknown number of static targets inside an assigned area. The search problem is tackled using Probabilisitic Quadtrees (PQ), a data structure we recently introduced. Probabilistic quadtrees allow for a variable resolution representation and naturally induce a search problem where the searcher needs to choose not only where to sense, but also the sensing resolution. Through a Bayesian approach accommodating faulty sensors returning both false positives and missed detections, a posterior distribution about the location of the targets is propagated during the search effort. In this paper we extend our previous findings by considering the problem of searching for an unknown number of targets. Moreover, we substitute our formerly used heuristic with an approach based on information gain and expected costs. Finally, we provide some convergence results showing that in the worst case our model provides the same results as uniform grids, thus guaranteeing that the representation we propose gracefully degrades towards a known model. Extensive simulation results substantiate the properties of the method we propose, and we also show that our variable resolution method outperforms traditional methods based on uniform resolution grids.