2. MAP DATABASE

As a core module of PerNavs, a road network database supports almost every other module of a navigation system (Skog and Handel, Reference Skog and Handel2009). The map matching module relies on road network data to determine a best estimate of current vehicle's position. The geocoding module uses road network data to interpolate the coordinates of a given address. The routing/direction module relies on road network data to calculate an optimal route and generate directions on it.

Road network data used in PerNavs includes geometries, topologies, and attributes, represented in the vector data model. A road network database containing basic attributes (e.g., street name, address range, length, street type) for geocoding and routing purposes is called a routable map. A road network database containing a complete set of attributes (e.g., orientation, landmarks, real-time traffic) for all navigation functions is called a navigable map. Today, many digital map data providers create and provide road network data and other map related content. Generally, map data providers can be grouped into three categories: (a) government and non-profit organizations, (b) commercial mapping companies, and (c) community mapping projects. Map data providers and their products, navigable and routable maps, are shown in Figure 1.

Figure 1. Road network databases.

2.1. Sources of Errors in Map Databases

Road network data errors come from multiple sources during the map generation process which has the following steps: data acquisition, data automation, and map creation, as summarized in Figure 2.

Figure 2. Sources of errors in digital maps.

Data acquisition is an extensive task and error prone. In addition to common acquisition techniques for road network data (i.e., field survey, paper map conversion, and satellite image feature extraction), a newer approach for collecting road data in a large geographical extent for creating network databases is through mobile mapping systems (Karimi and Grejner-Brzezinska, Reference Karimi and Grejner-Brzezinska2004).

Paper maps can either be digitized or scanned. Typical accuracy of paper map digitization ranges between 1·5 m to 15 m from its true position (Fekpe et al., Reference Fekpe, Windholz, Beard and Novak2003). Typical errors in scanning come from the map itself and the tracing method (Chang, Reference Chang2010). High-resolution aerial and satellite images are alternative sources of data for extracting road networks and updating road network data. Typical accuracy of aerial photographs, taken by high quality stereo plotters, ranges between 0·08 m and 0·13 m with image scale of 0·025:30·48 m (Fekpe et al., Reference Fekpe, Windholz, Beard and Novak2003).

The map creation process involves a series of choices on how real-world features should be represented in a digital map. Each decision may introduce uncertainties to the overall process. The steps in the map creation process include choice of map scale, level of generalization, projection, datum, and coordinate system. Maps suitable for car navigation systems and Intelligent Transportation System (ITS) applications are large-scale, about 1:5,000 for urban areas and 1:10,000 for rural areas (Zhao, Reference Zhao1997). A choice of generalization usually distorts details of map features; for example, the street centrelines model might eliminate small curves of actual road shapes. The choice of map projection, horizontal and vertical datum, and coordinate system may introduce some distortions and distance measurement errors.

3. GEOCODING

Geocoding is the process of assigning geographic coordinates to a given place name by comparing its description to the descriptions of location-specific elements in the reference database. For a comprehensive review of the geocoding process refer to Goldberg et al. (Reference Goldberg, Wilson and Knoblock2007), Rushton et al. (Reference Rushton, Armstrong, Gittler, Greene, Pavlik and West2006), and Zandbergen (Reference Zandbergen2008, Reference Zandbergen2009). Geocoding in PerNavs is required to locate points of interest (POIs) and origin-destination pairs for route planning.

PerNavs allow users to specify a desired destination in three ways: placing a point on the map, entering an address/intersection name, or selecting a POI from lists of directories. Usually, POIs in PersNavs are either pre-geocoded or geocoded on the fly. In the pre-geocoding method, coordinates of POIs or major landmarks (e.g., airport, parks, parking lots, and shopping centres) are stored in a database. On-the-fly methods find coordinates of an address at the time the address is provided.

3.1. Sources of Errors in Geocoding

Geocoding uncertainties are mainly associated with choices of techniques (street geocoding, rooftop geocoding), algorithms and reference databases. (Roongpiboonsopit and Karimi, Reference Roongpiboonsopit and Karimi2010a, Reference Roongpiboonsopit and Karimi2010b). In this paper, uncertainties associated with the street geocoding technique, since it is widely used in PerNavs, are focused. Figure 3 summarizes sources of errors for street geocoding.

