Indoor navigation - from an idea to a working prototype


    Developers of the internal practice of DataArt Travel and Hotel Business present an internal positioning system and explain how it is interesting for the industry.

    What is a indoor positioning system?

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

    Why not use GPS?

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

    Why are we doing this?

    Firstly, this is a new global trend, and no one has yet proposed a cheap and easy-to-use product that would meet the requirements of the trend. Therefore, development is a great opportunity to test strength in this segment.

    Secondly, we received several requests from companies that need solutions for internal navigation.

    Thirdly, for ourselves this is important and interesting. Personally, even after five years spent on higher education and obtaining a degree, it’s 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 arguably the cheapest option for a Bluetooth connection with a capacious battery, medium range (15 - 30 meters) and UDID / Major / Minor configuration support.


    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 a locus of intersection points, good performance in a laboratory environment (insignificant noise, 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 in a mesh pattern. At each point in time, your device will be in the field of 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 sophisticated mathematical models to reduce the effect of noise and adjust filtering coefficients when changing location, signal strength, etc.
    • Hybrid systems - combine two or more approaches described above to minimize location errors, or to switch between approaches depending on external conditions.


    Main problems

    Multipath propagation and signal attenuation. Indoor navigation systems based on BLE all rely on electromagnetic waves. This can lead to incorrect readings from beacons that are far away from the user, or to:
    1. Missing beacons. Sometimes CoreLocation shows that the coverage of the beacon is unknown, although a second ago it was listed as the closest.
    2. Intervals in dimension. Unfortunately, it is impossible to change the intervals for measuring and delivering information that are registered inside CoreLocation (updates go every second).
    3. Map engine All of the above things do not matter if you do not have a work card with metadata. The map is the heart of the navigation application, and the navigation and mapping 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 elements. If that doesn't work, use OSM and MapBox. ” Yes, that's right, but if you use MapKit, you end up with a ton of obstacles:

    • Elements must be aligned and sized according to the existing grid of the created map.
    • The building plan is made in the plane, the maps use the Mercator projection.


    That's why we decided to take the CATiledLayer approach: a 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 spoiled by the absence of Z-coordinates. After switching to 3D (each beacon has coordinates Vx, Vy, Vz), things went better, but not as much as expected.

    After several brainstorming sessions, we decided to use the normal distribution to simulate the height of the device and switch to the Center of Force principle. 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 that such calculations lack accuracy with small RSSI values ​​due to signal attenuation. This can lead to significant calculation errors.

    Prospects


    Despite the fact that the prototype allows you to achieve very good results (an approximate error of three meters, which, in general, is enough for airports and shopping centers), we see a lot of points that can be added or improved. Here are some:
    • Motion detection for adaptive filtering, which will allow 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 confidence in the readings of the beacon and its threshold value to rely on “trusted” beacons in each iteration.
    • A more sophisticated “geometric filter” for driving direction and determining turns.
    • Metadata - a graph of routes and waypoints (intersections, POIs, etc.).
    • The option "Snap the current position to the grid", as is done in real maps and navigation applications.
    • A routing algorithm for finding the (shortest) path.


    Some screenshots





    Posted by Yaroslav Vorontsov, Senior iOS Developer.

    Also popular now: