A Lower Bound on Observability for Target Tracking with Range Sensors and its Application to Sensor Assignment
This work addresses sensor assignment challenges in multi-target tracking for applications like surveillance or robotics, but it is incremental as it builds on existing observability measures and approximation methods.
The paper tackles sensor assignment problems for multi-target tracking by developing approximation algorithms to improve estimator observability, achieving a 1/3-approximation for a restricted version and a 1/2-approximation for a general version, with empirical validation through simulations.
We study two sensor assignment problems for multi-target tracking with the goal of improving the observability of the underlying estimator. In the restricted version of the problem, we focus on assigning unique pairs of sensors to each target. We present a 1/3-approximation algorithm for this problem. We use the inverse of the condition number as the value function. If the target's motion model is not known, the inverse cannot be computed exactly. Instead, we present a lower bound for range-only sensing. In the general version, the sensors must form teams to track individual targets. We do not force any specific constraints on the size of each team, instead assume that the value function is monotonically increasing and is submodular. A greedy algorithm that yields a 1/2-approximation. However, we show that the inverse of the condition number is neither monotone nor submodular. Instead, we present other measures that are monotone and submodular. In addition to theoretical results, we evaluate our results empirically through simulations.