Figure 3. Sources of errors in street geocoding.

3.1.1. Reference Database

Street geocoding uses road network data in a reference database. Following the US address model (i.e., house number, street prefix, street name, street suffix, postal codes, city, state, and country), the attributes that most likely introduce errors to geocoding results are street names, house number ranges, and polarity (i.e., even/odd house numbers assigned to left/right side of street) since any changes on these may not be reflected in reference databases immediately. A reference database containing many of problematic attributes can cause low match rates and possibly low positional accuracy (Karimi et al, Reference Karimi and Grejner-Brzezinska2004).

Geometrical accuracy of street centrelines and intersection nodes directly influences positional accuracy of geocoded results. Street resolution, which is the sampling frequency of shape points along each segment, is another source of errors. A low resolution segment results in a coarse representation of the actual street and a rough estimate of the total length of the segment.

Completeness of street centrelines in reference databases is another important factor impacting match rates. Even when the best geocoding algorithm is employed, missing major street centrelines associated with many addresses in the reference database can cause low match rates.

3.1.2. Geocoding Algorithm

A geocoding algorithm involves three steps: address standardization and normalization, attribute matching, and location estimation. Approaches, assumptions, and parameters in each step introduce uncertainties in geocoding results. Karimi et al. (Reference Karimi, Durcik and Rasdorf2004) showed that using the same reference database in different geocoding algorithms may not have a significant impact on results.

Address standardization and normalization converts an input address to a format that is understandable and compatible with the reference database. The geocoder must be robust and have provisions for unanticipated errors associated with input addresses. A simple standardization and normalization method (e.g., simple token parsing) leads to lower attribute matches than advanced methods, such as hidden Markov models, that can cope with many types of misspellings and misplacements rather well (Christen et al., Reference Christen, Churches and Willmore2004, Yang et al., Reference Yang, Bilaver, Hayes and Goerge2004).

Attribute matching is the first step in geocoding that finds the correct street for interpolation. Different approaches, such as word stemming, Soundex, and relaxation of matching requirements, can be applied to improve finding a match in the reference database (Churches et al., Reference Churches, Christen, Lim and Zhu2002, Drummond, Reference Drummond1995, and Nicoara, Reference Nicoara2005). A scoring scheme for quantifying quality of matches is applied which usually returns a score ranging between 0 to 100. A minimum matching score for examining street centreline candidates can be assigned. Assigning an appropriate minimum score is important because a too low score can result in higher match rates but lower positional accuracy of the output (Bonner et al., Reference Bonner, Han, Nie, Rogerson, Vena and Freudenheim2003, Rushton et al., Reference Rushton, Armstrong, Gittler, Greene, Pavlik and West2006).

Location estimation aims to interpolate the coordinates of the parsed address using the geometry and attributes of the selected street segment. In addition to the values of attributes (i.e., address range and polarity) necessary for interpolation (Cayo and Talbot, Reference Cayo and Talbot2003, Levine and Kim, Reference Levine and Kim1998), the algorithm has a set of underlying assumptions and internal parameters defined to improve the positional accuracy of the output (Zandbergen, Reference Zandbergen2009).

Two common assumptions in street geocoding are parcel homogeneity and address range existence. The parameters of an interpolation algorithm that can impact positional accuracy are side offsets and end offsets. An interpolation algorithm assumes that all addresses are located at a certain distance away from a street centerline and end nodes. Applying unreasonable offsets can magnify distance errors. However, Zandbergen (Reference Zandbergen2007) reported minor differences on the positional error distribution when offset values were varied between 0 to 50 m.

4. POSITIONING

The positioning module of a PerNav is responsible for continually estimating geographic coordinates of a vehicle's current location. Coordinates obtained by the positioning module are used to locate the vehicle's position on a map by the use of map matching techniques. The map-matched points then allow follow-up functionalities in PerNavs, including computing a route from the vehicle's current location to a destination, re-calculating a route, giving turn-by-turn directions, and searching nearby POIs.

