For target tracking applications, a Kalman filter is generally used to estimate the kinematic components of a manoeuvring target (position, velocity and acceleration) from noisy measurements. The tracking algorithm is selected according to a trade-off between its performance and real-time computational requirements when choosing the level of complexity of the model. According to the application, either a linear or a nonlinear Kalman filter algorithm can be used to track manoeuvring targets. However, although excellent accuracy estimates can be achieved with any chosen algorithm, it requires a huge amount of calculation thus making real-time processing impossible.
This paper investigates the parallel implementation of tracking Kalman filters (EKF, GRF, LDKF and MGEKF) in both 2- and 3-D frames onto a range of transputer topologies to enable practical realisations. The partitioning strategies are highlighted, real-time implementation results are presented, and the relative speedup and efficiency are calculated to evaluate the performance of each parallel implementation.
Anon. 1989. Parallel C User Guide. 31 Ltd, UK, Nov.
2.
Anon.1990. IMS B008: User Guide and Reference Manual. INMOS Ltd.
3.
Baheti, R.S.1986. 'Efficient approximation of Kalman filter for target tracking'. IEEE Trans on Aerospace and Electronic Systems, AES -22(1), 8-14, Jan.
4.
Baheti, R.S., and O'Hallaron, D.R.1988. 'Fast mapping of a Kalman filter on Warp'. In: SPIE Symposium, Real-Time Signal Processing XI, San Diego, California, USA, Aug. CA: Society of Photo-Optical Instrumentation Engineers.
5.
Baheti, R.S., O'Halloran, D.R., and Itzkowitz, S.1990. 'Mapping extended Kalman filters onto linear arrays '. IEEE Trans on Automatic Control, AC-35(12), 1310-1319, Dec.
6.
Bar-Shalom, Y., and Fortmann, T.E.1988. Tracking and Data Association, vol 179 of Mathematics in Science and Engineering. Academic Press, Inc, USA.
7.
Berg, R.F.1983. 'Estimation and prediction for maneuvering target trajectories '. IEEE Trans on Automatic Control, AC-28, (3), 294-304, Mar.
8.
Chang, C.B., and Tabaczynski, J.A.1984. 'Application of state estimation to target tracking'. IEEE Trans on Automatic Control, AC-29, 98-109, Feb.
9.
Daum, F.E., and Fitzgerald, R.J.1983. 'Decoupled Kalman filters for phased radar tracking'. IEEE Trans on Automatic Control , AC-28, 269-283, Mar.
10.
El-Mahy, M., and White, B.A.1993a. Parallel Implementation of Target Tracking Kalman Filters Onto Full-Linking Transputer Networks, Vol 2. IOS Press.
11.
El-Mahy, M.K., and White, B.A.1993b. The use of the Kalman filter for target tracking and parallel transputer'. In: 1993 SERC/InstMC Postgraduate Research Symposium in Control and Instrumentation, University of Nottingham, UK, 30-31 Mar.
12.
El-Mahy, M.K., Kellett, M.G., and White, B.A.1992. 'Efficient parallel implementation of target tracking Kalman filters using a network of transputers'. In: The IMA Conference on Aerospace Vehicle Dynamics and Control, Cranfield Institute of Technology, Bedford, UK, 7-10 Sept.
13.
Gaston F.M.F.1989. 'Systolic Algorithms and Architectures for Kalman Filtering'. PhD thesis, Faculty of Engineering, The Queen's University of Belfast, Apr.
14.
Graham, I., and King, T.1990. The Transputer Handbook. Prentice Hall .
15.
Iiguni, Y., Sakai, H., and Tokumaru, H.1990. 'A parallel implementation of tracking Kalman filter on a multi-processor system'. Trans Inst Electronics, Information and Communication Engineers, A,J73-A(1), 1-6.
16.
Kee, R.J.1992. 'Estimation For Homing Guidance'. PhD thesis, Faculty of Engineering, Department of Electrical and Electronic Engineering, The Queen's University of Belfast, Jan.
17.
Kee, R.J., and Irwin, G.W.1989. 'Parallel Implemenation of the Tracking Kalman Filter Using a Network of Transputers'. In: IEE Colloquium on 'Navigation, Guidance and Control on Aerospace', vol Digest No 142, pp 1/1-1/7.
18.
Kee, R.J., and Irwin, G.W.1991. 'Transputer Implementation of Tracking Kalman Filters '. In: IEE Control '91, vol 2, pp 861-866.
19.
Lawrie, D.I.1990. 'Parallel Processing Algorithms and Architectures for the Kalman Filter'. PhD thesis, Faculty of Engineering , University College of NorthWales, UK.
20.
Lee, K.B., and Haykin, S.1988. 'Parallel Implementation of the Tracking Kalman Filter ' In: ICASSP 88: Int conf on Acoustics, Speech and Signal Processing , vol 4, 2092-2095.
21.
Mead, C., and Conway, L.1980. Introduction to VLSI Systems. Addison-Wesley , Reading, Mass.
22.
Nocetti, D.F.G.1991. 'Parallel Processing in Digital Flight Control'. PhD thesis , University of Wales, Bangor, UK, Feb.
23.
Ohmuro, T.1984. 'A decoupled Kalman tracker using LOS coordinates '. In: Proc 1984 Int Symp on Noise and Clutter Rejection in Radars and Imaging, 451-455.
24.
Pattipati, K.R., Kurien, T., Lee, R.J., and Luh, P.B.1990. On mapping a tracking algorithm onto parallel processors'. IEEE Trans on Aerospace and Electronic Systems, AES -26(5), 774-791, Sept.
Pountain D.1988. A Tutorial Introduction to OCCAM Programming. Blackwell Ltd.
27.
Singer, R.A.1970. 'Estimating optimal tracking filter performance for manned maneuvering targets'. IEEE Trans on Aerospace and Electronic Systems , AES-6(4), 473-483, Jul.
28.
Song, T.L., Ahn, J.Y., and Park, C.1988. 'Suboptimal filter design with pseudo-measurements for target tracking. IEEE Trans on Aerospace and Electronic Systems , AES-24(1), 28-39, Jan.
29.
Sung, T.Y., and Hu, Y.H.1986, 'VLSI Implementation of real-Time Kalman Filter '. In: ICASSP 86: Int conf on Acoustics. Speech and Signal Processing, 41.23.1-41.23.4, Tokyo.
30.
Sung, T., and Hu, T.1987. 'Parallel VLSI implementation of the Kalman filter .' IEEE Trans on Aerospace and Electronic Systems, AES-23(2), 215-224, Mar.
31.
Woods, R., McCanny, J., and Irwin, G.1991. 'VLSI systems for DSP and control'. In: Lawrie, D., and Fleming, P. (Eds), Parallel Processing of the Kalman Filter. Woodhead Publishing Ltd, Cambridge, UK, pp.15-20.
