This week DataArt’s R&D team covers the hot topic of the indoor navigation.
DataArt’s Travel and Hospitality practice developed a PoC indoor positioning system. Now we’re ready to tell you why it’s important for the industry.
What is an Indoor Positioning System?
According to Wikipedia, it’s a “solution to locate objects or people inside a building using radio waves, magnetic fields, acoustic signals or other sensory information collected by mobile devices”. Under real world conditions, that means that you’re able to locate yourself in a large building using only a special application installed on your smartphone (of course, the rest of the equipment is hidden/not visible for you). Sounds like magic to non-tech people, a relief for those who’re always lost in airports, malls or other large buildings, and a challenge for hardware and software engineers.
Why not GPS?
Because GPS suffers signal attenuation caused by the different materials used in buildings, signal power loss, and multipath propagation that lead to uncorrectable errors. Of course, you can deploy GPS repeaters, but it’s not a cheap solution. In such cases, an indoor positioning system is a great alternative because of hardware prices.
Why We’re Doing This
First of all, it’s a worldwide trend, and it seems that nobody has provided an easy-to-deploy and cheap (or, at least, sold at reasonable price) product yet. That’s why it’s great to have a working PoC or even IP in this area, and that leads us to the second reason, we have several incoming requests from companies who are seeking a ready-to-use indoor navigation and pathfinding solution. The final point is that we’re doing this for our own fun and education. Seriously, even after 5 years of higher education and a PhD, I’m not tired of discovering something new and solving complicated mathematical and technical problems.
- An iPhone with iOS 8.0 and higher installed. It’s great if the device has a movement co-processor (M7/M8)
- BLE beacons. Perhaps the cheapest model that has a long-life battery, medium ranging distance (15-30 meters) and supports UDID/Major/Minor configuration over a Bluetooth connection.
Modern Approaches to Problem Solution
- Triangulation and Trilateration – two mathematical approaches relying on angle/distance measurements, respectively. They both share the same principles. Search for a locus of intersection points, work well in a lab environment (negligible noise, line of sight of the beacons, etc.), and give average or poor results in real world conditions due to multiple or a lack of intersections.
- Grid concept – beacons are places using a grid pattern. Your device will be in range of only a limited number of beacons at any point in the building, thus allowing you to identify your approximate location.
- Center of Forces/Gravity/Mass – a physical approach that assumes each beacon has its own force/weight function that affects the device’s current position. The nearest beacons are considered to have maximal force/weighting while the farthest have minimal. The resulting center of force/mass, which allows the whole system to be stable, is calculated with each step using the superposition principle.
- Advanced approaches with filtering (Kalman/particle filters) – employ probability theory and complex mathematical models to reduce the effect of noise and to tweak the position accordingly when there’s a significant/negligible change in location/signal power/etc.
- Hybrid systems – combine two or more of the approaches described above to minimize precision errors or to switch between them depending on external conditions.
- Multipath propagation and signal attenuation – yes, BLE-based indoor navigation system still relies on electromagnetic waves. This may lead either to “false positives” from beacons which are far away from your actual position or to:
- Beacons disappearing – sometimes CoreLocation says that a particular beacon’s range interval is unknown (even though a moment before this beacon was ranged in the “Immediate” zone).
- Measurement intervals – unfortunately, it’s not possible to change the measurement and information delivery intervals which are set somewhere inside CoreLocation (updates are delivered each second).
- Map drawing engine – all those things described above are senseless until you have a working map with metadata. It’s at the heart of a navigation application while the navigation and routing engines are its brain.
Some Technical Details from Current Implementation
The first problem which we had to solve was regarding the map. “Not a problem”, they will say, “MapKit allows you to use custom tiles. If you don’t like it – use OSM and MapBox”. Yes, that’s true, but if you use MapKit, you’ll end up with another heap of challenges:
- tiles should be aligned and sized according to the existing map grid;
- maps use Mercator projection while the building’s plan is flat;
That’s why we decided to stick with a CATiledLayer-based approach – the map is a tiled image which has several levels of details.
The second and the key problem was, of course, location search. We tested both trilateration and triangulation in a 2D space, but the results were significantly affected by the missing Z-coordinate. After switching to 3D (each beacon has Vx, Vy, Vz coordinates), things went better, but not as much as we expected. After several brainstorming sessions, we decided to use normal distribution to model the device’s height over the floor and to switch to a Center of Forces approach. During each iteration the device calculates the affection vectors from all beacons and applies them to its current position, thus correcting for errors. Direct distance to beacons is calculated using their RSSI values. The only problem here is that such calculations lack accuracy with low RSSI values due to attenuation and sometimes may lead to significant calculation errors.
Though the prototype allows achieving pretty good results (appoximately an accuracy of 3 meters, which is enough for airports and malls in most cases), there are plenty of things to do or to improve. Here’s a short list of them:
- movement detection for adaptive filtering in order to change the filtering algorithm on the fly or tweak its coefficients;
- more sophisticated solution to the “disappearing beacons” problem – introduce something like a “confidence level” and its threshold value to rely on “trusted” beacons during each iteration;
- more sophisticated “geometric filter” for movement direction and turn detection;
- metadata – graph of routes and waypoints (“crossroads”, POIs, etc.);
- “Snap current position to grid” option, like is done in real-world map and navigation applications;
- routing algorithm for pathfinding (wave or Dijkstra shortest path algorithms).