Currently, several positioning technologies are available for location-based services and applications, including Global Navigation Satellite System (GNSS), Dead Reckoning (DR), Wi-Fi, cellular networks, Ultra Wide Band (UWB), Radio Frequency Identification (RFID), and Bluetooth positioning (Retscher and Kealy, Reference Retscher and Kealy2006, Rizos, Reference Rizos2005). Of available positioning technologies, GNSS is predominantly utilized in PerNavs. However, GNSS suffers from losses of satellite signals in difficult areas such as indoors, urban canyons, heavy canopies, and tunnels. To overcome GNSS drawbacks and increase continuity and availability of positioning solutions, GNSS is often augmented by DR systems in PerNavs (Hide et al., Reference Hide, Moore, Hill and Park2006, Kao, Reference Kao1991, and Zhao et al., Reference Zhao, Ochieng, Quddus and Noland2003). In this paper we focus on the uncertainties associated with GNSS as it is commonly employed in PerNavs.

GNSS is an absolute radio-navigation positioning systems and currently the only fully operational GNSS is GPS. Russia's GLONASS, Europe's Galileo, and China's Compass will be available with full operation in the near future. For more comprehensive details on GNSS refer to Drane and Rizos (Reference Drane and Rizos1998), Hofmann-Wellenhof et al. (Reference Hofmann-Wellenhof, Lichtenegger and Wasle2008), and Kaplan and Hegarty (Reference Kaplan and Hegarty2006) .

4.1. Sources of Errors in Positioning

Figure 4 summarizes major sources of errors in GNSS positioning. GNSS accuracy depends on the level of measurement errors and satellite-receiver geometry. Some of these measurement errors could be reduced or eliminated by GNSS augmentation techniques (e.g., differential GNSS). Poor satellite geometry, on the other hand, cannot be corrected.

Figure 4. Sources of errors in positioning.

Measurement errors can be categorized into three groups: satellite-dependent, receiver-dependent, and signal propagation. Satellite-dependent biases consist of orbital bias and satellite clock bias. Receiver-dependent bias is primarily clock error due to the use of inexpensive quartz crystal oscillators, which can cause the difference between the receiver clock time and the satellite clock time. Signal propagation biases occur due to atmospheric and multipath effects. The ionosphere and troposphere cause slower velocity for the propagating signal than when it travels in outer space.

The multipath effect occurs whenever the signal takes an indirect path, reflecting from nearby objects, rather than the direct path from satellite to receiver. The delay can cause error for code pseudorange between 10 to 20 m and may increase to 100 m in severe areas. The multipath effect in PerNavs is more challenging due to varying surroundings from place to place, and introduces the most significant bias to the final position solution.

To combine contributions by different sources of measurement errors described earlier, user equivalent range error (UERE) is defined. Assuming that individual errors are uncorrelated, UERE associated with a satellite is computed as a square root of the summed squares of the individual errors (σ_UERE). For further reading on the amount of each measurement error and UERE for different GNSS types refer to Hofmann-Wellenhof et al. (Reference Hofmann-Wellenhof, Lichtenegger and Wasle2008) and Kaplan and Hegarty (Reference Kaplan and Hegarty2006) .

Satellite geometry is an amplification factor of the measurement errors that cannot be corrected by any means. The parameter for determining satellite geometry is dilution of precision (DOP) (Langley, Reference Langley1999). Based on different components used in DOP calculation, several definitions of DOP are possible. The most common DOPs for ground applications are positional DOP (3D coordinates) and horizontal DOP (2D coordinates).

5. MAP MATCHING

Map matching is the process of determining current location of the vehicle on the road network after obtaining its geographic coordinates via the positioning module. In general, map matching is a two-step process. In the first step a correct road segment that the user is travelling on is identified and in the second step a location on the identified segment is pinpointed. A map matching algorithm generally utilizes information available onboard, such as position data and road network. This information, as discussed earlier, is imperfect and contains errors.

