A parallel square-root algorithm for modified extended Kalmanfilter

A parallel square-root algorithm and its systolic array implementation are proposed for performing modified extended Kalman filtering (MEKF). The proposed parallel square-root algorithm is designed based on the singular value decomposition (SVD) and the Faddeev algorithm, and a very large scale integration (VLSI) systolic array architecture is developed for its implementation. Compared to other square root Kalman filtering algorithms, the proposed method is more numerically stable. The VLSI architecture described has good parallel and pipelining characteristics in applying to the MEKF and achieves higher efficiency. For n-dimensional state vector estimations, the proposed architecture consists of O(2n²) processing elements and uses O ((s+17)n) time-steps for a complete iteration at each instant, in contrast to the complexity of O((s+6) n³) time-steps for a sequential implementation, where s≈log n     

Performance evaluation of a cascaded logic for track formation inclutter

The authors present a Markov-chain-based performance evaluation technique for two-stage sliding-window cascaded logic (2/2×m /n) for track formation in a cluttered environment. The main features of this technique are that it avoids the need for extensive simulations and it is more realistic than previous methods, accounting for the association gate size variation. The gates are obtained from a Kalman filter and fully account for the transient observed for the cascaded logic following the two-point initiation from its first stage. Numerical examples of performance evaluation are given along with a logic design example     

Detectability of signals in Laplace noise

Closed-form expressions for the false-alarm and detection probabilities attained by the optimum and the linear detectors of a positive signal in n independent samples of noise having a bilateral exponential or Laplace distribution require lengthy computation when n is large, and those for the optimum detector suffer from round-off error because their terms alternate in sign. It is shown how the method of saddlepoint integration can be conveniently applied to compute these probabilities, and numerical comparisons of the accuracies of the methods are presented. The relative efficiency of the two detectors is calculated as a function of n and found to approach the asymptotic value of 2 very slowly     

Efficient algorithms for finding the K best paths througha trellis

A set of algorithms is presented for finding the best set of K mutually exclusive paths through a trellis of N nodes, with worst-case computation time bounded by N³log n for a fixed-precision computation. The algorithms are based on a transformation of the K-path trellis problem into an equivalent minimum-cost network flow (MCNF) problem. The approach allows the application of efficient MCNF algorithms, which can obtain optimal solutions orders of magnitude faster than the algorithm proposed by J.K. Wolf et al. (1989). The resulting algorithms extend the practicality of the trellis formulation (in terms of required computations) to multiobject tracking problems with much larger numbers of targets and false alarms. A response by Wolf et al. is included     

Position and force control of coordinated multiple arms

A technique is presented for controlling multiple manipulators which are holding a single object and therefore form a closed kinematic chain. The object, which may or may not be in contact with a rigid environment, is assumed to be held rigidly by n robot end-effectors. The derivation is based on setting up constraint equations which reduce the 6×n degrees of freedom of n manipulators each having six joints. Additional constraint equations are considered when one or more degrees of freedom of the object is reduced due to external constraints. Utilizing the operational space dynamic equations, a decoupling controller is designed to control both the position and the interaction forces of the object with the environment. Simulation results for the control of a pair of two-link manipulators are presented     

Extension of Euler's theorem to n-dimensional spaces

Euler's theorem states that any sequence of finite rotations of a rigid body can be described as a single rotation of the body about a fixed axis in three-dimensional Euclidean space. The usual statement of the theorem in the literature cannot be extended to Euclidean spaces of other dimensions. Equivalent formulations of the theorem are given and proved in a way which does not limit them to the three-dimensional Euclidean space. Thus, the equivalent theorems hold in other dimensions. The proof of one formulation presents an algorithm which shows how to compute an angular-difference matrix that represents a single rotation which is equivalent to the sequence of rotations that have generated the final n-D orientation. This algorithm results also in a constant angular velocity which, when applied to the initial orientation, eventually yields the final orientation regardless of what angular velocity generated the latter. The extension of the theorem is demonstrated in a four-dimensional numerical example. The issue of the correct n-D representation of angular velocity is discussed     

Target tracking in maneuver-centered coordinates

Aircraft targets normally maneuver on circular paths, which has led to tracking filters based on circular turns. A coordinate system to track circular maneuvers with a simple Kalman filter is introduced. This system is a polar coordinate system located at the center of the maneuver. It leads to a tracking filter with range, angle, and angular velocity in the state vector. Simulation results are presented, showing that the algorithm displays improved performance over methods based on constant x-y acceleration when tracking circular turns     

Decentralized CFAR signal detection

The authors develop the theory of CA-CFAR (cell-averaging constant false-alarm rate) detection using multiple sensors and data fusion, where detection decisions are transmitted from each CA-CFAR detector to the data fusion center. The overall decision is obtained at the data fusion center based on some k out of n fusion rule. For a Swerling target model I embedded in white Gaussian noise of unknown level, the authors obtain the optimum threshold multipliers of the individual detectors. At the data fusion center, they derive an expression for the overall probability of detection while the overall probability of false alarm is maintained at the desired value for the given fusion rules. An example is presented showing numerical results     

Quadratic extended Kalman filter approach for GPS/INS integration

GPS/INS integration system has been widely applied for navigation due to their complementary characteristics. And the tightly coupled integration approach has the advantage over the loosely coupled approach by using the raw GPS measurements, but hence introduces the nonlinearity into the measurement equation of the Kalman filter. So the typical method for navigation using measurements of range or pseudorange is by linearizing the measurements in an extended Kalman filter (EKF). However, the modeling errors of the EKF will cause the bias and divergence problems especially under the situation that the low quality inertial devices are included. To solve this problem, a quadratic EKF approach by adding the second-order derivative information to retain some nonlinearities is proposed in this paper. Simulation results indicate that the nonlinear terms included in the filtering process have the great influence on the performance of integration, especially in the case that the low quality INS is used in the integrated system. Furthermore, a two-stage cascaded estimation method is used, which circumvents the difficulty of solving nonlinear equations and greatly decreases the computational complexity of the proposed approach, so the quadratic EKF approach proposed in this paper is of great value in practice.     

Efficient Approximation of Kalman Filter for Target Tracking

A Kalman filter in the Cartesian coordinates is described for a maneuvering target when the radar sensor measures range, bearing, and elevation angles in the polar coordinates at high data rates. An approximate gain computation algorithm is developed to determine the filter gains for on-line microprocessor implementation. In this approach, gains are computed for three uncoupled filters and multiplied by a Jacobian transformation determined from the measured target position and orientation. The algorithm is compared with the extended Kalman filter for a typical target trajectory in a naval gun fire control system. The filter gains and the tracking errors for the proposed algorithm are nearly identical to the extended Kalman filter, while the computation requirements are reduced by a factor of four.     

Attitude determination with UD implementation of decoupled bias estimation

The application of the UD implementation decoupled bias estimation to attitude determination is analyzed here. The advantage of decoupled bias estimation in general is the reduction in the dimensions of the filter and the subsequent reduction in the amount of processing. The purpose of the UD implementation is to mitigate the effects of round-off errors. A unique advantage of the application of decoupled bias estimation to attitude determination is that the bias processing can easily be turned off whenever a reconfiguration to a bias-free estimator mode is necessary. A comparison of the attitude error of the UD decoupled Kalman filter attitude uncertainty is given with respect to the coupled Kalman filter attitude uncertainty during the time periods when the bias processing is turned off. A detailed discussion of the UD implementation is given.     

Federated square root filter for decentralized parallel processors

An efficient, federated Kalman filter is developed for use in distributed multisensor systems. The design accommodates sensor-dedicated local filters, some of which use data from a common reference subsystem. The local filters run in parallel, and provide sensor data compression via prefiltering. The master filter runs at a selectable reduced rate, fusing local filter outputs via efficient square root algorithms. Common local process noise correlations are handled by use of a conservative matrix upper bound. The federated filter yields estimates that are globally optimal or conservatively suboptimal, depending upon the master filter processing rate. This design achieves a major improvement in throughput (speed), is well suited to real-time system implementation, and enhances fault detection, isolation, and recovery capability     

航天器相对运动估计的一种并行推广卡尔曼滤波方法

 从并行的观点出发，研究应用推广卡尔曼滤波估计航天器交会对接寻的期相对位置和速率问题。推导出交会推广卡尔曼滤波公式；提出了基于奇异值分解（ＳＶＤ）和Ｆａｄｄｅｖ算法的并行平方根算法；给出了其脉动阵列（Ｓｙｓｔｏｌｉｃ）实现结构；并对阵列所需的处理单元数目和执行一次迭代所需的时间步进行了分析，说明了其实现的优越性。为航天器相对运动估计提供了一种新的有效方法     

