Fractionally Delayed Kalman Filter

Abhinoy Kumar Singh

Abstract—The conventional Kalman filter is based on the assumption of non-delayed measurements. Several modifications appear to address this problem, but they are constrained by two crucial assumptions: 1) the delay is an integer multiple of the sampling interval, and 2) a stochastic model representing the relationship between delayed measurements and a sequence of possible non-delayed measurements is known. Practical problems often fail to satisfy these assumptions, leading to poor estimation accuracy and frequent track-failure. This paper introduces a new variant of the Kalman filter, which is free from the stochastic model requirement and addresses the problem of fractional delay.The proposed algorithm fixes the maximum delay (problem specific), which can be tuned by the practitioners for varying delay possibilities. A sequence of hypothetically defined intermediate instants characterizes fractional delays while maximum likelihood based delay identification could preclude the stochastic model requirement. Fractional delay realization could help in improving estimation accuracy. Moreover, precluding the need of a stochastic model could enhance the practical applicability. A comparative analysis with ordinary Kalman filter shows the high estimation accuracy of the proposed method in the presence of delay.

I. INTRODUCTION

THE conventional Kalman filter [1] assumes that measurements are non-delayed in time [2], [3], even though every practical system involves certain delays. If the delay is large,the measurement carries inappropriate information about the state dynamics. Subsequently, the state estimation with delayed measurement suffers from poor estimation accuracy and frequent track-failure.

In many real-life problems measurements are time stamped and the measurement system has access to a clock, e.g. a network time protocol [4] based time distribution in large and diverse network systems, leading to a known delay. Such a delay can be modelled with a time-shift in measurements and the ordinary Kalman filter can be implemented. In the absence of time stamping and clock access, e.g. linear frequency modulator radar systems [5] where delay is in micro-seconds and a clock has such small resolution that it is infeasible in low budget applications, the delay remains unknown. An unknown and time varying delay is commonly known as random delay [6], [7], however early filtering literature cited such a delay with different names viz. out of sequence measurements (OOSM) [8], [9], filtering with random sample delay [10], [11], filtering with random time delayed measurements [12], etc. The filtering problems with randomly delayed measurements commonly appear in communication[13], control [14], target tracking [15], network systems [16],[17] etc.

The literature on state estimation with delayed measurements begins with the work of Rayet al. [18] which involved using a reformulated minimum error variance estimator to deal with randomly delayed measurements. The estimation in this approach was based on sensor data statistics and the maximum delay was assumed to be one-step i.e. the measurement at an instant is either one-step delayed or non-delayed. Yaz and Ray modified this approach in [19] by introducing Grammiam assignment for stochastic parameters of the delayed model, and further modified it in [20] by introducing a linear matrix inequality based stochastic parameter estimation technique.Later, a series of developments [21]-[26] appeared in the literature to further improve filtering performance. In [21], an optimal estimation technique was developed for multiple delayed measurements by extending the ordinary Kalman filter to work in delayed environments. In later developments[22]-[24], the robust and adaptive Kalman filtering techniques were extended for delayed measurements to counter constraints such as model and process error uncertainties. Another popular method [25] was introduced by S. Sun, which modelled the unknown delay with a set of Bernoulli random variables and obtained an optimal estimation in terms of the Riccati difference equation and Lyapunov difference equation. In[26], the delayed measurement Kalman filtering algorithm was further extended for the multiplicative noises.

The discussed filtering techniques for delayed measurements suffer from several drawbacks. To begin with,they are restricted to zero mean, white, Gaussian and uncorrelated noises, similar to the ordinary Kalman filter.Thankfully, some extensions of ordinary Kalman filter, e.g.[27] and [28], can be implemented with to mitigate these restrictions. Another drawback is that the above algorithms are sensitive to model validity, which is minimized up to some extent by implementing robust extension [29] of the ordinary Kalman filter. Another disadvantage is the discrete-time approximation of continuous process model which can be mitigated with continuous-time extension [30] of the ordinary Kalman filter. Apart from these drawbacks, there are certain limitations against which no proven solution is available in the literature. This paper introduces a solution for two of such limitations as mentioned below:

1) Existing delay filters approximate the delay as an integer multiple of the sampling interval (Fig. 1(a)), though it is ideally fractional (Fig. 1(b)). Thus, poor estimation accuracy and frequent track-failures are observed if the sampling interval is sufficiently large.

Fig. 1. Delay representation.