The level of map-matched results depends on how the algorithm is designed to tolerate uncertainties of the information sources it uses (i.e., positioning and road network). Advanced map matching algorithms can usually handle most ambiguous cases by reducing errors of map-matched points. Karimi et al., (Reference Karimi, Conahan and Roongpiboonsopit2006) provided a methodology to predict and evaluate performance of different map matching algorithms.

5.1. Sources of Errors in Map Matching

Map matching uncertainties come from three main sources: positioning module, digital road network, and map matching algorithms, as summarized in Figure 5. In urban areas where road networks are dense, most map matching algorithms cannot correctly identify correct road segments due to high uncertainties of GNSS positions. For instance, a field test in London found that the GPS error was more than 50 m (Zhao et al., Reference Zhao, Ochieng, Quddus and Noland2003), and in Hong Kong it was more than 80 m (Chen et al., Reference Chen, Li, Yu and Chen2003). Even though DR may be used to augment GNSS in PerNavs, drift errors may arise if the system is not calibrated for a period of time. Using the drifted DR points can significantly impact map-matched results. Distance travelled between two points is used by some map matching algorithms to estimate points on the selected segment. Thus, high uncertainty of distance information, either obtained from odometer sensors or derived from GNSS points, may cause errors in map-matched positions. Heading information can be used to identify a road segment, select the next travelling road segment only at the intersection, or determine new candidate segments whenever new points are obtained. Variation in heading may impact map matching solutions depending on how the algorithm utilizes this information. Chen et al. (Reference Chen, Li, Yu and Chen2005) showed that GPS position errors contribute 4% of mismatching positions, 22% of which are caused by distance measurement errors and 50% caused by heading errors.

Figure 5. Sources of errors in map matching.

6. ROUTING/DIRECTION

Routing and direction in PerNavs compute user-preferred routes and step-by-step instructions on how to travel on routes, respectively. Typical route preferences are shortest distance, fastest time, avoid highway, and avoid toll (Pang, Reference Pang, Takashi, Yokotab and Takenaga2002). Routing is an optimization problem that searches a road network for best routes between pairs of addresses. Several algorithms for solving routing problem exist including Dijkstra's algorithm (Reference Dijkstra1959) and Floyd-Warshall's algorithm (Pemmaraju and Skiena Reference Pemmaraju and Skiena2003). Generally, routing algorithms are either exact or heuristic. Exact routing algorithms can guarantee best solutions (routes) but with slow time complexity. Heuristic algorithms are an alternative to exact algorithms typically reduce the solution space in order to improve time complexity; for example, A* (Hart et al., Reference Hart, Nilsson and Raphael1972) and ORCA (Karimi, Reference Karimi1996). One drawback with heuristic algorithms is that they do not guarantee best solutions (Johnsonbaugh and Schaefer, Reference Johnsonbaugh and Schaefer2003).

Research in direction generation has been studied mainly as a field in cognitive science, especially in wayfinding. An example of direction generation is GUARD (Generation of Unambiguous, Adapted Route Directions) by Richter (Reference Richter2007) that automatically determines references to different types of landmarks into context specific route instructions. Generally, three types of information are used in PerNavs for generating directions: street names, street length, and orientation at decision points.

6.1. Sources of Errors in Routing/Direction

Uncertainty in routing refers to differences between routes computed and those requested by users. Uncertainty in direction refers to directions that contain incorrect, inaccurate, or outdated information. The primary sources of errors in routing/direction are summarized in Figure 6.

Figure 6. Sources of errors in routing/direction.

6.1.1. Routing

In routing, weight function computes weights (costs), based on user's preferences, for road segments. Considering that weight functions utilize attributes in map databases, directly or indirectly, their results depend on map database errors. For example, with travel time as a preferred criterion, erroneous road segment speed limits will cause errors in calculating weights.

Route computation consists of three main steps: obtaining origin position, obtaining destination position, and computing route between origin and destination. The vehicle's position in PerNavs is usually considered as the origin, which is obtained from the map matching module and thus susceptible to errors of map matching. Destination can be obtained through the geocoding module, and is thus susceptible to errors of geocoding and map database.

