We study the problem of devising a closed-loop strategy to control the position of a robot that is tracking a possibly moving target. The robot is capable of obtaining noisy measurements of the target's position. The key idea in active target tracking is to choose control laws that drive the robot to measurement locations that will reduce the uncertainty in the target's position. The challenge is that measurement uncertainty often is a function of the (unknown) relative positions of the target and the robot. Consequently, a closed-loop control policy is desired which can map the current estimate of the target's position to an optimal control law for the robot. Our main contribution is to devise a closed-loop control policy for target tracking that plans for a sequence of control actions, instead of acting greedily. We consider scenarios where the noise in measurement is a function of the state of the target. We seek to minimize the maximum uncertainty (trace of the posterior covariance matrix) over all possible measurements. We exploit the structural properties of a Kalman Filter to build a policy tree that is orders of magnitude smaller than naive enumeration while still preserving optimality guarantees. We show how to obtain even more computational savings by relaxing the optimality guarantees. The resulting algorithms are evaluated through simulations.
@cite_12: Consider a set of sensors estimating the state of a process in which only one of these sensors can operate at each time-step due to constraints on the overall system. The problem addressed here is to choose which sensor should operate at each time-step to minimize a weighted function of the error covariance of the state estimation at each time-step. This work investigates the development of tractable algorithms to solve for the optimal and suboptimal sensor schedule. First, a condition on the non-optimality of an initialization of the schedule is presented. Second, using this condition, both an optimal and a suboptimal algorithm are devised to prune the search tree of all possible sensor schedules. This pruning enables the solution of larger systems and longer time horizons than with enumeration alone. The suboptimal algorithm trades off the quality of the solution and the complexity of the problem through a tuning parameter. Third, a hierarchical algorithm is formulated to decrease the computation time of the suboptimal algorithm by using results from a low complexity solution to further prune the tree. Numerical simulations are performed to demonstrate the performance of the proposed algorithms.
@cite_12 presented an algorithm that computes the optimal scheduling of measurements for a linear dynamical system. Their formulation does not directly model a target tracking problem. Instead, the goal is to track a linear dynamical system using a set of sensors such that one sensor can be activated at any time instance. The posterior covariance in estimating a linear system in a Kalman filter depends on the prior covariance and sensor variance but not on the actual measurement values (unlike the case in non-linear systems). Thus, one can build a search tree enumerating all possible sensor selections and choosing the one that minimizes the final covariance. The main contribution of was to present a pruning technique to reduce the size of the tree while still preserving optimality.