Always choose second best: Tracking a moving target on a graph with a noisy binary sensor
Kevin Leahy, Mac Schwager · 2016
In this work, we consider the problem of using a noisy binary sensor to optimally track a target that moves as a Markov Chain in a finite discrete environment. Our approach focuses on one-step optimality because of the apparent infeasibility of computing an optimal policy via dynamic programming. We prove that, under mild assumptions, always searching in the second most likely location minimizes one-step variance while maximizing the belief about the target's location over one step. Simulation results demonstrate the performance of our strategy and suggest the policy performs well over arbitrary horizons.