Online Target Localization Using Adaptive Belief Propagation in the HMM Framework

Abstract

This letter proposes a novel adaptive sample space-based Viterbi algorithm for target localization in an online manner. The method relies on discretizing the target's motion space into cells representing a finite number of hidden states. Then, the most probable trajectory of the tracked target is computed via dynamic programming in a Hidden Markov Model (HMM) framework. The proposed method uses a Bayesian estimation framework which is neither limited to Gaussian noise models nor requires a linearized target motion model or sensor measurement models. However, an HMM-based approach to localization can suffer from poor computational complexity in scenarios where the number of hidden states increases due to high-resolution modeling or target localization in a large space. To improve this poor computational complexity, this letter proposes a belief propagation in the most probable belief space with a low to high-resolution sequentially, reducing the required resources significantly. The proposed method is inspired by the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -d Tree algorithm (e.g., quadtree) commonly used in the computer vision field. Experimental tests using an ultra-wideband (UWB) sensor network demonstrate our results.