2) Existing delay filters essentially require a stochastic model representing a stochastic relationship between the delayed measurement and a sequence of possible non-delayed measurements. Such models are formulated with a sequence of delay probabilities which are mostly unpredictable in practical problems. Therefore, existing delay filters are inapplicable to many real-life problems (where the probabilities are unknown), and have poor estimation accuracy (where an approximate stochastic model can be formulated with poorly estimated delay probabilities).

To counter the aforementioned limitations, this paper proposes a novel modification of the Kalman filter which addresses the problem of fractional delay and does not require the aforementioned stochastic model. The proposed algorithm is named as fractionally delayed Kalman filter.

In the case of fractionally delayed measurements, the ideal measurement time, which is defined as the arrival time for a measurement if there was no delay, can be in intermediate of previous sampling instants. Subsequently, the delay τdcan be a fractional multiple of sampling intervalT, besides being an integer multiple [18], [21], [25]. To characterize such a delay,a series of intermediate instants is defined hypothetically between two sampling instants. At timetk, the delayed instanttk-τdis one of these intermediate instants. Thus, the delay τdcould be estimated by defining a maximum likelihood based cost function and comparing it across all the intermediate instants (in the range of presumed maximum delay). The likelihood based delay identification could preclude the concerning stochastic model. Based on the τdestimate, the ideal measurement time foryk(measurement received attk)could be identified astk-τd. Subsequently,ykis used for state estimation attk-τdinstead oftk. In this regard, the covariance and optimal Kalman gain are re-derived for state estimation attk-τdusing the delayed measurementyk. Note that the filtering objective is to estimate the states at current instanttk(with measurementyk). Therefore, a sequential timeupdate approach, adopted from [31], [32], is implemented fromtk-τdtotk, and the desired estimates are obtained attk.

The proposed algorithm is tested in an environment of randomly delayed measurements. The test analysis shows an improved estimation accuracy for the proposed method compared to the ordinary Kalman filter.

II. KALMAN FILTER AND CHALLENGES WITH RANDOMLY DELAYED MEASUREMENTS

The Kalman filter is implemented over the dynamic state space model which is composed of process and measurement equations, as

where xk∈Rnandyk∈Rpare state and measurement vectors at thekth instant,k∈{0,1,2,...,N} withNbeing the number of samples,FkandHkare constants with appropriate dimension and,qkandvkare process and measurement noises, respectively. The process noise accounts for modeling error while the measurement noise compensates for the sensor error. The noises,qkandvk, are assumed to be white and Gaussian with zero mean and covarianceQkandRk, respectively.

The Kalman filter is implemented in two steps: time update and measurement update.

1). Time Update

This step predicts the estimate and covariance of states, one step forward in time, as [2], [3]

2). Measurement Update

This step determines the posterior estimateand covariance (Pk|k) at thekth instant. Prior to computingand, the estimate of measurement (yˆk|k-1) , innovationinnovation covariance (Sk) and an optimal Kalman gain (Kk)are computed as [2], [3]

A. Challenges With Randomly Delayed Measurements

As in (4), the state estimation accuracy depends on the accuracy of innovation,Due to delay,ykconsists of the state information associated withtk-τdwhere τd∈[0,tk). On the other hand,which is the predictedykand obtained by propagating xk-1|k-1through the state space model, consists of the state information attk. Thus, the state information comprised byykanddiffer in time by τd,resulting in an inappropriate computation ofThe state estimation with an inappropriateleads to poor estimation accuracy (equation (4)). The existing delay filters compensate for this difference up to some extent by presuming a stochastic model for delayed measurements;wherezkrepresents a possible non-delayed measurement attk, βiis a Bernoulli random variable with probabilityP(βi=1)=pi(also representsi-step delay probability) anddis the maximum possible delay at any instant. Based on this stochastic model,could be obtained by averaging the estimates ofzkat the current and delayed instantsThus, we getwhich provides a better match withykcompared to the traditional estimate

Stochastic model based filtering has two major drawbacks:1) the stochastic model is based on the integer delay assumption, hence fractional delay is beyond the scope, and 2)the computation of estimateis subject to an accurate knowledge of probabilitiespi∀i∈{1,2,...,d} which is very much unexpected in practical problems.

The problem of fractional delay can be simplified to an integer delay if the delay is known and the sampling interval is adjustable. However the random delay (which is the interest of this paper) refers to an unknown and time-varying delay[6], [7], hence such simplification is overruled. Moreover, the sampling interval is often not under the control of practitioners, e.g., [15], causing another restriction on such simplification.

