Indoor navigation - from idea to working prototype

The developers of the internal practice of DataArt "Travel and Hotel Business" represent the internal positioning system and tell us how it is interesting for the industry.

What is an indoor positioning system?

Based on a Wikipedia article, this is a solution for finding objects and people inside a building using radio waves, magnetic fields, acoustic signals, or other sensory information collected using mobile devices. Simply put, using this system, you can determine your location in a large building, using only a special application on your smartphone. For people who do not work in the technical field, it sounds like magic; for those who are lost in airports, shopping centers and other buildings - as a panacea; for developers of hardware and software - as a serious challenge.

Why not use GPS?

Significant disadvantages of GPS are its dependence on signal stability and multipath propagation leading to fatal errors. Of course, you can use GPS repeaters, but this is not a cheap pleasure. Therefore, the positioning system in the interior is an extremely profitable alternative.

Why do we do this

First, this is a new global trend, and no one has yet offered a cheap and easy-to-use product that would meet the requirements of the trend. Therefore, development is a great opportunity to test the strength in this segment.
')
Secondly, we received several requests from companies that need solutions for internal navigation.

Thirdly, it is important and interesting for ourselves. Personally, even after five years spent on higher education and a degree, it is interesting for me to discover something new and solve complex mathematical and technical problems.

Necessary equipment

iPhone with iOS 8.0 or higher. It is desirable that a motion processor (M7 / M8) be installed in the device.
BLE beacons. This is probably the cheapest option for a Bluetooth connection with a capacious battery, an average work radius (15 - 30 meters) and support for the UDID / Major / Minor configuration.

Modern approaches to solving problems

Triangulation and trilateration are two mathematical approaches that rely on the angle and distance scales, respectively. They have similar principles - searching for the locus of intersection points, good performance in a laboratory environment (low noise, limit of visibility of beacons, etc.) and average or unsatisfactory results when working in a living environment due to several intersections or their absence.
Mesh - beacons are arranged on a mesh pattern. At any time, your device will be in view of a limited number of beacons, allowing you to roughly determine your location.
Advanced filtering approaches (particle filters and Kalman filters) - use probability theory and complex mathematical models to reduce the effect of noise and adjust filter coefficients when changing location, signal power, etc.
Hybrid systems - combine two or more of the approaches described above to minimize errors in positioning, or to switch between approaches depending on external conditions.

Main problems

Multipath and attenuation. Indoor navigation systems based on BLE all rely on electromagnetic waves. This can lead either to incorrect readings from beacons that are far away from the user, or to:

Disappearing beacons. Sometimes CoreLocation shows that the range of the beacon is unknown, although a second ago it was listed as the closest.
Intervals in measurement. Unfortunately, it is impossible to change the intervals of measurement and delivery of information, which are registered within CoreLocation (updates go every second).
Mapping engine. All of the above things do not matter if you do not have a working map with metadata. The map is the heart of the navigation application, and the navigation and navigation engines are the brain.

Some technical details of the current implementation

The first problem we encountered is directly related to the map. "What is the problem? - you ask. - MapKit allows you to use custom items. If that doesn't help, use OSM and MapBox. ” Yes, this is true, but if you use MapKit, you end up with a lot of obstacles:

Elements must be aligned and adjusted in size in accordance with the existing grid of the created map.
The plan of the building is made in the plane, the maps use the Mercator projection.

That's why we decided to stick with the CATiledLayer based approach: the map is an image made up of small tiles, and the image has several levels of detail.

The second (and main) problem was, of course, the search for the current location. We tested both trilateration and triangulation in two-dimensional space, but the results were significantly affected by the absence of Z-coordinates. After switching to 3D (each lighthouse has Vx, Vy, Vz coordinates), things went better, but not as much as expected.

After several brainstorming sessions, it was decided to use the normal distribution to simulate the height of the device and switch to the principle of Center of Force. In each iteration, the device calculates the influence vectors of each beacon on the coordinate and applies them to the current position, thus correcting errors. The direct distance to the beacons is calculated using their RSSI values. The only problem in this case is related to the fact that such calculations lack accuracy at small RSSI values due to signal attenuation. This can lead to significant calculation errors.

Perspectives

Despite the fact that the prototype allows to achieve very good results (an approximate error is three meters, which, in general, is enough for airports and shopping centers), we see a lot of things that can be added or improved. Here are some:

Motion detection for the implementation of adaptive filtering, which allows you to make changes to the filtering algorithm on the fly or adjust its coefficients.
A more sophisticated solution to the problem of “disappearing beacons” is the introduction of a level of trust in the indications of the beacon and its threshold value in order to rely on the “trusted” beacons in each iteration.
A more sophisticated "geometric filter" for driving direction and determining turns.
Metadata - a schedule of routes and waypoints ("intersections", POI, etc.).
The option “Bind current position to grid”, as is done in real maps and navigation applications.
Routing algorithm for finding the (shortest) path.

Few screenshots