Approximate optimal periodic scheduling of multiple sensors with constraints

A constrained periodic multiple-sensor scheduling problem is considered in this paper. For each sensor, constraints on dwell time and activation times are imposed. At each time instant, only one sensor can update its measurement with the estimator; and the objective is to minimize the average state estimation error. An approximation framework is proposed to calculate the objective function, which transforms the original scheduling problem into an Approximate Optimal Scheduling Problem (AOSP). An upper bound on the approximation error is presented to evaluate the performance of the framework. To solve the AOSP, a necessary condition is first proposed on the optimal schedules. When no constraints on activation times exist, a dynamic programming based algorithm is devised to identify the optimal schedule with polynomial computational complexity. When activation-time constraints exist, we show that the AOSPs can be solved by solving traveling salesman problems. Examples are provided to illustrate the proposed results.