Predicting physical processes in the presence of faulty sensor readings

A common problem in the operation of mission critical control systems is that of determining the future value of a physical quantity based upon past measurements of it or of related quantities. Some of the sources of variability that make this problem difficult include imprecision due to measurement error, measurements that change with time, and intermittent failures leading to faulty measurements. We present a novel solution to this problem based upon the following hypotheses: each measurement is presented as a time-stamped interval that contains the correct value of the physical quantity; the underlying process describing the physical quantity is linear or a low-degree polynomial; and up to f of the n measurements may be arbitrarily faulty, where n/spl ges/2(f+1). For a given future time t/sub o/, our algorithm produces the smallest set of possible values that the function may take at time t/sub o/. For linear functions, our algorithm runs in time O(n/sup 2/), and for degree-d polynomials it runs in time O(n/sup d+1/).