Heuristic routing algorithms may introduce uncertainties which are not issues in exact the routing algorithm. In addition, geometrical, topological, and attribute errors in road network databases can cause errors in routing solutions; for example, missing road segments, incorrect orientation (one-way or two-way) of road segments, or missing intersection nodes.

6.1.2. Direction

Direction generation in PerNavs involves two main steps: generating direction from origin to destination and retrieving turn-by-turn instruction in real time based on the vehicle's position. Uncertainties of direction mainly associate with road attributes. The main sources of errors in the first step of direction generation are segment name and segment length. The sources of errors in the second step of direction generation are associated with the vehicle's position determination at each time epoch using the map matching module and distance estimation to the next decision point based on the vehicle's position, speed, and current road segment length.

6.2. Measuring Routing/Direction Errors

To measure errors of the routing and direction modules, we define two sets of parameters, one for measuring route errors and one for direction errors.

6.2.1. Route Error Measures

Three parameters for route uncertainty are: weight error (w _e), route precision (R _prec) and route completeness (R _comp), which can be measured from individual computed routes.

Weight error is the average of normalized differences between weights of segments in the computed route and weights of segments in the true route. True routes are the baseline routes preferred by the users. Weight error can be calculated as follows:

(1)

where w _ci is the weight on the i ^th segment of the computed route, w _ti is the weight on the i ^th segment of the true route, and n is the number of segments in the true route. The segments of the computed routes that are not contained in the true route are discarded since they cannot be compared against the baseline.

Route precision is a measure of exactness of the computed route comparing to the optimal route (the true route). It is defined as the ratio between the number of common road segments in the computed route and in the actual optimal route and number of road segments in the actual optimal route, calculated as follows:

(2)

where P _c is the set of road segments in the computed route, P _o is the set of road segments in the optimal route.

Route completeness is a measure of completeness of the computed route compared to the optimal route. It is defined as the ratio between the number of common road segments in the computed route and in the actual optimal route and number of road segments in the computed route, calculated as follows:

(3)

Thus, if R _prec=1 and R _comp=1, the computed route is the same as the optimal route; otherwise, there is uncertainty associated with the computed route.

6.2.2. Direction Error Measures

The parameters for direction uncertainty are: distance error (e _d), topological error (e _t), and attribute (landmark) error. In order to compute these parameters, the computed route is assumed to be correct and the true direction along the given computed route is used as the baseline direction.

