Universal Navigation on Smartphones

People routinely seek navigation assistance to find their way from one location to another. In particular, knowing one’s current location and finding ways to get to another location in unfamiliar geographic areas (e.g., a person visiting a city for the first time) can be daunting tasks. For thousands of years, humans have been building devices to provide navigation assistance, as reliable way-finding is important to everyone. Early navigation devices were based on the advanced technologies of the time which were mainly mechanical in principle and were not based on maps. As technologies further advanced and new technologies emerged, new navigation devices were developed. Current navigation devices enjoy a range of new and advanced technologies which are based on electronic principles and maps. Of the advanced technologies that provide the foundation for navigation gadgets, Global Positioning System (GPS) is the one which has had the greatest impact on the increasing popularity of navigation systems. Navigation technology for use in the outdoors can be grouped into four generations. Navigation technology for use in the indoors has a shorter life span and can be grouped into two generations. There are differences between navigation in outdoors and in indoors including the requirements for navigation assistance and the types of technologies and maps.

Today’s outdoor navigation systems are based on various advanced technologies. The main technologies include geo-positioning to determine the current location of a user in real time (e.g., using GPS), wireless communication to obtain updated data about traffic and weather in real time and/or to provide navigation services via remote servers, and database for storage of spatial and non-spatial data in the form of networks (e.g., road networks). GIS databases are the main source of data for outdoor navigation systems. Using these technologies and appropriate algorithms, outdoor navigation systems perform such functions as: data retrieval, e.g., finding points of interests (POIs), map creation (rendering a map at a specific scale), mapping, e.g., zoom in/out, geocoding (finding coordinates of POIs, origin or destination addresses), routing (finding optimal routes from current location to a given destination or between pairs of origin and destination locations), navigation (tracking the movement of the user during a trip), and directions (a set of instructions to assist the user with a given route). Usability features of outdoor navigation systems include mode of travel (driving, walking, riding in a wheelchair or on a bike), map presentation (road segments and networks, sidewalk segments and networks), navigation situation (static, dynamic), purpose of trip (commute, emergency, leisure), and user’s preferences with respect to POIs, routes, and map presentation.

While indoor navigation systems are available, they are not as popular as outdoor navigation systems. The major reasons for this lack of popularity are (a) navigation assistance in indoors (buildings) is not crucial as people do not consider getting lost inside of buildings and (b) options for making navigation decision in buildings are very few. For these reasons, indoor navigation systems are mostly designed for special needs populations (e.g., for visually-impaired) and special occasions (e.g., emergency). The main technologies for indoor navigation systems are geo-positioning to determine a user’s current location in real time (e.g., using RFID), wireless communication primarily for positioning, and databases for storage of spatial and non-spatial data (e.g., hallway network). CAD databases are one source of data for indoor navigation systems. Typical functions performed by indoor navigation systems are data retrieval (e.g., finding POIs), map creation (rendering of floor layouts), mapping (e.g., zoom in/out), geocoding (finding coordinates of POIs, origin, or destination addresses), routing (finding optimal routes from current location to a given destination location or between pairs of origin and destination locations), navigation (tracking the movement of the user in the building), and directions (a set of instructions to assist the user with a route through a building). Usability of indoor navigation systems includes mode of travel (walking, riding in a wheelchair), map presentation (hallway segments and networks), purpose of trip (commute, emergency), and user’s preferences with respect to POIs, routes, and map presentation.

To overcome the shortcomings of current navigation systems and services (for both outdoors and indoors), Universal NAVIgation Technology (UNAVIT) is proposed. UNAVIT refers to a new and emerging navigation service that is expected to be available on smartphones. Features of UNAVIT are navigation anywhere, which means the capability to provide navigation assistance regardless of the environment (outdoors or indoors); at any time, which means the capability to provide appropriate navigation assistance based on the time when it is needed; for any user, which means the capability to provide navigation assistance to users with different needs and preferences. UNAVIT is also able to function for any mode of travel, which means the potential to offer navigation assistance appropriate for each possible mode of travel; to provide navigation assistance automatically with the least intervention by the user; and to be adaptable, which means offering specific navigation assistance based on changes in user behavior. Given that UNAVIT will be service-oriented, various possible architectures (each with its own pros and cons) are possible. UNAVIT will be one of the pervasive applications on smartphones, such as Android and iPhone, and through Web Mapping Services such as Google Maps, Bing Maps, Yahoo Maps, and Mapquest.

