Car navigation technology has made amazing strides over the last decade. Heck, we may talk about a future of driver-less cars, but we already have navigator-less cars, with humans acting only as vehicular operators following the mindless turn-by-turn instructions of some disembodied Voice. Many drivers will freely admit that they’ve lost all innate sense of where they are or how to get anywhere without the assistance of the Voice.
Get out of the car, however, and things aren’t so straightforward – especially once we go under a roof. Part of it is the fact that we’re on foot instead of in a car, making it harder to track our location. But even more important is the fact that, indoors, we are no longer within the benevolent embrace of the GNSS (global navigation satellite system) systems. We’re like bees, with GPS as our queen: If we lose contact with the queen, then we’re lost.
We’ve looked at various different aspects of indoor navigation before, including a general look, specific examples, robot navigation, the challenges of gauging pedestrian motion, and even indoor beaconing systems to replace GPS. But each of these aspects is only a piece of the navigation puzzle. The algorithms will involve sensor fusion if you’re using your phone or some other device that you’re carrying to navigate, but this is also where data fusion has a play. And part of that data fusion is something we’ve touched on but taken for granted: maps.
We can take maps for granted outside. Many of us grew up looking at the maps our parents got for free from the friendly gas-station attendant while on a vacation road trip. (For those of you over-worked types, ask your parents to tell you that story again about how, in the olden days, people used to go on vacations…) Today we can peruse the terrain of some natural disaster half-way around the world using Google Earth. So we expect access to outdoor maps. It’s remarkable how quickly we’ve gone from paper to digital maps; we now rely on them on a regular basis.
Here again, things get trickier indoors. We’re simply not used to indoor maps. Yes, a good mall or airport will have a directory. And if the mall is functioning well, that directory might even be up to date. But that’s about it. You can find maps of campuses or hospitals online, but, most often, those are graphic maps – drawn, but with no underlying data structure; they’re just pictures.
What we’re not used to are consistent maps that can tell us how to get somewhere indoors. Heck, we might not even have the same navigation goals inside. After all, with outdoor maps, we’re mostly looking for a physical location – an address. Indoors, well, we’re not so much looking for a specific set of physical coordinates; we may be looking for a wide range of things: the toy department; the closest restroom with a baby-changing station; a restaurant that has good vegetarian options; the shelf where your favorite brand of toothpaste is (bonus if you can find out whether it’s out of stock); your theater seats; the room where Aunt Tilly is recovering from surgery; the classroom where your final is being held; the gate you’re running to before they close the airplane door on you… I could go on like this… (But I won’t.)
Add to this the fact that there is no standard addressing scheme indoors. Even what makes sense as an address will be context-specific.
Ultimately we can resolve all of these references to a global, absolute physical location (longitude, latitude, altitude), but that takes much more precision than outdoor mapping provides. 5 decimal places on location coordinates get you accuracy down to 1 meter, so we’re talking very fine gradations in two dimensions. And with altitude, inches matter: The distance between two store shelves will be far closer than any realistic notion of relation to “sea level” could provide – given that different oceans have different mean levels and that the level changes throughout the day.
Private companies and private maps
I was able to get a feel for some of these challenges and how they’re being addressed in a wide-ranging conversation with Dave Sutter of Micello (pronounced “my-‘sell-oh”), one of a few companies doing indoor mapping. Micello has been doing this for about four years, and they’ve seen a definite uptick in interest over the last year.
These companies tend to work with individual institutions that want their premises mapped. Unlike outdoor spaces, which are publicly mapped, these tend to be private maps, privately commissioned, and, ultimately, privately presented. That presentation may occur via some application on, say, a phone, but that application may arise as a result of a separate project from the actual mapping. For example, Micello may do the map, but they won’t be doing the app.
Since these maps are more than just pretty pictures, they need to be based on a data set. But the whole notion of an indoor mapping data format is murky. There are a couple of “public” options for storing map data, but they still have their limitations; proprietary formats are common – even if they can be exported to something more generic.
One of the simplest, but least preferred, formats (according to Micello), is the shapefile format. The challenge with this approach is that it’s more or less a huge spreadsheet. Each location will have coordinates, of course, but it may also have a number of context-specific properties (unlike outdoor maps). Bathrooms can have a “gender” property; restaurant tables don’t. Bathrooms may or may not have a baby-changing option; restaurant tables decidedly don’t.
So with shapefile, you have to include columns for gender and baby-changing, even though they apply only to bathrooms. Meanwhile, the restaurant table might have properties like number of seats and window view. So the file needs those columns as well, to be used only for restaurant tables. Do this for all possible destinations, and you end up with a bazillion columns, most of which have no data.
By contrast, geoJSON is an open format that works much more like XML. So you can define properties and then reference them only if relevant for a given destination. If you’re describing a bathroom, then you call out the “gender” and “baby-changing” properties and not the “number of seats” or “window view” properties. (Although I suppose “number of seats” might still apply to the bathroom… “Window view”… not so much.)
The point being, with geoJSON, you don’t have the large, sparse data table that shapefile requires. Even so, geojSON has its limitations; for instance, it allows only polygons for shapes. You can do a decent job with that, but Micello still has an internal, proprietary format that allows actual Bezier curves.
So, ultimately, does it matter which format maps use? Is there a reason to harmonize formats? So far, there isn’t much push for it, but is that because we simply haven’t experienced enough chaos yet?
Navigating with private maps?
This whole aspect ends up being far more subtle than I initially expected. And to make sense of it, we need to think more deeply about what the applications for these maps are. Naturally, from a navigation standpoint, one of the uses of the map is that, given some way of determining where you or a destination or a route between you is, you want to present that on a map. In that case, the map is simply part of the “presentation layer” of the underlying algorithm
But it’s more complicated than that. As suggested above, maps don’t just serve to display the results; they can also participate in the algorithms that determine the results through data fusion – more specifically referred to as “map matching.” The map acts as a set of constraints that can help correct errors that accumulate elsewhere in the algorithm.
Outdoors, if your GPS is a dodgy or your accelerometer has accumulated too much error, the algorithm can look at the map and realize that, according to the sensors, you’re driving right over the top of the Jersey barrier separating you from opposing traffic.
Given the extremely low (albeit non-zero) probability that you are indeed motoring down the median, the map-matching feature helps to disabuse the navigation algorithm of this idea, nudging your location to the right (or left, if you’re in a country that drives on the wrong side of the road) to correct that error.
In reality, you’re probably not using accelerometers for navigation while driving, and GPS is pretty reliable. So map-matching for traditional navigation applications is straightforward to do, but it’s a secondary or tertiary input to the overall navigation approach.
Map matching should be able to provide more value indoors, at least in theory, since GPS isn’t available, and you may therefore be relying more heavily on motion sensors to figure out where you are. If the algorithm shows that you’re two feet away from the elevator and then suddenly you start ascending, the map data allows the algorithm to nudge its internal representation of where you are over by a couple feet, placing you inside the elevator rather than in front of it. (It’s either that or build a model of the Rapture into the algorithm – and there’s definitely no global standard for that!)
That said, however, map-matching is harder indoors than out. And this was one of my big “aha” moments when discussing this stuff: it occurred to me that indoor maps and outdoor maps are, in a way, conceptually opposite entities.
Think about it: the outdoors consists of broad swaths of land, and, throughout the space, there are a few places – the roads and paths – where you can legitimately navigate. Most of the space is “off limits,” making it easy to tell if the algorithm has you drifting into forbidden space. So outdoor map features identify those points where you can be.
Indoors is exactly the opposite. You’ve got broad areas where anyone can walk; these spaces are interrupted by a few barriers like walls or doors or shelving. So indoor map features identify those points where you can’t be. If the algorithm happens to show that you’re standing in a wall, then, unless you’re on Platform 9¾, it should probably nudge you to one side or the other.
But unless you transgress one of those features, then the map is less helpful in correcting errors, since most of the space is fair game. If you’re in the middle of a large convention space where nothing has been set up, the map isn’t going to help, since you’re a long way from any walls or other constraints.
The other thing that makes map-matching tougher indoors is that indoor maps get out of date much more quickly. Especially if you’re mapping a store, including product locations, the map could change in some small way every day or week. That uncertainty will make an indoor map less reliable unless you’re sure you’ve got the latest version or the map pulls live data from a database. (Yes, the formats allow versioning.)
So this makes it seem like map-matching indoors just isn’t that useful. To test that notion, let’s break things down a little more. Hillcrest Labs points out that, for example, with fire fighters entering a building, a good, accurate map can help ensure that the firefighters pick the shortest, safest possible routes both to rescue anyone inside and to fight the fire. This is a matter of life and death, and if the map is even slightly out of date, a fire-fighter might be sent the wrong way, putting either his/her life or the life of a trapped person in danger.
That’s an example of why Hillcrest Labs prefers to rely as much as possible on a solid inertial-sensor-based approach to navigation, relying on maps as little as possible. They outright suggest that map-matching can be too easily used as a crutch by companies that have less robust inertial navigation algorithms.
That said, both they and Movea do include maps in their algorithms, even for indoors. Because mapping tends to proceed project-by-project, both companies end up accepting any format and dealing with conversions manually. There’s no high-volume engine that resolves proprietary formats.
Micello’s Mr. Sutter one possible change that could spark format unification. It’s something that helped to drive the outdoor mapping standards: 911. He noted that, if the FCC were ever to mandate that 911 calls include indoor location information, this would likely force the industry to figure out a single way of representing internal and external locations.
Finding the goods
But there’s another consideration that arose in a discussion with Sensor Platforms. Google, of course, isn’t sitting on their outdoor-mapping laurels. Granted, they haven’t sent their little cars rampaging through our malls and houses (yet – it could be dangerous for the drivers: could this be their real motivation for driverless cars?). But they are still working to improve their reach indoors such that, when you use the map feature on your Android phone, it can go deeper into an edifice.
Using the Android map means going into Googles map database and pulling information out from that. To me, this feels like an extension of outdoor mapping to the indoors. But that can only go so far. It can get you to a store or other building, and perhaps even to some room within that building – and that’s it.
If a store wants to take you further – say it wants to show you where it has the shoes you’ve been looking for on sale, then it has to provide information about where that inventory is located in the store. That typically happens by tying into the store’s inventory database. And the store is decidedly unlikely to give Google access to that database. A store will want to protect that information, and a mall may well want to protect mall mapping as a service for its tenants.
So this really leaves us with two levels of navigation. There’s the “generic” one, with, say, Android directing us outdoors and probing perhaps more deeply inside than they currently do as they get access to more building blueprints. Then there’s proprietary mapping, where a store or mall or airport or hospital will have a custom application that provides a much more detailed picture of what’s where.
This latter case is what we described above as a privately-commissioned map presented via a privately-commissioned application. That application could invoke inertial sensors, beacons, and the private map to improve the navigation algorithm’s results. And because of the sensitive nature of the material and the potential competitive edge it gives the owner, these maps are likely to remain proprietary, as will the underlying formats, the applications, and the presentation graphics.
Although the great outdoors has been rather thoroughly mapped, indoor work is still in its early days. Because it’s largely private businesses launching mapping projects, each with its own requirements, the various indoor spaces are being mapped one at a time. And there are a lot of such spaces to map. (And remap if a store closes and is replaced by another.)
So it’s all still a bit rough and ready. Companies are busy mapping, and there’s enough work to keep them from running into each other. Once there’s a bigger “installed” base of maps, and once we start using them more, then there may be more of an incentive to streamline things. For the time being, it’s deal by deal, map by map.
Companies doing this include Micello (the only one of the companies I contacted that responded), Aisle411, and Trimble. Of course, Google and Microsoft are also busy trying to map everything. But, unlike with outdoor mapping, they don’t seem to have a lock on this. Yet, anyway.