Filtering with fractionally delayed measurements is challenging for following reasons: 1) in case of the stochastic model based filtering, the number of probabilities in the stochastic model is very large due to intermediate instants involved, causing higher uncertainty in the model, and 2)ordinary filters, including the existing delay filters, are designed to perform the filtering updates (time update and measurement update) at sampling instants, however filtering with a fractional delay essentially requires the updates at intermediate instants.

III. FRACTIONALLY DELAYED KALMAN FILTER

In this section, a modified Kalman filter is introduced to improve the estimation accuracy in filtering with randomly delayed measurements. The proposed algorithm determines the ideal measurement time forykusing a likelihood based approach. The ideal measurement time can be in intermediate of two sampling instants, given that the delay is fractional.Subsequently, the delay could be characterized by definingmintermediate instants between successive sampling instants.The time duration between two intermediate instants is δ=T/m(Tis the sampling interval). The intermediate instants are denoted asthus(asjbecomesm) representstk+1. In the remaining part of this paper, the filter parameters at intermediate instants are represented with following notations:

with A being a hypothetical parameter.

Remark 1: A highermoffers better precision in estimating ideal measurement time, but increases the computational burden. Thus,mshould be chosen as large as possible under the preassigned computational budget.

The proposed algorithm consists of three steps:

a) time update,

b) ideal measurement time estimation,

c) measurement update.

A. Time Update

The time update fromtk-1totkis performed through intermediate instants. Subsequently, the estimate and covariance at an intermediate instanttk-1+jδ could be obtained as

B. Ideal Measurement Time Estimation

Let us assume, the maximum delay does not exceeddsampling instants (i.e.,d×T). Let us defineDtas a set of time instants that consists of every possible ideal measurement time foryk, thenA simplified notation isδ} wherej∈{1,2,···,m}. Note thatdis a practitioner’s choice, hence the proposed algorithm is not restricted in terms of maximum delay. Let us assumetsis a past sampling instant within the range of the maximum delay, i.e.,ts∈{tk-d,thenandcan be determined for allj∈{1,2,...,m} using (6). Based on these quantities, the outcome of following Lemma offers a mathematical tool for estimating the ideal measurement time foryk.

Lemma 1:Ifrepresents a negative Gaussian log likelihood thatykcorresponds to a delayed instantts+jδ, then

Proof: The Kalman filter is based on Gaussian assumption of state vector xk.Thus,a linear state space model (which is the assumption of this development) insures a Gaussian distribution forykas well. Let us assume that the Gaussian distribution parameters, mean and covariance, ofykare µ and Σ, respectively, then

whereP(·) represents probability density function (pdf) andp is the dimension ofyk.

Let us denoteas the likelihood thatykcorresponds to a delayed instant (ts+jδ ). Ifholds true, thenykmust follow the estimate and covariance of a hypothetical measurement corresponding to (ts+jδ ), i.e.,andHence,

The likelihood analysis is typically an arithmetic comparison,hence, a logarithmic simplification of likelihoods does not harm the generality. Thus, a simplified expression forcould be obtained as

Following the similar argument,could be further simplified by removing the constant additive termand thereafter the constant multiplication factor 1/2, i.e.

Note that x andyare linearly related (equation (2)), hence

similar to (3).

Substituting (9) into (8),

is the likelihood ofykassociating with a delayed instant (ts+jδ), which can be obtained for every possible element ofDt. The element ofDtfor which the likelihood ofykis the largest is naturally the ideal measurement time.

Note:represents a negative likelihood function,hence the maximum likelihood is obtained as the minimum of.

Afterykis received atcould be computed for alls∈{k-d,k-d+1,...,k-1} and for allj∈{1,2,...,m}, i.e. for every element ofDt. Subsequently, if (ts*+j*δ) is the ideal measurement time foryk, then (s*,j*) could be obtained as

C. Measurement Update

The objective of this step is to construct the posterior estimate parameters attk, i.e.and Pk|k, as soon asykis received. As discussed above,ykis most likely to be arriving from (ts*+j*δ) (ideal measurement time) instead oftk. Hence,it is appropriate for computingandinstead ofand Pk|k. The proposed algorithm computesand Pk|kin two steps: i) based onyk,the posterior estimation is performed to obtainandat (ts*+j*δ), and ii)andare sequentially updated [31], [32] from (ts*+j*δ) totkto obtainand Pk|k.