Improving performance in pulse radar detection using neuralnetworks

A new approach using a multilayered feed forward neural network for pulse compression is presented. The 13 element Barker code was used as the signal code. In training this network, the extended Kalman filtering (EKF)-based learning algorithm which has faster convergence speed than the conventional backpropagation (BP) algorithm was used. This approach has yielded output peak signal to sidelobe ratios which are much superior to those obtained with the BP algorithm. Further, for use of this neural network for real time processing, parallel implementation of the EKF-based learning algorithm is indispensable. Therefore, parallel implementation has also been developed     

Sensor Netting via the Discrete Time Extended Kalman Filter

An implementation is presented of the discrete time extended Kalman filter which the authors have found useful for sensor netting in a variety of tactical radar and ballistic missile defense (BMD) applications. A Potter square root version of the extended Kalman filter is used where vector measurements are processed serially. Both the state and covariance equations are initialized by processing past measurements. The initialization technique and the filter are used in two tactical radar tracking examples.     

Information type filters for tracking a maneuvering target

Two previously proposed adaptive covariance-type Kalman filtering techniques for tracking maneuvering targets (see Y.T. Chan et al. ibid., p.237-44, Mar. 1979, and Z. Tang et al. Report, Department of Electrical and Computer Engineering, Oregon State University, Corvallis, Oct. 1983) are developed further to utilize the information-type Kalman filter. These adaptive information-type filters are described in structurally decoupled forms, thereby greatly reducing the computational requirements while rendering the filters amenable to implementation on parallel processors. A coherent decision procedure for including partial coupling when necessary is developed via offline analysis of crosscorrelation functions     

A Fault-tolerance Estimating Method for Ionosphere Corrections in Satellite Navigation System

 Aiming to the reliable estimates of the ionosphere differential corrections for the satellite navigation system in the presence of the ionosphere anomaly, a fault-tolerance estimating method, which is based on the distributed Kalman filtering, is proposed. The method utilizes the parallel sub-filters for estimating the ionosphere differential corrections. Meanwhile, an infinite norm (IN) method is proposed for the detection of the ionosphere irregularity in the filter processing. Once the anomaly is detected, the sub-filter contaminated by the anomaly measurements will be excluded to ensure the reliability of the estimates. The simulation is conducted to validate the method and the results indicate that the anomaly can be found timely due to the novel fault detection method based on the infinite norm. Because of the parallel sub-filter architecture, the measurements are classified by the spatial distribution so that the ionosphere anomaly can be positioned and excluded more easily. Thus, the method can provide the robust and accurate ionosphere differential corrections.     

Multiple target tracking using products of position measurements

The continued development of the symmetric measurement equation (SME) filter for track maintenance in multiple target tracking (MTT) is considered, focusing on the case in which the SMEs are generated by forming sums of products of the original position measurements. The SME filter is developed for the case of N targets whose motions consist of random perturbations about constant-velocity trajectories. It is assumed that measurements of x-coordinate positions are available, and that the number of measurements is equal to the number of targets. Various analytical properties of the SME filter are studied. It is shown that under a very weak condition, the estimation error equation is locally exponentially stable. The performance of the SME filter is investigated by comparing it with an optimal (minimum-variance) estimator and by generating a computer simulation in the six-target case     

Performance Degradation in Digitally Implemented Kalman Filters

A technique is presented for analyzing expected degradations in the performance of a fixed-point arithmetic implementation of a Kalman filter with precomputed gains. A quantitative approach is provided for comparing the relative degradations associated with different mechanizations of the same Kalman filter. The causes of divergence in digitally implemented filters are investigated. Finally, simulation studies are utilized to show how closely the analytical predictions agree with actual results.     

Adaptive Tracking Filter for Maneuvering Targets

A general method of continually restructuring an optimum Bayes-Kalman tracking filter is proposed by conceptualizing a growing tree of filters to maintain optimality on a target exhibiting maneuver variables. This tree concept is then constrained from growth by quantizing the continuously sensed maneuver variables and restricting these to a small value from which an average maneuver is calculated. Kalman filters are calculated and carried in parallel for each quantized variable. This constrained tree of several parallel Kalman filters demands only modest om; puter time, yet provides very good performance. This concept is implemented for a Doppler tracking system and the performance is compared to an extended Kalman filter. Simulation results are presented which show dramatic tracking improvement when using the adaptive tracking filter.