Multimodal Localisation: Analysis, Algorithms and Experimental Evaluation

The term localisation is derived from the word locale, which traditionally means a small area or vicinity. In ancient days, localisation meant navigation -- an art of finding the way from one place to another. Tremendous advancement in the science of navigation dates back to the sixteenth century, when instruments like compasses, sextants and the first ever clock to keep the time exactly were devised. Advancement in navigation brought ways and means to explore the world, be it for expansion of the territories or for promoting trade and business. Since then localisation has been explored for several decades as a classical problem in many disciplines -- including robotics, virtual reality, navigation. Now we are in the era of ubiquitous computing -- a term coined by the visionary Mark Weiser in the early 1990s. Weiser sees technology only as a means to an end, which should take a back seat in order to allow user to fully concentrate on the task at hand. Looking from a technological standpoint, today we are surrounded by a wealth of devices enriched with sensing, computing and communication capabilities which are seamlessly integrated in our daily lives. Knowing the location of an object is an important cornerstone and fertile research area in ubiquitous computing. The growing need of location systems underscores the importance of addressing this problem -- government initiatives to locate emergency call by cellular network providers and the increasing usage of global positioning systems (GPS) in many commercial applications as in navigation are just a few examples. Since the field is active and vibrant, new services and market players are constantly emerging. Google have just launched a new service called Latitude, which lets smart phone and laptop users share their location with friends and allows those friends to share their locations in return. Latitude uses satellites and cell towers to estimate location. The market for GPS products and services alone is expected to grow to USD200 billion by 2015. Real-time location systems (RTLS) in the transport and logistics sector drive the penetration of several location-based solutions. The number of RTLS suppliers is expected to increase from 50 to 200 by 2013, reflecting a market growth from USD 145 million in 2008 to USD 2.7 billion in 2013. Despite the extraordinary advances in outdoor localisation and navigation, indoor localisation still remains an open challenge. Fundamental to any location system are the algorithms used to estimate location. This thesis focuses on formulation of localisation algorithms with the capability of fusing measurements from multiple modalities. We begin by systematically analysing the basic principles of localisation through a review and classification of the state of the art. From our detailed survey, it is evident that no location system is error-free and suited for all situations. For example, pure inertial sensors suffer from drift, ultrasound sensors require clear line of sight and magnetic sensors are affected by ferromagnetic and conductive materials in the environment. Thus, we rationalise "multimodal localisation" as one of the promising ways for improving location accuracy. Apart from improving performance of the location system in limited measurement volumes, fusion of heterogeneous sensing systems will ultimately allow people to move between places covered by different sensing systems without loss of location knowledge. We explore localisation algorithms that use multiple sensing modalities to improve accuracy and robustness. To ground our work, we have chosen three specific applications covering both infrastructure-based positioning and ad hoc-based positioning systems. From our taxonomy, we create a blueprint of location technologies that would meet those three application needs. -Localisation in office environments to facilitate social networking, as a way to help coordination of people and understand social patterns. We leverage the existing wireless local-area networks (WLAN) infrastructure to sense motion and location with the main motivation of building wide-area location services. Our contributions include-- (i) in-depth characterisation of received signal strength (RSSI), (ii) novel algorithms to deduce motion by observing fluctuations in RSSI across all the access points in range, and (iii) performance comparison using real data against common deterministic location algorithms with and without adding motion information. -Transport and logistics operation (e.g. in warehouses), motivating the need of fine-grained location information. We use ultra-wideband (UWB) as it copes with harsh indoor environments better than conventional radio technologies. Our contributions include-- (i) characterisation of heterogeneous observations (pseudoranges and angles) obtained from two deployments, mimicking real-world (low-overhead) vs. ideal deployment (carefully planned and calibrated), (ii) formulation of algorithms to fuse heterogeneous observations and (iii) a thorough evaluation for both static and dynamic tracking. -Emergency response scenarios, motivating the need for ad hoc positioning capabilities. In particular, we use a combination of inertial sensors and ultrasound sensors. The position error in a purely inertial system increases with time and requires correction from external sources. We address this problem by deploying ultrasound sensors as landmarks correcting for the inertial drift. Our contributions include-- (i) characterisation of inertial and ultrasound data, (ii) algorithms to support guidance and tracking and (iii) a thorough evaluation from data gathered from real deployments. While the chosen technologies and applications are not exhaustive, they are representative as they cover a broad spectrum across several dimensions: accuracy -- fine grained to coarse grained, coverage -- room-level to wide-area, dependence -- dense infrastructure to ad hoc, cost -- expensive to minimal cost. In every instance, we have illustrated the benefits of combining multiple modalities. In short, our contributions include algorithms for motion detection and technology independent localisation algorithms that have the ability to fuse readings across different sensing technologies and incorporate motion models to improve accuracy significantly. Another important aspect of the work presented in this thesis is the characterisation of the raw measurement errors of the individual modalities. In all cases, we perform a rigorous evaluation of the presented algorithms by using measurements collected from real deployments