Optimal Decision-Making in an Opportunistic Sensing Problem

In this paper, we consider the problem of sensing a finite set of (moving) objects over a finite planning horizon using a set of sensors in prefixed locations that vary with respect to time over a discretized space. Control in this situation is limited and the problem considered is one of opportunistic sensing. We formulate an integer program that maximizes the quality of sensor return given either deterministic or probabilistic (i.e., forecasted) object routes. We examine the computational complexity of the problem and show it is non-deterministic polynomial-hard. We theoretically and numerically illustrate subclasses of the problem that are computationally simpler, ultimately deriving a heuristic that is strongly polynomial. Real-world and constructed data sets are used in our analysis.