1) Posterior Estimation at(ts*+j*δ): Following the Kalman filtering strategy [2], the posterior estimation at(ts*+j*δ)requires an optimal Kalman gainat (ts*+j*δ). For the Kalman gainto be optimal, it must minimize the trace of error covariance matrix[2 ]. This paper computes the optimal Kalman gainthrough two subsequent lemmas. The first lemma formulates a generalized expression forwhile the second lemma determinesfor which the trace ofis minimum.innovation and innovation covariance at (ts*+j*δ) may be

Before proceeding forward, the estimate of measurement,computed as

Lemma2:If (ts*+j*δ) is the ideal measurement time foryki.e.then a generalized expression forcould be given as

Proof: The posterior covariance at (ts*+j*δ) is

similar to (4).

Following the system dynamics,

Substitutingykandfrom (15) and (11) in (14),

Simplifying further,

Asis uncorrelated,

A further simplification to above equation gives

Asand

The representation of the covariance matrix in form of (12)is also known as Joseph’s form [3] of covariance matrix

Lemma3:The optimal Kalman gainand corresponding error covarianceat intermediate instant (ts*+j*δ) are

and

Proof: As the optimal value ofminimizes the trace of[2],

Expanding and further simplifying theexpression in (12),

Substitutingfrom (11),

Thus, the optimal Kalman gain is obtained as

After the optimal Kalman gainis obtained, the posterior estimate at (ts*+j*δ) may be determined as

At this st age, the posterior covariance at (ts*+j*δ) can be given as

2) Computation ofandPk|k: Aswe can denoteasandas. It is to be noted that the objective of filtering is to estimate the states in real-time, i.e. to determineand Pk|kusingyk.Therefore,andare sequentially updated[31], [32] from (ts*+j*δ) totkto obtainand Pk|k.

Let us assume thatmdis the number of intermediate instants between (ts*+j*δ) andtk; then,md=(k-s*-1)m+(m-j*).Asandcorrespond to (ts*+j*δ),mdtimes sequential update is required for obtainingand Pk|k. For the linear state dynamics,ith update could be obtained as

This update step is performed recursively untilireachesmd.Oncei=mdis reached, the desired posterior estimate and covariance are obtained as

A complete block-diagram for implementing the proposed method is provided in Fig. 2.

The filter design technique introduced in this section does not use a stochastic model and accounts for fractional delay,leading to higher estimation accuracy. On the other hand, it requires the storage of the estimated data from delayed instants, hence requires a larger storage budget compared to the ordinary Kalman filter. The general assumptions involving noise in Kalman filter design, such as white, zero mean Gaussian and uncorrelated noises, are imposed over the proposed algorithm as well.

IV. SIMULATION

In this section, the proposed method is implemented for a filtering problem with randomly delayed measurements. The performance of the proposed method is compared with ordinary Kalman filter in terms of root mean square error(RMSE).

A. Dynamic State-Space Model

The system under consideration follows a linear state dynamics, given as

Fig. 2. Flow chart for implementing the proposed algorithm.

whereqkis process noise. The process noise is assumed to be normally distributed with zero mean and covariance

whereT=0.5 is sampling interval and c=10×10-6is constant.

With ideal behaviour (with no delay in measurements), the measurement system observes the first state as a measurement at every sampling interval. Thus, the expected non-delayed measurement could be modelled as

whereHk=[1 0], andvkis the measurement noise component which is approximated as Gaussian with zero mean and covarianceRk=1.

B. Delayed Measurement Simulation

With the lack of real-life data, a simulated dataset has been generated in Matlab to characterize the randomly delayed measurements. The data simulation is based on a presumed stochastic model for delayed measurements, in a dynamic system represented by (24) and (25). The maximum possible delay is assumed to bedsampling intervals. The fractional delay is characterized by assigningmintermediate instants between two sampling instants. Subsequently, the measurementykreceived attkcorresponds to an instant inDtdefined in Section III-B. Thus, the delayed measurementykcould be modelled using a set of Bernoulli random variablesand ∀j∈{1,2,...,m} i.e.Note thatindicates thatts+jδ is the ideal measurement time foryk. Thus,ykcould be modelled as

Note thatis a hypothetical non-delayed measurement atts+jδ.

During the data simulation, it was assumed that multiple measurements are not received at any instant, hence β(s,j)can be 1 for only one pair ofsandjattk. To be noted, it is possible that∀s∈{k-d,k-d+1,...,k-1} and ∀j∈{1,2,...,m} attk, demonstrating the case where there is a missing measurement, which is observed if the delay has a sudden increase.

