2016/08/26 by Vasileios Tzoumas, Tzoumas, Vasileios, Ali Jadbabaie +3 · 1 citation
Computer Science · Engineering · #Distributed Sensor Networks and Detection Algorithms #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Robotics (cs.RO) #Stability and Control of Uncertain Systems #Systems and Control (eess.SY) #Target Tracking and Data Fusion in Sensor Networks #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1608.07533
openalex publication_date 2016/08/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we focus on batch state estimation for linear systems. This\nproblem is important in applications such as environmental field estimation,\nrobotic navigation, and target tracking. Its difficulty lies on that limited\noperational resources among the sensors, e.g., shared communication bandwidth\nor battery power, constrain the number of sensors that can be active at each\nmeasurement step. As a result, sensor scheduling algorithms must be employed.\nNotwithstanding, current sensor scheduling algorithms for batch state\nestimation scale poorly with the system size and the time horizon. In addition,\ncurrent sensor scheduling algorithms for Kalman filtering, although they scale\nbetter, provide no performance guarantees or approximation bounds for the\nminimization of the batch state estimation error. In this paper, one of our\nmain contributions is to provide an algorithm that enjoys both the estimation\naccuracy of the batch state scheduling algorithms and the low time complexity\nof the Kalman filtering scheduling algorithms. In particular: 1) our algorithm\nis near-optimal: it achieves a solution up to a multiplicative factor 1/2 from\nthe optimal solution, and this factor is close to the best approximation factor\n1/e one can achieve in polynomial time for this problem; 2) our algorithm has\n(polynomial) time complexity that is not only lower than that of the current\nalgorithms for batch state estimation; it is also lower than, or similar to,\nthat of the current algorithms for Kalman filtering. We achieve these results\nby proving two properties for our batch state estimation error metric, which\nquantifies the square error of the minimum variance linear estimator of the\nbatch state vector: a) it is supermodular in the choice of the sensors; b) it\nhas a sparsity pattern (it involves matrices that are block tri-diagonal) that\nfacilitates its evaluation at each sensor set.\n