Anywhere navigation is the ability of UNAVIT to provide navigation assistance anywhere, outdoors and indoors, regardless of geographic location. To support this capability, in addition to providing navigation in outdoors and indoors, UNAVIT must be able to provide navigation assistance seamlessly when the user transits from outdoors to indoors, or vice versa. Detection of transition between the two environments is important as each environment requires different geo-positioning sensors and different map databases. When transition from outdoors to indoors is detected, there should be a handoff from the geo-positioning sensor for outdoors (primarily GPS) to geo-positioning sensor for indoors (e.g., RFID or WiFi) and of map database for outdoor (GIS data) to map database for indoor (CAD data). When transition from indoor to outdoor is detected, there should be a handoff of geo-positioning sensor for indoor (e.g., RFID or WiFi) to geo-positioning sensor in outdoor (primarily GPS) and of map database for indoor (CAD data) to map database for outdoor (GIS data). Without seamless and timely handoffs, the navigation service is unable to recognize the new environment and cannot perform map matching, routing, and geocoding.

Anytime navigation is the UNAVIT’s ability to provide navigation assistance which will be suitable for different times. For example, a route that is optimal during daylight may not be considered quite so optimal during dark. Another example is a route that is suitable when the roads are dry may not be suitable, or even possible, when the roads are wet. Anytime navigation is only important and needed for outdoor navigation and has no impact on indoor navigation. In general, time-dependent factors affecting outdoor navigation are day, week, or season. Issues impacted by day are time (such as navigation during non-rush hours vs. during rush hours), event (such as navigation during holidays or during a major sporting event or concert), and weather conditions (such as dry, rain, or snow). These time-dependent navigation factors are further analyzed based upon mode of travel. In general, while time-dependent factors are generally the same for both driving and walking, their impact could be different as issues of driving on road segments might be different than walking on sidewalk segments at different times.

Anyuser navigation is the capability of UNAVIT to provide navigation assistance that will best meet the needs and preferences of users which may vary greatly. In order to better understand users’ needs and preferences, users are grouped into the following five categories: general population, mobility-impaired, visually-impaired, cognitively-impaired and elderly. Current navigation systems primarily address the needs and preferences of the general population category and fall short in handling the special needs and preferences of users in the other four categories. There are permanent physical barriers in both outdoor and indoor environments that affect mobility of users in each category. Examples of permanent environmental barriers in outdoor sidewalk segments include slope, surface, and curbs; those in indoor hallway networks might include protruding objects and width. There are also temporary environmental barriers in both the outdoors and indoors that affect mobility of users in each category. Examples of such temporary barriers in the outdoors are snow, rain, and darkness; barriers that might exist indoors include construction and out-of-order elevators.

While the current trend in navigation systems and services is model-based, where maps are used to represent real-world navigation environments and navigation decisions are computed algorithmically, the emergence of Web 2.0 technologies (in particular social network systems) are paving the way for a new method of navigation assistance. This new approach is referred to as experience-based where, through social networks, members can share their experiences with POIs, routes, directions, and geofences with other members. The recent development of location-based social networks, where location information is central to the social interaction among members, is facilitating this experience-based navigation assistance approach. Salient differences between model-based and experience-based navigation assistance include: model-based navigation assistance must contain and rely heavily on maps of the navigation environments, whereas maps are optional in experience-base navigation assistance; in model-based navigation assistance, navigation decisions are computed algorithmically, whereas in experience-based navigation assistance recommendations of members are searched to find suitable matches.