It is understood in above discussion thatp(k-1,m)is the probability of receiving a non-delayed measurement. To simulate the measurement data,p(k-1,m)was taken as 0.3 and the remaining probability was equally distributed overdsampling intervals (including the intermediate instants).

It should be noted that the delay measurement model (26) is used only for generating simulated measurement data, with no role in the filtering algorithm.

C. Implementation and Results

The proposed algorithm is implemented over 500 time-steps(k∈{1,2,...,500}) to estimate the states of the dynamic system represented by (24) and (25). For comparison purposes, the simulated data for the states were generated using (24) with initial state being x0=[0 0]Twhere T denotes transpose of matrix. The delayed measurement data was simulated using the stochastic model given in (26). For filter implementation, the initial estimatewas assumed to follow the Gaussian distribution with mean x0and initial covariance P0|0=diag([1 1]).

1) Estimation Accuracy: To analyze the estimation accuracy, the estimateand the true state xk∀k∈{1,2,...,500}are plotted for individual states in Fig. 3. An appreciable match between the true state and the estimated state reflects a high estimation accuracy for the proposed method. It also reflects the ability of the proposed method in dealing with fractionally delayed measurements.

Fig. 3. True and estimated states.

2)Comparison with Ordinary Kalman Filter: The comparison between the proposed algorithm and the ordinary Kalman filter is based on RSME analysis. The RMSE is computed by implementing several independent Monte-Carlo runs. At thekth step, the RMSE forith state is determined as

whereM=1000 is the number of Monte-Carlo runs.

For most of the practical systems, the delay is not muc h larger than the sampling interval [33], hence, the analysis has been limited to the case where the maximum delay does not exceed 5 sampling intervals. For the case of maximum delay not exceeding 1 and 2 sampling intervals, the RMSE for the proposed method and the ordinary Kalman filter are plotted in Figs. 4 and 5, respectively. In these figures, the Kalman filter is abbreviated as KF. For higher delays, the average RMSE(between 100 to 500 steps) is compared in Table I and II. The proposed method has a convergence time of 100 steps, hence the comparative analysis begins after this duration. The tables also analyze the relative reduction in RMSE for the proposed method compared to the ordinary Kalman filter.

The plots and tables indicate a significantly reduced RMSE for the proposed method compared to the ordinary Kalman filter. It concludes a better estimation accuracy for the proposed algorithm in the presence of delay.

Fig. 4. RMSE plots: maximum delay being 1 sampling interval.

Fig. 5. RMSE plots: maximum delay being 2 sampling intervals.

TABLE IAVERAGE RMSE OF STATE 1

TABLE II AVERAGE RMSE OF STATE 2

To analyze the rise in computational time, the execution time was studied for the proposed algorithm as well as the ordinary Kalman filter by implementing them over 500 timesteps. The implementation was performed in the Matlab environment on a personal computer with a 64-bit operating system, 4GB RAM, and 2GHz intel core i3 processor. The execution time (s) for the proposed method was 0.2400,0.4740, 0.6705, 0.8689 and 1.0785 for maximum delay varying from 1 to 5 sampling intervals, respectively.However, the execution time was constant around 0.02 seconds for all delay cases using the ordinary Kalman filter.

V. DISCUSSION AND CONCLUSION

Time delay is a common phenomena in physical measurement systems, though it may be sufficiently small to ignore in several cases. The Kalman filter in its traditional form ignores the measurement delay, and suffers from poor estimation accuracy and frequent track-failure if the delay is sufficiently large. The existing variants of the Kalman filter for addressing measurement delay are constrained with two major assumptions: 1) the delay is an integer multiple of sampling interval, and 2) a precise stochastic model is known for delayed measurement (in terms of a sequence of possible non-delayed measurements). The practical problems usually do not fulfill these assumptions, leading to poor estimation accuracy and often track-failure. A new variant of the Kalman filter is proposed in this paper to address the fractional delay and remove the constraints of the stochastic model.Addressing the fractional delay is advantageous in improving estimation accuracy, while not using the stochastic model could enhance practical applicability in addition to improving the estimation accuracy. The simulation results report a reduced RMSE for the proposed method compared to the ordinary Kalman filter, demonstrating an improved estimation accuracy in presence of delay. On the other hand, the computational time for the proposed method is reported to be larger than the ordinary Kalman filter. The fundamental assumptions on noises, including zero mean, white, Gaussian and uncorrelated, when designing an ordinary kalman filter,are imposed with the proposed method as well. The future extension of the proposed algorithm has multiple scopes, e.g.improving estimation accuracy further, reducing computational time, and removing the constraints on noisesetc.