Rollout Algorithm for Target Search in a Wireless Sensor Network

A mobile, autonomous searcher is tasked with finding the source node of a broadcast message in a randomly deployed network of location-agnostic wireless sensor nodes. Messages are assumed to propagate by flooding, with random node-to-node delays. In networks of this type, the hop count of the broadcast message, given the distance from the source node, can be approximated by a simple parametric distribution. The mobile searcher can interrogate a nearby sensor node to obtain, with a given success probability, the hop count of the broadcast message. We model the search as an infinite-horizon, undiscounted cost, online POMDP and solve it approximately through policy rollout. The cost-to-go at the rollout horizon is approximated by a heuristic based on an optimal search plan in which path constraints and assumptions about future information gain are relaxed. This cost can be computed efficiently, which is essential for the application of Monte Carlo methods, such as rollout, to stochastic planning problems. Finally, we demonstrate that our rollout approach outperforms a popular method of target search based on a myopic, mutual information utility.