Under the term localization in buildings, we can imagine methods and techniques with the aim to determine your location where there is no GPS coverage, let’s say in a building. There are several methods but today we will focus on dead reckoning.

What is dead reckoning and how does it work?

It’s a navigation method as old as humanity itself. It’s intuitive and straight forward but its accuracy depends on the experience of the person using it. Let’s take a treasure map as an example. “Walk twenty steps north, then turn right and walk another thirty steps,” says the map. “Turn left and take ten steps more. Start digging.”

If we stick to the instructions, we should end up on top of the treasure. But it’s not there… How’s that possible? It’s because the alpha and omega of this method are missing from the instructions – the starting point. It has to be an exact spot, in this example an exact spot on the treasure island. If we start from that spot, we should find the treasure.

The basic principle is to account for deviations from the starting point. It’s sufficient to determine a location using the GPS and from there we can start our movement in space. We know exactly where we started and because we saved any deviation, we can, using vectors, easily calculate our current position. Well, that’s in an ideal world.

What are the disadvantages of dead reckoning?

As with every method, even this one has a weak spot. It’s dependent on the quality of measured deviations, which have to be measured precisely. It is not necessary to measure the deviations down to nanometres and angular seconds; decimetres and degrees should be fine. But even that is sometimes a problem. Take smartphones for example. This amazing device has so many sensors that can be used and dead reckoning therefore seems to be the ideal method. Unfortunately, it’s not that simple.

What is it called in the language of mathematics?

We have a starting point in space, let’s take the Cartesian system for simplicity. We deviate from the starting point by a certain distance in a given direction. This deviation is represented by a vector. Getting back to the treasure map example, the deviation will give us this set of vectors.

The picture looks very nice, right angles everywhere as we expect them to be. Everything just looks very exact and on point. When we actually measure the deviations, the reality can become a bit different. One right angle is 85°, another can be 95°. And the picture starts to lose its luster. The noted path would then look completely different. I indicated the error in angle measurement by a blue cone at every point. And that is only half of the problem.

Because not only can we measure the angle wrong, but also the distance. These measurement errors can occur and we have to be aware of this possibility. But I’m not saying that the method is useless or wrong. The truth is that this navigation is so good that it was used in aviation until the rise of GPS systems (Inertial Navigation). You only need good quality sensors for it to work well.

How can you perform dead reckoning using your smartphone?

We need to take into consideration that an aircraft gyro and an accelerometer won’t fit into a smartphone. Therefore we have to use a different approach and account for the errors in measurement. We’ll solve this using statistics. Then we only need to take the average deviation in order to prevent steps like “now face backwards” showing up, as it only takes pointing the smartphone to the ceiling. Android partially solved this problem for us by implementing a software position sensor but it’s still good to average the data a bit. Should that not be sufficient, we can use data from other sensors. The traditional air navigation uses only an accelerometer and a gyroscope, we can often use a magnetometer, more commonly known as a compass. But we have to understand that the data we get is from three different axes (x, y and z). To get a rotation vector, it’s necessary to transform the data.

That’s it for angular deviations. The distance gets a bit trickier. When talking about navigation in a building for users, we’ll make the most use of sensors that can capture the user’s steps. Android is equipped with two sensors that can do this: the Step Detector Sensor and the Step Counter Sensor. Personally I would recommend the first one because it triggers an event at every captured step. The second one measures the steps a bit more precisely but the result is supplied by Android with a few second delay, making the application slower.

If we add some nice fluff to these elements, for the app to show a neat building plan, we can start using dead reckoning.

Why and where is dead reckoning used?

Do you doubt its applicability for a phone? It works! Microsoft created an app that leads you through a building and uses even more sensors than those we mentioned. Using more sensors is a great idea by the way; a barometer that determines height can indicate the floor you are on etc.

We are not used to this type of navigation as it’s necessary to walk through the navigated route beforehand. The navigation itself works only after this step. Therefore it’s not an ideal solution for ad-hoc navigation, like “I get my car and want to get to a certain location”. So what is it good for?

Where would one want to guide other people via a given route? You might think of shopping malls but I have something else in mind. I mean places where you can also learn something. Museums, galleries, exhibitions… In these places dead reckoning is the ideal method for navigation. It leads you from one exhibit to another and makes you stick to the prepared route. You can easily walk from one distant pavillion to another and it will not affect the principle of navigation. You don’t even have to invest in additional infrastructure or other devices such as the iBeacon transmitter. Dead reckoning is not dependent on any of these. All you need is a phone with an accelerometer and a gyroscope.

Next, we will take a closer look at multilateration.

Previous articles:

• Localization with a to-the-room accuracy fast and easy (1/4)