Adaptive Particle Filters for Wireless Indoor Target Tracking

Abstract

Particle filters (PFs) are efficient tools for nonlinear state estimation especially for a wireless indoor target tracking system, who estimates the target's position using wireless facilities in the buildings or houses. Particle filters are recursive Monte-Carlo methods based on Bayes' theorem, which fuse the previous state information and the current measurement data to obtain the target position. The advantage of using PFs is that the heterogeneous information can be combined effectively within the PFs to estimate the unknown state. The purpose is to design PF algorithms with high estimation accuracy, where average absolute error approaches 0, and make PFs robust to hybrid line-of-sight (LOS) and non-line-of-sight (NLOS) errors. Particle filters should also have a low computational complexity. The major contributions are five folds: 1\. The impact of instantaneous measurement error is firstly found and analyzed in this thesis. It is the major source of the estimation error of PFs. According to the analysis, a likelihood adaptation method is proposed to reduce the instantaneous measurement error. Then, adaptive PFs integrated with the likelihood adaptation method are developed. 2\. Due to the NLOS and multi-path effect, the ranging error is difficult to model in indoor environment. Therefore, a dynamic Gaussian model (DGM) is proposed to describe the distribution of hybrid LOS/NLOS ranging errors. Then, adaptive PFs using DGM are extended in the high dynamic indoor environment still with the accurate estimation. 3\. Design the architecture of a real world tracking system for adaptive PFs. In addition, adaptive PF fusing building layout information to improve the estimation accuracy is proposed. 4\. Propose distributed PFs protocols to collaboratively estimate the target using local anchors. Selective gossip algorithms are applied in the distributed PF design. 5\. Theoretical analysis of the adaptive PFs for the estimation performance based on the Cramer-Rao lower bound. It is proved that with reliable priori information, the adaptive PFs outperform conventional PFs. The performance of the adaptive PFs are evaluated in various simulations and real world experiment. The estimation results are compared with the conventional PFs and other localization algorithms. For the conventional PFs, the average absolute errors have biases, which are about 0.5m to 1m, and the root mean square error (RMSE) is more than 2m, but the average absolute errors of proposed adaptive PFs can approach to 0 and RMSEs are only about 1.5m error, which meets the requirements of the indoor location based services. In addition, only 30 particles are required in the adaptive PFs, which significantly reduce the computational complexity. In real world experiments, adaptive PFs also outperform other localization algorithms, e.g. linear least square method, nonlinear least square method, min-max algorithm, extended Kalman filter, etc. The estimation accuracy of distributed PFs using selective gossip algorithms are guaranteed. The communication overheads are also significantly reduced compared with other distributed consensus based schemes.

Partikel Filter (PF) sind effiziente Werkzeuge zur nichtlinearen Zustandsschätzung und eignen sich besonders für drahtlose Indoor Tracking Systeme die sich dazu eignen die Position eines Objektes innerhalb von Gebäuden zu schätzen. Partikel Filter entsprechen rekursiven Monte-Carlo Verfahren die auf dem Bayes-Theorem basieren, das die vorher bekannte Position mit neuen Messwerten fusioniert um auf die aktuelle Position zu schließen. Der große Vorteil von PFs besteht darin, das heterogene Informationen effektiv kombiniert werden können um den unbekannten Zustand zu ermitteln. Mein Ziel ist PF Algorithmen mit hoher Genauigkeit zu entwerfen, deren durchschnittlicher Fehler gegen 0 geht und die ein hohes Mass an Robustheit gegenüber Line-of-sight (LOS) als auch Non-line-of-sight (NLOS) Fehlern aufweisen. Die PF Algorithmen sollten außerdem möglichst wenig komplex und einfach berechenbar sein. Die fünf wichtigsten wissenschaftlichen Beiträge dieser Arbeit sind: 1\. Der Einfluss des momentanen Messfehlers wird in dieser Arbeit analysiert. Der Messfehler ist die Hauptursache für Schätzungsfehler eines Partikelfilters. Auf Basis der Analyse wird ein Likelihood Verfahren vorgeschlagen, welches den Messfehler reduziert. Nachfolgend werden adaptive PF vorgeschlagen, die das Likelihood Verfahren anwenden. 2\. Aufgrund von NLOS und multi-path Effekten ist der Entfernungsfehler einer Messung in einer Indoor-Umgebung schwer zu modellieren. Zur Lösung dieses Problems wird ein dynamisches Gauss-Model (DGM) vorgeschlagen um die Verteilung von hybriden LOS/NLOS Entfernungsfehlern zu beschreiben. Das DGM wird anschließend ebenso in einem adaptiven PF integriert um die Genauigkeit der Zustandsschätzung zu verbessern. 3\. Es wird eine Real-World Architektur für ein PF basiertes Tracking-System vorgelegt. Des Weiteren wird vorgeschlagen vorhandene Karteninformationen als zusätzliche Eingabe für den adaptiven PF zu verwenden um die Genauigkeit zu steigern. 4\. Es werden verteilte PF Protokolle vorgeschlagen um eine kollaborative Schätzung der Position eines Objektes zu ermöglichen. Selektive Gossip-Algorithm bilden dabei die Grundlage für das verteilte PF Verfahren. 5\. Eine theoretische Betrachtung der Schätzqualität der PF anhand der Cramer-Rao-lower-bound. Es wird dabei bewiesen, das adaptive PFs mit zuverlässigen a priori Informationen bessere Schätzungen liefern als herkömmliche PFs. In mehreren Simulationen und real world Experimenten wird die Performance von adaptiven PFs evaluiert. Die Resultate des Schätzers werden mit den Resultaten konventioneller PF und anderen Lokalisierungsalgorithmen verglichen. Der durchschnittliche Fehler von konventionellen PFs hat einen Bias von 0,5 m bis 1,0 m und das quadratische Mittel der Fehler beträgt mehr als 2,0 m. Für den vorgeschlagene adaptive PF kann der durchschnittliche Fehler gegen 0 gehen und das quadratische Mittel der Fehler beträgt etwa 1,5 m, was den Ansprüchen von Location Based Services genügt. Weiterhin benötigt der adapative PF nur 30 Partikel was den Rechenaufwand signifikant verringert. In Real-World-Experimenten übertrifft die Genauigkeit des adaptiven PF auch die Resultate herkömmlicher Lokalisierungsalgorithmen wie Linear Least Squares, Nonlinear Least Squares, Min-Max-Algorithmus oder den erweiterten Kalman Filter und andere. Der verteilte PF mit selektiven Gossip-Algorithm hat eine garanatierbare Schätzer Genauigkeit. Des Weiteren wir der Kommunikationsaufwand im Vergleich zu anderen verteilten Konsens-Schemata erheblich reduziert.