Navigation, Pedestrians and Landmarks (Part 2)
I have started using the term foot-driven navigation to describe this topic, because the path that a walker takes in moving between locations often is less directed than the path of a car moving between locations. While not quite a random-walk, foot-driven navigation is a series of path-parts, each with mini-objectives (what’s in that window?) interlaced into a series of saunters that eventually deposit the walker in the desired destination. The important point here is that the pedestrian’s choices form the path taken and, for this reason, the term foot-driven navigation seems appropriate. (By the way this term popped into my head when I was reading an article by Frank Stajano (University of Cambridge Computer Laboratory), about Foot-Driven Computing. His most recent article appeared in the July, 2009 edition of the SIGSPATIAL Special that was focused on privacy and LBS. The “Special” is the newsletter of the ACM Special Interest Group on Spatial Information. Thanks to Duane Marble for calling this to my attention.)
Now, back to describing the issues of interest in creating a route guidance system for pedestrian navigation.
Foot-driven navigation will be delivered to users via smart phones through multipurpose websites that provide mapping, routing (vehicular and foot), as well as a variety of other services (local search, LBS, etc).
Foot-driven navigation will require more diverse types of data to support route guidance than automobile navigation. But if we have GPS on phones, why would we need additional data to provide route guidance for foot-driven navigation?
While many might think that geotagging the location of pedestrians would be a leading benefit of GPS, often this is not the case. In many of the environments commonly encountered by pedestrians, GPS signals may arrive after they have been reflected (multipath) or degraded. Both of these circumstances introduce significant errors into calculating the position of the user.
The degradation of GPS signals is a common occurrence and resolving this problem has led to a search for technology that might be able to enhance the localization of mobile cellular devices (and their users). In Assisted GPS (AGPS) GPS is augmented by the use of complimentary technology, such as cell tower triangulation and a data server that are used to calculate a new, enhanced position.
In order to enhance GPS to “route” pedestrians, additional databases will need to be collected that can help localize the user. It is likely that “war driving” to collect data on the strength of signals from cell towers at locations and the strengths and locations of nearby Wi-Fi access points will be required to supplement GPS. However, as noted above, GPS and other location indicators (Wi-Fi, cell tower triangulation, etc.) may not work well in urban canyons, where there are numerous forms of interference, mostly in the form of occlusions such as tree cover, awnings, tunnels, etc.
One final localization technology of interest to our problem is the digital compass, such as that included in the new iPhone 3GS. The compass can be used to determine the direction the user (perhaps the phone) is facing. Knowing the direction the user is facing will be important in calculating the path and for determining where the users might be looking, what they might be looking at, and their “pose” when photographing objects along their path – but more about that later.
In addition, to the databases mentioned above, what other databases might we need to undertake building a route guidance system for pedestrians?
Route guidance designed to assist pedestrians using mobile devices obviously requires some form of map database. The map database should be designed to provide coverage of the comprehensive network of paths that could be used by pedestrians to travel from their present location to a destination of interest.
Existing navigation databases, such as those produced by Navteq and TeleAtlas, can meet many of the requirements for developing route guidance systems for pedestrians. However, as Navteq has shown with the announcement of its Navteq Discover Cities coverage, additional information is required to ensure that databases originally developed for automobile navigation can meet the needs of pedestrians. It is likely that these automobile navigation databases will be of significant benefit to pedestrians walking along streets that are included in the navigation databases.
Converting an automobile navigation database into one that can support route guidance for pedestrians obviously requires augmenting streets with pedestrian crossings and information supportive of foot navigation. Foot-driven navigation also requires the inclusion of information concerning paths limited to pedestrian access (zones, walkways, tunnels, building passages, underground malls, etc); a collection task that is certain to be complex and difficult. For example, the alternate path classes listed above may not have official names, may involve geometry that varies temporally (including day-parting), or could involve recording a z-value (for elevated walkways or the like).
Presuming that some organization could gather the data mentioned above (and afford to refresh it periodically), what other databases might be required to provide route guidance for pedestrians?
One thing that pops-up quickly, when you play with building such a system, is the need for a comprehensive geographical gazetteer. The gazetteer would serve as a repository for both official and unofficial place names, as well as the names that might be associated with pedestrian lanes and walkways, common meeting places or other areas that could be used as “thoroughfares” for the walker.
It seems likely that the geographical gazetteer would need to be based on information from a mixture of sources. Likely candidates would include the names available in automobile navigation databases, official sources of geographic names (e.g. governments at all levels) and crowd-sourced names, as the commonly used name for a feature may not be the official name for the feature.
In the past, I believed that all gazetteers should be authoritative and definitive, but, in regards to foot-generated navigation, I have concluded that the gazetteer needs to be exhaustive at the expense of being authoritative. Why? Because the best clue you may have to where the user is located could be the name of a feature that they use to describe their position. If they cannot see a street sign or other location-related sign, or do not know the official name of the position describing their location, they may know some alternative name or descriptor. I would hope that a navigation system would be able to find that name in a gazetteer and append it to the appropriate location.
Next, it seems that the effectiveness of a useful foot-driven navigation system would depend on reference to a comprehensive business listing directory. The use of store branding to identify shops and reference a pedestrian’s location seems an obvious need. In addition, shops may be the destination or sub-destinations on a foot traveler’s path, or serve as well-known features along these paths.
But we need something more to really nail route guidance for pedestrians and it is…a database of landmarks. Perhaps some would call these POIs, but I will use the term landmarks and work through the complexities of that issue in the next blog. Landmarks are extremely interesting and their use may be the most promising method of providing route guidance to pedestrians. Indeed, matching a pedestrian’s real-time photograph of a “landmark” with a master-database of photographs of “landmarks” may be just the solution for the foot-directed navigation problem. But why would anyone be silly enough to do that and when would you need to use such a method? Let’s begin to discuss that next time, too.
In summary, route guidance systems for foot-driven navigation will attempt to create paths based on GPS and map data bases. When these fail, geographical gazetteers and business listings directories will help fill the gaps. When GPS fails, other location databases (e.g. cell tower strength, etc) will be applied. But, all of these solutions will be enhanced by the use of landmarks and by the pedestrian becoming an active part of the localization solution.
I will be out of town on business next week and may not be able to post my next blog on this topic until the following week. For those of you who will be celebrating, I hope you have a relaxing and enjoyable 4TH of July.