Microsoft Research Blog

Microsoft Research Blog

The Microsoft Research blog provides in-depth views and perspectives from our researchers, scientists and engineers, plus information about noteworthy events and conferences, scholarships, and fellowships designed for academic and scientific communities.

Path Guide: A New Approach to Indoor Navigation

July 14, 2017 | Posted by Microsoft Research Blog

Montreal’s Underground City. Photo by Tourisme Montréal.

By Yuanchao Shu, Associate Researcher, and Börje Karlsson, Sr. Research Dev Lead, Microsoft Research

Mobile outdoor GPS navigation apps have proven to be lifesavers to countless people. With a smartphone in hand, it is easy to find your way to a destination, even in an unfamiliar city. However, it is still easy to get lost indoors, where GPS satellite signals are not accurately traceable for navigation applications.

How often have you had a hard time locating that new café inside in a bustling shopping center where you were supposed to meet your friends? How often have you wandered the hallways of some office building trying desperately to find that meeting room you were supposed to be in? How convenient would it be to have an app, similar to the ones used outdoors, that works indoors? We at Microsoft Research Asia’s Cloud & Mobile Research group recently launched Path Guide, a research-based application that provides low-cost, plug-and-play indoor navigation services. Users can easily find the correct path to their destinations by simply following traces created by a “leader,” or user who has been to the location before.

Microsoft Path Guide app for Android devices.

Indoor Navigation Anywhere: Is It Beyond Reach?

Let’s start by examining why GPS cannot be relied upon for indoor navigation. The first step in GPS navigation is positioning. Essentially, the receiver chip of the GPS system running on a handheld device picks up positioning signals from satellites and calculates the coordinates of the receiving device. Signals from a GPS satellite have poor penetration and are often blocked by building walls. Moreover, even with accurate positioning results, map information that most navigation applications depend on is not widely available for indoor scenarios. Real-time GPS-based indoor navigation is therefore out of the question.

So, what are the current applicable ideas for indoor navigation? A relatively well-known navigation approach is based on Bluetooth beacon positioning. Taking Apple’s iBeacon as an example, a smartphone app can roughly work out the device’s location on a map via signals from one or more iBeacons. Based on this information, the app then can calculate a route and navigate the user to her destination. However, this solution only works in buildings where iBeacons exist and the limited Bluetooth transmission range results in high costs for deployment and maintenance in large-sized indoor environments (shopping malls and office buildings, for instance).

Another popular indoor navigation approach is built upon Wi-Fi-based positioning. Wi-Fi signals are more commonly found in indoor environments than Bluetooth beacons. Similar to the Bluetooth method, this type of solution determines the approximate position of mobile devices through radio frequency (RF) signal characteristics and triangulation processes. Different positioning systems rely on signal strength, signal phase, transmission time, RF angle of arrival, channel state information, etc., but in general, they all leverage the differences and correlations between various Wi-Fi signals to determine  positioning.

These systems can also use signal propagation models and learning algorithms to build a fingerprint map of indoor areas, and then train the system with, let’s say, radio signal strength information for positioning. However, due to the complexity of indoor environments, Wi-Fi signals are easily affected by interference and can fluctuate widely. Keeping Wi-Fi signal data up to date can lead to high maintenance costs. Additionally, positioning accuracy is limited by other factors such as the deployment density of Wi-Fi routers, how often the indoor environment changes, and the effort required to train and calibrate the system.

There are also solutions based on dedicated equipment within various indoor locations, which require the deployment of a certain number of special-purpose sensing devices, including cameras, visible light communication systems, RFID, Ultra-Wideband (UWB), infrared, ultrasound, or even laser-based instruments gears.  These solutions can greatly improve system accuracy, but widespread deployments are heavily constrained by high hardware and labor costs.

Finally,  indoor navigation generally relies on indoor maps, but map collection, data representation and data manipulation in large-sized indoor spaces are outstanding and costly issues, placing a huge question mark over the universal application of indoor navigation technologies. And for smaller buildings, owners may not have the means to collect and expose the necessary data.

So, how can we achieve low-cost, plug-and-play, scalable indoor navigation?

Path Guide: A Flexible Solution to Indoor Navigation

Taking the above knowledge into account, we turned our eyes to the smartphones that everyone uses.  Could we rely only on what’s already available there?

After generations of upgrades, mobile phones today have an increasing variety of sensors, such as accelerometers, gyroscopes, electronic compasses, barometers, etc. Based on our previous research on making the most of such smartphone sensors and in using sensor data for indoor navigation, we decided to switch approaches. Instead of doing positioning first, why not focus only on navigation, as that’s our goal? Experiments have determined that the indoor geomagnetic field is disturbed by building structures, and that it is relatively stable inside buildings. This gave us the idea of creating an indoor navigation system based on the magnetic sensor data gathered from different locations, while leveraging the other phone sensors to support real time navigation instructions.

Combining the teams’ knowledge and expertise in mobile computing, pervasive computing, and intelligent sensing, we developed Path Guide. The Path Guide Android-based mobile app is user-friendly and can be installed directly onto a user’s smartphone, without the need for indoor maps or for building to have any special pre-installed hardware (including Wi-Fi routers).

To make the system work for anyone, we developed a peer-to-peer leader/follower model. Once a user goes to an indoor location using the app to record sensor data along a path, any other user can follow that path and get there. As more users collect data, different paths can be combined that make the system even more useful. This approach has two main benefits: First, the system is completely plug-and-play. Any two users in any building can use indoor navigation from scratch. Second, by combining data from multiple users, we can amplify the benefits of every single collected path, providing more navigation opportunities to more people with improved user experience.
The Path Guide app can be used in many scenarios. For example, if you are going to a large office building for the first time to attend a client meeting, a colleague who knows where the meeting room is can act as a “guide leader” and, using Path Guide, record a trace from the entrance of the building to the meeting room.

After arriving at the meeting room, the “leader” clicks the “finish recording” button to upload the path data trace to Path Guide’s backend in the cloud. Anyone who subsequently enters the building for the meeting and is using Path Guide can then follow the shared trace step-by-step to easily locate the correct room.

In more open areas, like shopping malls, any person or even shop owners can act as “guide leader” and share path traces from multiple locations (e.g., different entrances) to get to a certain destination, such as a relatively hidden restaurant or a clothing store.

Users of Path Guide can also record a trace and follow it backwards to its starting point. For instance, in an unfamiliar garage, you can record a trace from your parking spot to the elevator, and later follow it in reverse to find your car.

Another Path Guide feature is its support of annotations during trace recording. Text, audio, and photos can be added along a path, providing more information and interactivity.

Moreover, all traces that are uploaded to the cloud can be viewed from a web browser and shared with others using a unique trace ID. This way, shop owners can post wayfinding instructions on their own websites, and meeting coordinators can attach a route to an email meeting request.

Path Guide is a research project and admittedly still has rough edges. We hope you’ll download the app. Any feedback on improvements to the app UI, its usability, or in dealing with problematic situations are greatly welcome by the research team. You can either search for Path Guide in Google Play or download it directly from the project’s official website.

Related