Navigation, Pedestrians and Landmarks (Part 1)
Don’t know how many of you played “Zork: the Great Underground Empire” released by Infocom in 1980. It was a text-based game for computers (there were no graphics involved). Instead, you were supplied a concise description of the scene facing you, such as
West of House
You are standing in an open field west of a white house, with a boarded front door.
(There is a small mailbox here.)
To move through the game you needed to keyboard in actions, such as “walk to the Mailbox.” After opening the mailbox, you got the idea that the house was the real target, keyboarded instructions to approach it, found the way in and discovered all sorts of treasures. However, the house was merely a portal to the Great Underground Empire and then the game began.
It is this notion of finding the paths to places with which we are unfamiliar and perhaps cannot adequately describe that powers my interest in navigation by pedestrians. We all deal with this problem. In Zork it would have looked like this:
“You are standing at Fifth and Main.
A stranger approaches and gives you a slip of paper. On it is printed “The Oinker Bar in one hour.”
The game is afoot!”
You know where you want to go, but you do not know exactly how to get there. In fact you may only know where you want to go at a topical level, not at a spatial level. In the example above we need to find the Oinker Bar. Unfortunately, we have no idea where it is located. So, we cheat, we use our mobile phone and initiate a local search for the Oinker, presuming it is somewhere around us, and bingo (should that be BING?) our trusty local search engine returns the location. From there it is just a short, few hundred keystrokes until we can see a map and a route taking us to the Oinker. Problem solved? Maybe, maybe not!
The success of a foot-route depends on several factors. One important issue is whether the application providing the route can locate your position with enough accuracy to suggest a “useful” path to another location. Another concern is whether the map database being used to generate the path includes spatial cues that would benefit the navigator who is on foot, or if includes the types of cues needed to access to multi-model transportation to reach the destination. Perhaps of greater significance, can we determine, with an appropriate level of specificity, where the pedestrian is located and the direction in which they appear to be moving?
Before we go over the cliff, I suppose I should tell you more about why this is of interest to me and many who are interested in Local Search.
There are millions, perhaps billions of foot trips every day and many of these odysseys involve searching for destinations that provide a specific service. Since the walkers are mobile they might require assistance to identify and locate the service. Due to the serendipitous mindset that sometimes characterizes walking, people who start out not looking for a good or service may run into one that appeals to them.
Knowing where these potential consumers are located and where they are going may provide an advertising venue that allows an ad distributor to supply spatially targeted inventory to the those navigating on foot. It is likely that the device of choice to deliver this information will be some form of smart phone. Delivering targeted information that might result in a sale and meet the needs of the consumer who is on foot is a market that many feel has a significant economic potential.
Changing your mindset – literally
It’s at this point of the discussion that I am going to mention that it may be inefficient to put a “head” that normally develops automobile navigation systems and traditional navigation map databases on the shoulders of someone who needs to develop a system for pedestrian navigation and advertisement delivery. While we will describe advertising later, let’s just think about the differences between automobile navigation systems and a system designed to promote navigation by pedestrians. I’ll give some of the game away here – I am not convinced that the main solution to this problem is a map database, but we will get to that later in the series.
The methods of moving between locations on foot or by car are obviously quite different. In addition, both set of movements are governed by different types of rules and considerations. The movements of pedestrians, for example, are often interrupted by intervening opportunities, reclassification of objectives, sometimes something as simple as satisfying the urge to find a new way to move between locations. Movement on foot is probably more influenced by socio/temporal consideration than vehicular movements (is it safe to walk this path at this time of day?), may reflect environmental considerations (e.g. “It’s cold, I think I’ll take the Skyway) or aesthetic considerations (e.g. “Is that a statue? Let’s look”).
In other words, calculating the number of paths available to walkers moving between locations can be enormously complicated. Conversely, the paths available to a car are quite restricted. Automobile navigation systems benefit from these restrictions, since it is quite easy to calculate a legal route between locations when you must use streets as the links/ pathways available in the network. In addition, since automobiles will normally be limited to traveling along streets, roads or highways, it is relatively easy to match location and position, even when some of positioning data are missing, obstructed or possibly erroneous – since “map matching” can be used to accommodate these variations.
Conversely, we might consider if there is a surrogate for map matching when tracking the path of pedestrian between two locations? They can move anywhere there is access that is not restricted by a barrier of some sort. If the barrier is permeable (e.g. there are doors or gates) the pedestrian can even move through seeming obstructions to navigate to a destination. Hmm, seems like a hard problem. Then again, even if we did so, it might not be a particularly useful tool.
To solve the problem of supplying route guidance to pedestrians, we need to know where they are located and develop some notation for helping describe the path that will take them to their chosen destination, as informed by their choices about how we should calculate the path. Finding their location and guiding them to a new location are an extremely difficult problems. They are akin to the problem in robotics of how a sensor-equipped-probe navigates a landscape that is completely unknown to it (wait, did I just personalize a robot?) before the device enters the environment to be traversed. Perhaps it is here and in computer vision that we might find some ideas on solving these problems.
Let’s hold that until next time when we talk about paths, landmarks, maps and other interesting stuff. It is going to take several blogs to cover the important stuff, so if this not interesting to you, check back in a couple of weeks.