Distance error is the total sum of differences between distances provided in the computed direction and actual distances among entities (e.g., between user's location and landmarks). It is calculated as follows:

(4)

where d _cj is the j ^th distance provided in the direction, d _tj is the actual j ^th distance in the computed route, and n is the number of times the distances are provided in the direction.

Topological error is the difference between the number of turns provided in the direction and the number of true turns in the computed route. It is calculated as follows:

(5)

where T _c is the total of number of turns provided in the direction and T _t is the total number of true turns on the computed route.

Attribute (landmark) error is the discrepancy between the landmarks provided in the direction and the actual landmarks on the computed route. It is calculated as follows:

(6)

(7)

(8)

where L _c is the set of computed landmarks and L _t is the set of actual landmarks. All elements in L _c must exist in L _t, otherwise the information about the landmarks in the direction is incorrect.

7. NAVIGATION UNCERTAINTY MODEL

This section presents an understanding of uncertainty in navigation by analyzing the impact of uncertainty in each module on overall uncertainty in PerNavs. Of the possible approaches for analyzing uncertainty in navigation, a Bayesian Network (BN) which is a probabilistic graphical model, is employed to analyze uncertainty propagation in a PerNav. The objective of employing a model like BN is to provide PerNav developers with a tool for explaining the performances of their products to end users, assisting them in making appropriate navigation decisions. The BN structure for PerNavs, called Navigation BN (Nav-BN), is shown in Figure 7. Nav-BN is composed of thirteen variables, represented by nodes, which are classified into three groups: specific, modular, and overall. Specific variables represent uncertainties associated with a particular navigation module. Modular variables represent the overall uncertainty of each navigation module. Overall variable represents the total uncertainty in a PerNav. In this particular design, seven nodes are specific variables, five nodes are modular variables, and one node is overall variable. To simplify the network, variables are provided with two possible states: confidence and not_confidence. Each node is defined as follows:

• • Attribute is the level of confidence in attribute data, stored in the map database, that meets the required accuracy;

• • Geometry is the level of confidence in geometrical data, stored in the map database, that meets the required accuracy and completeness;

• • Topology is the level of confidence in topological data, stored in the map database, that meets the required correctness and completeness;

• • Map DB is the overall confidence in map database influenced by Geometry, Topology, and Attributes;

• • Geocoding Algorithm is the level of confidence in geocoding algorithm that generates correct results;

• • Geocoding is the overall confidence in the geocoding module influenced by Map DB and Geocoding Algorithm;

• • Positioning is the overall confidence in the positioning module;

• • Map Matching is the overall confidence in map matching, influenced by Map DB, Positioning, and MM Algorithm;

• • Weight Function is the level of confidence in the weight function that produces desired costs meeting users' preferences;

• • Routing Algorithm is the level of confidence in routing algorithm that produces routes satisfying users' preferences;

• • Routing/Direction is the overall confidence in computed route and direction, influenced by Map DB, Weight Function, Routing Algorithm, and Geocoding;

• • Real-Time Guidance is the overall confidence in real-time navigation performance that a PerNav provides correct and satisfactory solutions.

Figure 7. A Bayesian network for errors in PerNavs with initial probabilistic values.

Nav-BN requires prior information tables (PIT), or knowledge, in the form of probabilities to indicate possibilities of the confidence levels for the specific variables and the Positioning variable. For example, a PerNav employs a positioning sensor that can estimate acceptable positions with 80% confidence, as shown in Figure 7 at the Positioning node. Nav-BN also requires conditional probability tables (CPTs) for the modular and overall variables for representing changes on the confidence levels given causes. Figure 8 shows an example of CPT for Map DB variable with initial values. Generally, there are two possible approaches to estimate values in PITs and CPTs, which are estimated from collected data and expert judgment. Collected data used for measuring performances of each module during the design and evaluation process of PerNavs can be used to estimate the probabilistic values of both PITs and CPTs. Alternatively, probabilistic values can be estimated by learning from users' experiences using PerNavs. Figure 7 shows estimated probabilistic values of a Nav-BN for a PerNav based on the authors' judgment. The performance confidence of this particular PerNav is, on average, 79%, which is directly influenced by the uncertainty associated with the map matching and the route/direction modules.

Figure 8. An example of a conditional probability table (CPT) for the Map DB variable.

Nav-BN can benefit both PerNav developers and end users in several ways. Nav-BN can help developers better understand uncertainty associated with each module and the overall navigation performance at the Real-Time Guidance node. They can also infer a confidence level in each module if the confidence of Real-Time Guidance is fixed as a requirement. The inferred confidence level of each module can assist developers in choosing suitable database, positioning sensors and algorithms. Nav-BN benefits end users by helping them make appropriate navigation decisions. Nav-BN can provide periodic estimates of navigation performance by observing and measuring the confidence level of position data in real time. For example, if the level of confidence in positioning solutions is known through errors of estimated coordinates (x, y), the map matching module can immediately update the confidence results accordingly, which in turn influences the overall real-time guidance confidence.

8. SUMMARY

In this paper we discussed the importance of understanding uncertainty in navigation by developers and end users. We discussed and analyzed uncertainties associated with each of the five modules (map database, geocoding, positioning, map matching, routing/direction) of PerNavs and how uncertainties of each would propagate to some or all other modules. Uncertainties of each module were analyzed and their sources were discussed. Clearly, a map database is the foundation of a PerNav and its uncertainties propagate to all other modules which impacts subsequent processes. We also presented a Bayesian network model, called Nav-BN, as one possible approach for capturing each module's uncertainty and realizing the impact of uncertainty propagation through modules.

Even though this paper has addressed several issues of uncertainties in navigation, many open issues still remain for future research. One area of future research is to experiment with the presented Bayesian network model to find its suitability and compare it with other possible approaches. While this research area will be of interest to PerNav developers, exploring means of communicating uncertainty in navigation to PerNav end users is another research topic.