Dissertation zur Erlangung des Doktorgrades der Technischen Fakultät der Albert-Ludwigs-Universität Freiburg im Breisgau Calibration-Free Localization using Time Differences of Arrival Institut für Informatik Technische Fakultät Albert-Ludwigs-Universität Freiburg Johannes Wendeberg Oktober 2013 Calibration-Free Localization using Time Differences of Arrival Johannes Wendeberg Dissertation zur Erlangung des Doktorgrades der Technischen Fakultät der Albert-Ludwigs-Universität Freiburg im Breisgau Dekan: Prof. Dr. Yiannos Manoli Erstgutachter: Prof. Dr. Christian Schindelhauer (Universität Freiburg) Zweitgutachter: Prof. Dr. Kalle Åström (Universität Lund, Schweden) Datum der Disputation: 14. Oktober 2013 Zusammenfassung (deutsch) Die zunehmende Verbreitung mobiler Technologie im Alltag hat zu einer wachsenden Nachfrage nach Lokalisierungsdiensten bei Handheld-Anwendungen und nach Tech- nologien zur Positionsbestimmung autonomer Systeme geführt. In jüngster Zeit ist eine Verschiebung des Interesses in Richtung Lokalisierung innerhalb von Gebäuden zu beobachten. Desweiteren schafft die zunehmende Verbreitung autonomer intelligen- ter Systeme in Bereichen, die lange Zeit eine Domäne manueller Arbeitsabläufe waren, Nachfrage nach präzisen Ortsinformationen auch im Innenbereich. Globale Naviga- tionssatellitensysteme wie zum Beispiel GPS sind in diesen Szenarien zumeist nicht verfügbar. Alternativen wie WLAN-Lokalisierung konnten sich bisher aufgrund man- gelnderPräzisionnichtdurchsetzen,undoptischeSystemeaufBasisvonLaserscannern oderKamerasystemensindpräzise,aberauchsehrteuer,undumständlicheinzurichten. Dagegen ist die Hardware für Navigation mittels Schall und Ultraschall kostengünstig, und kann präzise Ortsinformation im Bereich von Zentimetern bieten. Lokalisierung mittels Time Differences of Arrival (TDoA) beruht auf der Ausbrei- tungszeit solch eines Signals. Bei herkömmlicher hyperbolischer TDoA-Lokalisierung sinddieReferenzpositionenimVorausbekannt,alsoentwederSenderoderEmpfänger, und die Position eines Ziels ist zu bestimmen. Manuelle Vermessung der Referenzen erreicht man durch ein Maßband, Laser-Distanzmessung, mittels geodätischer Metho- den oder durch externe Infrastruktur, beispielsweise GPS. In einigen Fällen ist ein Ortungssystem wünschenswert, das unabhängig von manueller Installation und exter- nen Systemen ist. Gründe hierfür sind die eingeschränkte Flexibilität eines externen Systems, und erhöhte Kosten und Energieverbrauch durch eine externe Lösung. In der kalibrierungsfreien TDoA-Lokalisierung werden Referenzpositionen direkt während des Lokalisierungsprozesses berechnet, wodurch die quälende Notwendigkeit wegfällt, die Positionen der Referenzen im Voraus zu kennen. In dieser Arbeit stellen wir mehrere neue Ansätze zur kalibrierungsfreien TDoA-Lokalisierung vor. Wir be- trachten das Problem aus mehrerlei Gesichtspunkten, wofür wir Algorithmen in vier Bereichen entwickelt haben – die Fernfeldannahme, lokale Optimierung, Branch-and- Bound-Algorithmen und probabilistische Zustandsschätzung. Die Annahme, dass Signale von weit entfernten Orten stammen, die sogenannte Fernfeldannahme, vereinfacht das Gleichungssystem und ermöglicht schnelle und sta- bile Algorithmen in geschlossener Form. Wir stellen die Ellipsoid-TDoA-Methode vor, die darauf beruht, dass TDoA-Messungen von drei Empfängern in der Ebene eine Ellipse bilden. Die Parameter der Ellipsengleichung lassen sich fehlertolerant durch Regression bestimmen, woraus sich Abstände und Winkel zwischen den Empfängern ableiten lassen. Die Ellipsoid-TDoA-Methode ist der erste Algorithmus, der das mi- nimale Problem in der TDoA-Fernfeldannahme ohne Erfordernis von Synchronisation zwischen Empfängern löst. Wir demonstrieren die Robustheit in Simulation und Ex- perimenten und zeigen, dass die Ellipsenmethode auch dann noch stabil ist, wenn die Fernfeldannahme teilweise verletzt wird. iv Approximative Algorithmen unter der Fernfeldannahme sind in der Allgemeingül- tigkeitbegrenzt,vorallemdann,wenndieZahlderMessungengeringist.Wirbetrach- ten den Bereich der lokalen nichtlinearen Optimierung als Herangehensweise an den allgemeinen Fall der TDoA-Lokalisierung, wobei wir den Fokus auf die Fehlerfälle set- zen. Aufgrund der hohen Dimensionalität der kalibrierungsfreien TDoA-Lokalisierung tendieren iterative Optimierungsalgorithmen dazu, das globale Optimum der Fehler- funktion nicht zu finden, welches die einzige richtige Lösung darstellt. Wir stellen den Cone-Alignment-Algorithmus vor, einen iterativen Algorithmus auf Basis einer Masse- Feder-Simulation, in der Sender- und Empfängerpositionen durch physikalische Parti- kel repräsentiert werden. Eine TDoA-Fehlerfunktion wird durch physikalische Federn zwischendenPartikelnmodelliert.MittelsRelaxierungderFedernwirddieFehlerfunk- tionminimiert,wobeidiePartikelanSchwunggewinnenundsolokaleMinimaüberwin- den. In umfangreichen Simulationen analysieren wir den Algorithmus und vergleichen ihn mit den Standardalgorithmen Gradientenabstieg, dem Gauss-Newton-Verfahren und dem Levenberg-Marquardt-Algorithmus. Wir zeigen, dass der Cone-Alignment- Algorithmus die richtige Lösung häufiger findet als die Standardalgorithmen. Um das Problem der Vollständigkeit in der Optimierung zu lösen, stellen wir einen Branch-and-Bound-AlgorithmusinPolynomialzeitvor,derbeweisbaralleLösungenfür kalibrierungsfreie TDoA-Probleme bis zu einer Fehlerschranke (cid:15) approximiert. Der Al- gorithmus basiert auf der Unterteilung eines fünfdimensionalen Suchraumes, mit dem der Minimalfall von vier Empfängern in der Ebene dargestellt wird, in Teilräume, und Prüfung jedes einzelnen Teilraums darauf, ob er eine mögliche Erklärung der TDoA- Messungen mit Unsicherheit (cid:15) darstellt. In der praktischen Umsetzung zeigen wir, dass der Algorithmus asymptotisch schneller als die Aufzählung aller Zellen der Größe (cid:15) ist. Der Branch-and-Bound-Algorithmus ist unseres Wissens die erste theoretische Lösung des allgemeinen Minimalfalls der TDoA-Selbstlokalisierung. Wir präsentieren außerdem das kalibrierungsfreie Ultraschall-Ortungssystem, das im Rahmen dieser Dissertation entwickelt wurde. In dem System emittiert ein mobi- ler Ultraschallsender kurze diskrete Impulse, die von mehreren Ultraschallempfängern empfangen werden, wodurch der Sender lokalisiert wird. Die Lokalisierung im System ist kalibrierungsfrei, wofür wir einen Algorithmus zur probabilistischen Zustandsschät- zung entwickelt haben. Dieser basiert auf einem Partikelfilter, der sowohl den mobilen Sender, als auch die Positionen der Empfänger schätzt. Der Algorithmus verwendet ein probabilistisches Sensormodell für TDoA-Daten, das explizit die Messunsicherheit berücksichtigt, wodurch er robust gegen Mess-Ausreißer wird, welche eine typische Ge- fahr in der TDoA-Lokalisierung darstellen. Wir haben die Robustheit des Ultraschall- Ortungssystems in umfangreichen Experimenten überprüft, wo wir zeigen, dass der probabilistische Ansatz genaue Positionsschätzungen für den Sender und die Empfän- gerselbstbeiMess-Ausreißerngewährleistet,wobeidasSystemmittlerePositionsfehler von unter 5 Zentimetern erreicht. v Abstract The continuous rise of mobile technology in everyday life has led to an increasing de- mand for location-based services for handheld applications and autonomous systems. In recent time, a shift of interest towards indoor localization can be observed where global navigation satellite systems, such as the Global Positioning System, are mostly not available. The hardware for positioning and navigation based on sound or ultra- sound is affordable and precise in the range of centimeters. Localization based on the time differences of arrival (TDoA) relies on the propagation time of such a signal. In conventional hyperbolic TDoA localization the reference positions, i.e. the positions of either receivers or senders of a signal, are known a priori, and the position of a target is subject to locate. In calibration-free TDoA localization, reference positions are calculated during the process of locating the target – or just the references are calculated from unknown signals,eliminatingtheagonizingneedtodeterminethepositionsofreferencesbyhand. In this thesis, we propose several novel approaches to the domain of calibration-free TDoA localization. Addressing the problem from several points of view, we propose algorithms in four fields – the far-field assumption, local optimization, branch-and- bound algorithms, and probabilistic state estimation. The assumption that signals originate from remote locations, the so-called far-field assumption, simplifies the equation system and allows for fast and robust closed-form algorithms. We propose the Ellipsoid TDoA method, which relies on the fact that TDoA measurements from three receivers in the plane form an ellipse. This ellipse is robustly determined by regression, and the distances and angles between the receivers are calculated from the parameters of the ellipse. The Ellipsoid TDoA method is the first algorithm that solves the minimum problem of the TDoA far-field assumption, requiring no synchronization between receivers. We demonstrate the robustness of the algorithm in simulation and in experiments, where we show that the Ellipsoid method is still reliable when the far-field assumption is violated to some extent. Far-fieldalgorithmsarelimitedingenerality,especiallywhenmeasurementsarerare. We consider the field of non-linear local optimization where we set focus to the failure cases. Due to the high dimensionality of the calibration-free TDoA problem, iterative optimization tends to not find the global optimum, which is the only acceptable solu- tion. We propose the Cone Alignment algorithm, an iterative mass-spring simulation where signal and receiver positions are represented by physical particles which gather momentum to overcome local minima. In numerical simulations we compare the algo- rithm to standard optimization approaches, where we demonstrate the superiority of Cone Alignment in finding the solution. To address this intrinsic problem of local optimization, also denoted as the problem of completeness, we propose a polynomial time branch-and-bound algorithm that is a proof to enumerate all solutions of calibration-free TDoA up to an error bound (cid:15). The algorithm is based on subdivision of a five-dimensional search space into subspaces, by vi which the minimum problem of four receivers in the plane is represented, and test of each subspace for being a possible explanation of the observed TDoA measurements, given uncertainty (cid:15). In practical implementation we demonstrate that the algorithm is asymptotically faster than enumerating all cells of size (cid:15), which is the brute-force approach. The branch-and-bound algorithm is to our knowledge the first theoretical solution to the general minimum case of calibration-free TDoA. Furthermore, wepresentthecalibration-freeultrasoundlocalizationsystem, wherea mobileultrasoundsenderislocatedbyemittingshortpulsesthatarereceivedbyseveral ultrasound receivers. We have created a probabilistic state estimation algorithm based on aparticlefilter thatestimates both themobile senderand thepositions ofreceivers. The algorithm is robust against measurement outliers, which is a common pitfall in TDoA localization. We have verified the robustness of the ultrasound localization system in extensive experiments, where we demonstrate that our approach provides accuratepositionestimateswitherrorsbelow5cmevenincaseofmeasurementoutliers of large magnitude. vii Acknowledgments First of all, I wish to thank my supervisor Christian Schindelhauer who gave me the opportunity to do my doctorate at his chair. He was a great advisor, and he granted me a large degree of freedom, while he guided me in scientific methodology and taught me to question scientific conventions with academic rigor. Both, our shared opinions about scientific research and our opposing points of view were a great inspiration for my work. I would like to thank my cooperation partners who have a large share to the achievements in this thesis. Particularly, my gratitude goes to Fabian Höflinger, who developedtheexceptionalhardwareoftheultrasoundlocalizationsystem. Also, Iwish to thank the fellows and students who helped in creation of the system and in our ex- periments, especially Manuel Bührer, Joachim Hoppe, and Thomas Janson who pro- vided valuable assistance in software and hardware development. I would like to thank Jörg Müller for the fruitful collaboration with the probabilistic algorithm, and Simon Burgess for the inspiring teamwork in the TDoA far-field assumption. My special thanksgo tomyco-authors KalleÅström, Amir Bannoura, Joan Bordoy, Wolfram Burgard, Simon Burgess, Manuel Bührer, Thomas Janson, Joachim Hoppe, Patrick Hornecker, Fabian Höflinger, Yubin Kuang, Zvi Lotker, Jörg Müller, Leonhard Reindl,ChristianSchindelhauer,andRuiZhangforthecriticaldiscussionandvaluable help in scientific writing. I wish to thank the members of the Research Training Group for fascinating discussions and workshops, and Manuela Kniß, Norbert Küchlin, and Kerstin Pfeiffer for help in administrative matters. My thanks go to Thomas Janson, Christian Ortolf, and Arne Vater for razor-sharp discussions, but also for being great workmates, and for the support and pleasurable environment. Ialsothankthefellowswhohelpedtoproof-readthisthesis. Last, Iwish to thank my family for their unconditional support and encouragement in all stages of my life. This work has partly been supported by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) within the Research Training Group 1103 (Embedded Microsystems). Contents 1 Introduction 1 1.1 Multilateration based on the Runtime of Signals . . . . . . . . . . . . . 1 1.2 Calibration-Free TDoA . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Applications of Calibration-Free TDoA . . . . . . . . . . . . . . . . . . . 6 1.5 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.6 Collaborations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.7 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.8 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Gaining Insight into TDoA 13 2.1 The Calibration-Free TDoA Problem . . . . . . . . . . . . . . . . . . . . 13 2.2 Hyperbolic Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Combinatorial Problem of Timestamp Association . . . . . . . . . . . . 15 2.4 The Minimum Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5 Estimation of the Convex Hull . . . . . . . . . . . . . . . . . . . . . . . 20 2.6 Evaluation of Anchor-Free TDoA . . . . . . . . . . . . . . . . . . . . . . 22 2.7 The Velocity of Sound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.7.1 Sound Velocity in Air . . . . . . . . . . . . . . . . . . . . . . . . 23 2.7.2 Sound Propagation in a Temperature Gradient . . . . . . . . . . 24 3 Far-Field Approximation 27 3.1 Min/Max Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Statistical Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.1 Variance Estimator . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.2 Arc Cosine Estimator . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 The Ellipsoid TDoA Method . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.1 The Receiver Triangle . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3.2 Solving the Equation System . . . . . . . . . . . . . . . . . . . . 35 3.3.3 Unsynchronized Receivers . . . . . . . . . . . . . . . . . . . . . . 35 3.3.4 A Solution in Three Dimensions . . . . . . . . . . . . . . . . . . 36 3.3.5 Covariance Representation. . . . . . . . . . . . . . . . . . . . . . 37 3.3.6 Transformation of the Covariance Matrix . . . . . . . . . . . . . 40 3.3.7 Issues of Regression . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3.8 Numerical Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3.9 Real-World Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 44 ix 3.4 Coordinates From Distances . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.4.1 Classical Multidimensional Scaling . . . . . . . . . . . . . . . . . 45 3.4.2 Iterative Construction . . . . . . . . . . . . . . . . . . . . . . . . 46 3.4.3 Bipartite Distance Graphs . . . . . . . . . . . . . . . . . . . . . . 47 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4 Local Optimization 49 4.1 First-Order Gradient Methods . . . . . . . . . . . . . . . . . . . . . . . 49 4.1.1 The Gradient Descent Method . . . . . . . . . . . . . . . . . . . 49 4.1.2 The Gauss-Newton Algorithm . . . . . . . . . . . . . . . . . . . . 51 4.2 Iterative Cone Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2.1 Error Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2.2 Mass-Spring Simulation . . . . . . . . . . . . . . . . . . . . . . . 54 4.3 Numerical Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.3.1 Local Minima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3.2 The Scilab lsqrsolve Function . . . . . . . . . . . . . . . . . . . 59 4.3.3 Minimum Case: Four Receivers . . . . . . . . . . . . . . . . . . . 63 4.3.4 Towards a 100 Percent Solution . . . . . . . . . . . . . . . . . . . 64 4.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.5 Global Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5 A Branch-and-Bound Algorithm 68 5.1 Existence of a Solution in TDoA . . . . . . . . . . . . . . . . . . . . . . 68 5.2 The Error Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.3 A Test of Feasibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.4 Recursive Grid Refinement . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.5 Numerical Evaluation of Four Receivers . . . . . . . . . . . . . . . . . . 75 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6 Probabilistic TDoA Localization 79 6.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.2 Robust State Estimation in the Particle Filter . . . . . . . . . . . . . . . 80 6.2.1 Calculation of the Particle Filter Estimate . . . . . . . . . . . . . 82 6.2.2 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.2.3 Motion Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.2.4 Sensor Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.3 Parameter Estimation of the Particle Filter . . . . . . . . . . . . . . . . 88 6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7 Real-World Experiments 92 7.1 The Localization Framework . . . . . . . . . . . . . . . . . . . . . . . . 92 7.2 Acoustic Self-Localization . . . . . . . . . . . . . . . . . . . . . . . . . . 96 x