Real-Time, Continuous, Reliable, Indoor/Outdoor Localization
By Zainab Syed, Jacques Georgy, Abdelrahman Ali, Hsiu-Wen Chang, and Chris Goodall
Using a select set of components, a navigation software development kit can easily be configured to fit a variety of mobile and portable devices. Testing on several current devices demonstrates that the kit’s use of sensors already present in smartphones to enable entertainment can provide 3D positioning when satellite signals are degraded or absent, such as in urban canyons or in deep indoor environments. The solution also provides the heading of the user, the 3D orientation of the device, and the user’s velocity, without restriction on device usage.
Location-based services (LBS) have evolved to the point that a smartphone is considered incomplete if it does not have navigation functionality. In fact, basic navigation functionalities are no longer sufficient, because of the limited capabilities of traditional solutions. Traditional navigation techniques are usually based on the trilateration of GPS signals. Smartphones use Assisted GPS (AGPS) technology, which utilizes pre-knowledge about the satellite constellation to provide GPS-based positions in urban canyons and indoor environments, a capability once considered impossible. Because GPS signals cannot reach indoor environments, some companies have developed map databases to provide a positioning solution using available Wi-Fi signals. The concept is simple: to provide absolute positioning where GPS signals are too weak or are unavailable. However, such a solution requires continuous updates of ever-changing Wi-Fi hotspot maps, making this a costly system to manage. Nevertheless, it is an attractive option for positioning in the absence of GPS signals.
Because LBS demand reliability, continuity, and accuracy in all environments, as well as information about the headings of the device and user, many research groups and technology companies are working to achieve these goals by integrating the aforementioned positioning methods with pre-existing sensors in smartphones. Currently, micro-electro-mechanical systems (MEMS) sensors are used predominantly for entertainment applications in the phone. The orientation of the screen is sensed by the MEMS accelerometers, which switch the display orientation according to the user’s needs. Some applications use the accelerometers and magnetometer to provide an indoor navigation solution starting from a user-defined position, but only if the smartphone is kept in a fixed orientation — an unrealistic assumption. Other recent research works also include gyroscopes for navigation. In general, it has been found that embedded mobile-phone sensors are insufficient for reliable navigation purposes because of very high noise, large random drift rates, and also because it can be assumed that the mobile device is able to freely change orientation with respect to the moving platform (the human body while walking, or a vehicle while driving).
This article provides the results of using an efficient and high-rate navigation platform with low computational requirements for mobile devices. Known as the Trusted Portable Navigator (T-PN), it utilizes a smartphone’s existing MEMS sensors. Despite some of the challenges with MEMS, the T-PN can provide a real-time, continuous, and reliable navigation solution that works regardless of the motion pattern of the user. Example motion patterns include walking with the smartphone indoors or outdoors; driving in clear sky conditions, downtown, or through tunnels and underground parkades; or a combination of walking and driving in any environment.
The main challenge with low-cost MEMS sensors in smartphones is that they cannot be used without proper error modeling because of high noise characteristics and bias instabilities. Thus, the T-PN has innovative algorithms that autonomously develop custom error models, turning the available sensors into navigation-capable inertial sensors, without any restrictions on the user or any delay in the navigation solution.
Current consumer mobile devices can be used in a variety of ways; for example, while texting, on the ear, in pocket, dangling freely while handheld, and on a belt. The orientation of the phone changes significantly with each use case, which makes accurate sensor-based navigation very difficult to achieve if referenced to the user. The common practice in traditional inertial navigation is to attach and align the device to the moving body. However, it is unrealistic to ask a user to keep their phone in any specific orientation. To solve this problem, the T-PN calculates these orientation angles in real-time and uses them as corrections for the user’s attitude and position.
The ultimate demonstration of the T-PN’s capabilities is its real-time performance in smartphones and tablets. The tests described here were performed on the commercially-available Android and QNX operating systems in tablets and smartphones. The T-PN was packaged and built at the native level to ensure computational efficiency. Several devices were used in the real time testing, including: the Samsung Galaxy Nexus, the Samsung Galaxy Note, the Samsung Galaxy S III, and the Blackberry Playbook. This device selection is an accurate sampling of the current mobile technologies available today.
Other manufacturers will have more of these devices running newer versions of Android and other operating systems. All of these devices include tri-axial gyroscopes, tri-axial accelerometers, tri-axial magnetometers, a barometer, and a GPS chipset with AGPS capabilities. All the devices used feature different brands of these low-cost sensors.
The sensors need to be calibrated for two different types of errors to ensure a precise and accurate navigation solution. The first type of calibration is known as deterministic errors calibration, which includes the estimation of initial turn-on biases and scale factors of the sensors. For very high-cost systems these errors are usually negligible, but mobile phone-grade sensors show high variations from turn-on to turn-on.
The second type of calibration is more involved and labor-intensive, as it requires large static datasets. Allan variance curves are calculated to estimate the bias instability and random walk parameters. These parameters are called stochastic error model parameters and are necessary to obtain optimum results for longer periods of standalone navigation. They are also very important when attempting to design a consistent filter. For very low-cost sensors, these parameters may change from unit to sensor, and over time for the same sensor. This means that individual systems may demonstrate different performances with the exact same integration software.
The T-PN eliminates the need of any calibration, as it uses a patent-pending technique that automatically completes all the required calibration within 5–10 minutes of the navigation mission. The only requirement is the availability of a good GPS position, velocity, and timing (PVT) solution for at least 5–10 minutes. Starting from generic calibration parameters, artificial intelligence techniques quickly narrow down the search to the most optimum error-model parameters. This makes the T-PN suitable for navigation use with mobile phone-grade inertial sensors.
Changing orientations cannot be avoided for smartphone-based navigation. While navigating, users will take calls, text, and check their position; therefore it is impractical to request that the user keep the phone fixed to their body. The solution must be robust to provide navigation for these common use-case scenarios.
The T-PN uses patent-pending techniques to identify the changing orientations as they occur and adjust the user’s navigation solution accordingly. The result is a seamless and robust solution, with or without GPS.
Mode of Transit
Mobile phone navigation cannot be restricted to pedestrian-only or vehicle-only cases. The user will be carrying the device wherever they will go, which requires the navigation software to be adaptable for the user’s mode of transit.
Through a patent-pending technology, the user’s mode of transit is detected. Different modes may include walking, using the stairs, driving, riding an elevator, and static periods related to the above modes. Once the mode is detected, the appropriate algorithms and constraints are applied to ensure minimal navigation drift, even for long periods of standalone sensor navigation. There is no restriction on modes of transit or any requirement to perform a special task, making the T-PN user-friendly and efficient.
The T-PN is highly customizable software that converts any quality and grade of inertial sensors into a navigation-capable system. In other words, it can be used on any available smartphone operating system, such as Android. This navigation engine takes any available measurements and improves the navigation results by filtering the updates. GPS is the most common type of external update that provides absolute position and velocity information to the inertial engine and reduces time-related errors.
Wi-Fi is another absolute update for positioning in deep indoor scenarios, and is also accepted by the T-PN. Wi-Fi measurements are noisy, but the T-PN integrated solution smooths the noise and closely represents the user’s actual position. Wi-Fi updates are optional for T-PN, but they will enhance the solution if long periods of indoor navigation are desired.
Physical movements of the user, such as pedestrian dead reckoning, zero-velocity updates, and non-holonomic conditions are used as constraints to improve the navigation solution.
The constraints are also tailored to the user’s mode of transit to ensure the most robust solution for the user. Mode of transit is automatically detected on a continuous basis.
If additional sensors such as magnetometers and barometers are present and properly calibrated by the T-PN software, their readings can be used as optional updates. Figure 1 shows a complete flowchart of the algorithm for the T-PN. The dashed lines show the optional updates for the T-PN.
Hardware Description and Use Cases
The test platforms used are smartphones and tablets running different versions of Android and QNX. The opening picture shows some of these units, listed here with their operating systems.
- MOTOROLA Xoom Wi-Fi MZ604 – Android 3.2
- SAMSUNG Galaxy Nexus GT-I9250 – Android 4.0
- SAMSUNG Galaxy Note GT-N7000 – Android 2.3
- Blackberry 16GB Playbook – QNX 220.127.116.118 (pictured)
- SAMSUNG Galaxy S III – Android 4.0.4 (pictured)
A variety of use cases, listed in Table 1, are currently supported in the T-PN.
The results are divided into three sections:
- the results for consumer navigation and their respective LBS applications;
- tracking applications for personnel on-foot and in-vehicle;
- and driving with or without GPS with the device left on the seat or holder with or without a connection to the on-board diagnostic system (OBDII) of the vehicle.
Consumer Navigation, LBS App. This is a very typical use case. It involves the user starting the navigation after parking his/her vehicle to locate a certain destination in an indoor environment; for example, a specific store in a shopping center or an office inside a building. As the user heads deep indoors, GPS will stop providing any useful positioning information, as illustrated in Figure 2 (blue line). The user started the navigation in texting portrait mode, then held the phone in hand for some time and let it dangle naturally, and then finally puts the phone in his or her pocket. The trajectory in red is the T-PN solution and the blue line shows the available GPS solution. The Samsung Galaxy S III was used in this trajectory, with a maximum error of less than 7 meters for 2 minutes of deep indoor navigation.
Figure 3 shows a trajectory collected and processed on an S III with GPS signals (including multipath) in blue provided with the T-PN solution in red. During the navigation, the user was making a phone call with the phone on the ear. The maximum error stayed within 17 meters for 5 minutes of indoor navigation with severe multipath in GPS signals. It has to be noted that the heading solution would have converged better if the user walked outdoor for an adequate time, but here the user went straight indoors a few seconds after starting.
The trajectory in Figure 4 was collected and processed on a Samsung Galaxy Note. The user was holding the Note in texting portrait mode in Shanghai’s downtown core. When the user entered the building, GPS positioning information became unavailable, and the only positioning information available was from T-PN (as shown by the red line in Figure 4). The maximum error after approximately 2 minutes of indoor trajectory was less than 6m.
Figure 5 shows a pure indoor trajectory without GPS, collected and processed on a Samsung Galaxy Nexus. The user walked in a loop for 4 minutes and then returned back to the same location. The maximum error stayed within 13 meters, even with the phone changing orientation with respect to the user. This trajectory was collected at Computex 2012 conference in Taipei.
Tracking Applications. Another usage of T-PN can be related to tracking of personnel such as firefighters. In this case, the tracking device will be attached to the users for a high-accuracy solution. To show the performance, a Samsung Galaxy Nexus was tethered to the user in a chest mount strap. The user took a trajectory that started outdoors and then went indoors for over 9 minutes, covering multiple floors and taking elevators and stairs to access the different floors. At the end of the trajectory, the error was less than 6 meters, or 1.5 percent of the distance traveled. Figure 6 shows the results, with the red line showing the T-PN solution and the blue line showing the GPS solution.
Figure 7 shows the result of the tethered chest-mount system that was connected wirelessly with a vehicle’s OBDII while inside that vehicle. The vehicle entered an underground parkade with no GPS availability and completed two full loops inside the parkade before exiting.
Consumer Vehicle Navigation. The results of using the T-PN platform on a Blackberry Playbook in real time in the downtown Toronto Eaton Centre parkade appear in Figure 8. The Playbook was left untethered on a seat during the navigation. The T-PN was able to bridge the complete loss of GPS signals (blue line) in the multi-level parkade, and to effectively filter the multipath in the GPS signals in the Toronto downtown core.
The next set of results are for a changing misalignment case within the trajectory. In this case, T-PN was running on a Samsung Galaxy S III and evaluated in Calgary’s downtown core. The GPS signals were erroneous due to multipath (as shown by the blue lines in Figure 9), while the T-PN solution was able to provide a proper trajectory, including an almost perfect figure-eight.
For the final sets of results, a Samsung Galaxy S III was placed (untethered) on a seat in a vehicle with a wireless connection to the vehicle’s OBDII. Despite the misalignment, the T-PN showed the three loops in the parkade almost perfectly, as shown in Figure 10.
Today, mobile phones are used as navigation devices. GPS often fails to provide an accurate positioning solution in urban canyons and deep indoor environments because GPS is either not available in these environments or will provide erroneous positions because of multipath.
The T-PN provides accurate positioning everywhere by converting the pre-existing inertial sensors of mobile devices (such as tablets and smartphones) into navigators. The results were provided for walking and driving cases where GPS positioning information was unreliable or unavailable. In all these cases, the T-PN solution was able to successfully provide enhanced navigation solution of the user.
This article is based on a paper first presented at ION GNSS 2012, September 2012, Nashville, Tennessee.
The T-PN was developed by Trusted Positioning, Inc., of Calgary, Alberta, Canada.
Zainab Syed is a co-founder/VP engineering at Trusted Positioning Inc. She obtained her Ph.D. from the University of Calgary. She has 6 patents pending and more than 50 publications on integrated navigation systems.
Jacques Georgy is the VP of R&D and a co-founder of Trusted Positioning Inc. He received his Ph.D. in electrical and computer engineering from Queen’s University, Canada. He has 10 filed patents, written a book, and more than 40 papers.
Abdelrahman Ali is an algorithms designer at Trusted Positioning Inc. He is also a member of the Mobile Multi-Sensor Systems Research Group at the Department of Geomatics Engineering in University of Calgary where he is completing his Ph.D.
Hsiu-Wen Chang is an algorithms designer at Trusted Positioning Inc. She is also a member of the Mobile Multi-Sensor Systems Research Group at the Department of Geomatics Engineering in University of Calgary where she is completing her Ph.D.
Chris Goodall is the CEO/co-founder of Trusted Positioning Inc. Chris has been working in developing, deploying, and evangelizing multi-sensor navigation systems for more than 8 years. He has more than 40 publications and seven patent applications.