Indoor Positioning – Getting There

It is hard to imagine anyone not knowing what GPS is these days (as an aside GPS, is the US Global Positioning System, which is a subset of the overarching Global Navigation Satellite System, GNSS) – over the past 20 years or so it has become part of our everyday life. GPS receivers are now included in most Smart Phones, Smart Tablets, consumer cameras, many vehicles, etc. Furthermore, because of this ubiquitous technology it is difficult to get lost in most of the world – when your GPS receiver can “see” a few satellites you (or rather your smart device) will be able to determine your position on the globe with fantastic accuracy. Even when you do not have a good view of the sky (e.g., you are in an “urban canyon” surrounded by view-blocking skyscrapers), in many cases other technologies will be able to compensate – because your smart device usually includes additional sensors (like accelerometers, electronic compasses, gyroscopes) that enable things like dead reckoning. Oh yeah, let us not forget that your smart phone, at least, can also determine location based on signals coming from a number of cellular base stations (but usually not with the same accuracy as GPS).

So this is great when you are outdoors, but the minute you walk into a large building, mall, hospital, etc., your GPS receiver becomes useless. I don’t know about you, but getting lost in a large mall is not an unusual scenario. Indoor navigation (for humans and robots) is an obvious use case, but there are others, such as –

  • Highly accurate positioning – less than 1 meter accuracy. This enables, for example, a retailer to know exactly in front of which item her customer is standing; knowing exactly where a specific, tagged asset is in a large warehouse.
  • Positioning in 3D – knowing whether you are standing or in distress and lying on the floor.
  • Tracking – for example, in shopping centers it may be of interest to understand what paths people take as they explore the place; in times of emergency it could be important to know where people are and where they are heading.

There are already quite a few solutions that assume that you have your smart phone with you at all times and that WiFi and/or Bluetooth are turned on (e.g., check out Wifarer), however that is not always the case (e.g., when you are home on the weekend you may want to be away from your phone…). Additionally, some of these solutions require a lot of infrastructure (e.g., many WiFi access points and associated networking hardware) and complex installation. Ideally, one would like minimal infrastructure and nothing on your person, but with the capability of scaling to locating and tracking of many entities simultaneously in a privacy preserving way (i.e., avoid using cameras) – this is a pretty tall order…as usual, tradeoffs need to be made and to understand them let’s go over some basics.

So how does positioning work?

There are a few ways – the simplest one involves transmitting a pulse (RF, light, ultrasound), which then gets reflected; this reflected pulse is picked up by a receiver and the time between transmission and reception is measured. Since the pulse speed is known (speed of light for RF and light, speed of sound in air for ultrasonic) the distance can be calculated. Seems simple…but…Let’s look at Radar (and for the moment oversimplify): if the transmission is in all directions (omnidirectional antenna) then your reflected pulse can come from anywhere on a circle (all points on a circle are the same distance from its center, where the radar is located) – we need to do something else to determine direction. This can be achieved by making the antenna directional – a narrow beam is pointed at the direction of interest or the beam is “swept” across a section of interest. Here is another complication – almost everything reflects the radar pulse and most of it is not interesting; how do you track entities of interest? In most cases, a lot of what you are looking at is stationary and this “background” can be accounted for; alternatively moving objects “change” the pulse (check out the Doppler effect if you are really interested) and identifying this change allows one to immediately identify the moving things. So not so simple after all…

Note that if the object you are locating and tracking happens to have a device (with some unique identifier) attached to it, like some sort of tag or Smart Phone, things become significantly easier. Now you can have many fixed transmitters sending out pulses, getting received by the device that can then send out a “reply” (rather than the reflected pulse) that can also contain its unique identifier. The transmitters can be simple and omnidirectional, but then you need a few of them (remember each one defines a circle; in the plane, i.e., in 2D, at least 3 transmitters are needed to determine a unique position) – the determination of a location from measuring distances to a few fixed points is known as Trilateration (check out Multilateration while you’re at it). This still requires some calculations that need to be performed somewhere – basically solving for the intersection point of multiple circles. Additionally, in many cases, the object is moving and we would like to track it accurately and in real time.

There are additional methods for real time positioning specifically for indoor environments, but this is not meant to be a comprehensive survey (Wikipedia’s IPS entry is a pretty good starting point) – suffice it to say that it is non-trivial. What else do we need? We know from location-based applications and services for outdoor solutions that usually we want our location to be displayed on a map of some sort. Similarly, when we determine the position of an entity indoors we would like to see it on some sort of schematic or (CAD) drawing – this is also more involved than outdoor positioning where high quality maps are readily available. Many new buildings may have used sophisticated 3D architectural tools when designing the building and therefore good accurate 3D models of that building are available, that is not the case with older buildings, which, in turn, may imply creating new accurate drawings (based on accurate measurements). These drawings, just like maps, need to be kept up to date.

The technology and many of the standards are pretty much there, but the ultimate indoor positioning solution that is inexpensive, has high accuracy, has good privacy protection, etc., is still not quite there.

At the end of the day, where we are in space and time is tightly coupled with what we are doing and also provides some of our context. Outdoor location is part of the story (when did we leave home, where did we go, etc.) but many of us spend a lot of their time indoors – at home, in the office, in shopping malls, in restaurants, etc. – providing much more information on our activities, behavior, preferences, and more. Whether we want to share this data and let others use it, is a different story…

I am quite sure that indoor positioning systems will become ubiquitous (just as GPS is a given today), enabling an ever-growing number of services to make our lives easier (as well as getting much more targeted advertisements…sigh). Read less