In my previous post, I wrote about how Indoor Mapping might be the answer to bridging the gap toward a seamless end-to-end pathfinding experience. The use cases are exciting and endless, but today I wanted to take a closer technical look at the topic - and explain how we used a small-scale proof-of-concept to explore the capabilities of Apple’s Indoor Survey app.
► Apple's Indoor Mapping
Back in 2013, Apple acquired indoor GPS startup WiFiSLAM, and gained the technology that helped make Indoor Mapping come to fruition.
Typically, GPS accuracy is around 10 metres when performing well. This is fine when travelling down a road in a car, as 10 metres is negligible, but 10 metres vertically could be a difference of 3 floors in a typical office building. This is a huge problem for indoor positioning - and that's if the GPS is working well!
This is where the technology acquired from WiFISLAM comes into play. A user's location is determined by using trilateration of WiFi and cellular signals. This works well outside, but not so well inside a building. Instead, WiFi signals from hotspots indoors can be used to provide an approximate location.
These WiFi signals will be affected by the position of hotspots and the materials used in a building's construction, so location accuracy is then improved by using WiFi fingerprinting to determine the strength of WiFi signals within areas of a building. Other RF parametric data is also consumed, such as cellular and GPS. On top of this, motion data is also recorded to help paint a picture of the actions a user is taking indoors.
All of this data is recorded when using the Indoor Survey app. The user walks around a building with the app, placing ‘marks’ down at various points, and the app records all the information for a full building survey. After a survey, this data is then uploaded to Apple to help augment the CoreLocation framework for indoor positioning.
The CoreLocation framework remains largely the same with the indoor positioning. From iOS8, there's an additional property on 'CLLocation' - 'floor' - which is a 'CLFloor' object. If no floor information can be found, then 'floor' will be 'nil'. This object simply holds a 'level' as an integer, with 0 being the ground floor, and positive and negative numbers indicating above and below ground respectively.
► Finding our way around pathfinding
Leveraging the possibilities that Indoor Mapping granted us, we wanted to experiment with pathfinding within TAB’s HQ.
To do this we looked into the A* search algorithm. A* is an algorithm that is widely used in pathfinding and graph traversal problems, efficiently plotting a traversable path between multiple nodes. It's an extension to Dijkstra's algorithm, using heuristics to guide its search.
Instead of guessing the next node to traverse to, like a simple depth-first-search, A* chooses the next node by looking at what appears to be the most promising node to deliver the shortest route. To achieve this, each possible traversable node has a projected cost generated, and the node with the lowest projected cost is chosen to traverse to next.
The cost function is defined as:
f = g + h
'g' is defined as the cost it took to get to the current node, and 'h' is the projected remaining cost to get to the end goal.
The main thing to note is 'h' in our calculation. This is our heuristic, helping the algorithm to determine the shortest path.
Using a grid data structure, we can mark certain nodes as non-traversable to denote obstacles. Because A* only takes into account traversable nodes, this inherently gives us the ability to calculate paths around objects. These non-traversable nodes correspond to real world obstacles, such as walls in an office, shelves in a supermarket, or stalls in a transport hub.
► Bringing this into the real world
Since we started exploring this technology, we have been excited about the scope for Indoor Mapping in the real world. From transport hubs, to hospitals and shopping malls, there are all kinds of public spaces that would benefit from indoor mapping.
Here at The App Business, we love a lean experiment so taking our early explorations into the A* algorithm, we defined an MVP proposition: to create a proof-of-concept pathfinding app of our very own home - the Spitfire Building.
► A* across multiple levels
Our first proof-of-concept was to modify the A* search algorithm to work across multiple levels. This was achieved by taking a grid that represents the floor plans of both the 1st and 2nd floor of the Spitfire Building and then placing non-traversable nodes between the two areas to block them off. You might be thinking that if we want to find a path between 1st and 2nd floor, we can't - and you'd be right. So how do we fix this?
Node connections define how the grid can be traversed, and in a grid, a node will usually have connections to all surrounding nodes. To enable for traversal between multiple levels, we provide additional connections between nodes on the 1st and 2nd floor. These act as a stairwell, or lift. This means that now, if the target location is on a different level to the starting point, A* is able to pick up that these multi-level connections between different levels in order for them to be traversed.
► The proof-of-concept
With our pathfinding algorithm working across multiple levels, we started implementing it into our MVP.
One thing to note is that Apple's Indoor Mapping currently does not provide floor plans from the surveys uploaded. To counter this, we provided our own floor plan of the office to overlay the map.
To provide a grid for A* to work its magic on, we defined a rectangle to represent the Spitfire Building, with its top left and bottom right representing the latitude and longitude of the respective corners of the building. This rectangle was then split up into multiple nodes, with each node defining a latitudinal/longitudinal point in the office.
Using the method outlined above, we created a grid that represents both floors of the building. With each node in the grid having an associated lat/long, we can work out which nodes on each level should provide the connections between floors to represent the stairwells and lift.
We set up a list of points of interest in our office with associated co-ordinates, such as meeting rooms and bathrooms. With a translation set up between real world co-ordinates and grid co-ordinates, our location point is identified and we can select a destination point. These real world co-ordinates are then translated into the grid space. After the pathfinding algorithm is run, we get back a list of nodes for the shortest path to the target. Translating these nodes back to into real world co-ordinates, we can then render a path onto the map to show the user the quickest route from where they are to their next meeting.
We've only just started to explore the breadth of what we can do with Apple's Indoor Mapping in this MVP. Indoor positioning opens up a lot of opportunities to improve upon existing processes in various industries. If you're interested in finding out more about what we learned during our experiment with Indoor Mapping, get in touch here.