Günther Retscher and Michael Thienelt

---

Abstract

In the research project NAVIO (Pedestrian Navigation Systems in Combined Indoor/Outdoor Environments) at our university (Vienna University of Technology), we are working on the improvement of navigation services for pedestrians. We are mainly focusing on the information aspect of location-based services, i.e., on the user's task at hand and the support of the user's decisions by information provided by navigation services. Specifications allow us to select appropriate sensor data and to integrate data when and where needed, to propose context-dependent routes fitting to partly conflicting interests and goals as well as to select appropriate communication methods in terms of supporting the user by various multimedia cartography forms.

In this paper, these tasks are addressed in three different work packages: "Integrated positioning," "Pedestrian route modeling," and "Multimedia route communication." In this paper we will concentrate on the findings of the first work package. For continuous positioning of a pedestrian suitable location, technologies include GNSS and indoor location techniques, cellular phone positioning, dead reckoning sensors (e.g. magnetic compass, gyro and accelerometers) for measurement of heading and travelled distance as well as barometric pressure sensors for height determination. The integration of these sensors in a modern multi-sensor system can be performed using an adapted Kalman filter. To test and to demonstrate our approach, we take a use case scenario into account, i.e., the guidance of visitors to departments of the University. The results of simulation studies and practical tests will confirm whether such a service can achieve a high level of performance for the guidance of pedestrians in urban areas and in mixed indoor and outdoor environments.

1. Introduction

Pedestrian navigation services require continuous positioning and tracking of a mobile user with a certain positioning accuracy and reliability. Especially navigating in urban environments and mixed indoor and outdoor areas is a very challenging task as pedestrians move in spaces where no one of the known location methods works continuously in standalone mode. A solution to the problem can only be found if different location technologies are combined in the sense of a modern multi-sensor system. In this paper, suitable location technologies for pedestrian navigation are identified and investigated.

These technologies include GNSS and indoor location services as well as cellular phone positioning for absolute position determination and dead reckoning sensors (e.g. magnetic compass, gyros and accelerometers) for measurement of orientation and travelled distance from a known start position as well as barometric pressure sensors for height determination.

For location determination of a pedestrian in a multistory building the use of WLAN (Wireless Local Area Networks) is investigated. To achieve an integrated positioning determination with other sensors and a seamless transition between indoor and outdoor areas, a multi-sensor fusion model based on an extended Kalman filter approach is employed.

Finally, in a practical use case scenario, the guidance of a pedestrian from public transport stops to our Department at the Vienna University of Technology is investigated. The results of this study showed that such a pedestrian navigation service can achieve a high level of performance.

2. Integrates Positioning in Navigation Services

A reliable pedestrian navigation service requires the determination of the current user's position using different sensors that are integrated into the system design. In the "Integrated positioning" work package of the research project NAVIO (Pedestrian Navigation Systems in Combined Indoor/Outdoor Environements) the following challenging tasks are addressed:

• The capability to track the movements of a pedestrian in real-time using different suitable location sensors and to obtain an optimal estimate of the current user's position.
• The possibility to locate the user in 3 dimensions with high precision (that includes to determining the correct floor of the user in a multistory building).
• The capability to achieve a seamless transition for continuous positioning determination between indoor and outdoor areas.

Such a navigation support must be able to provide location, orientation and movement of the user as well as related geographic information matching well with the real world situation experienced by pedestrians. The integration of the sensors in a modern multi-sensor system can be performed using a Kalman filter as this algorithm is particularly suited for real-time evaluation. In the following presentation, the state-of-the-art in mobile positioning is discussed and suitable sensors for integrated positioning in a pedestrian navigation service are identified.

2.1 State-of-the-art in Mobile Positioning

Satellite-positioning technologies (GNSS) are employed most commonly for outdoor navigation. In those cases, the achievable positioning accuracies of the navigation system are on the few meters to 10 m level in standalone mode or sub-meter to a few meter level in differential mode (e.g. DGPS). If an insufficient number of satellites is available for a short period of time due to obstructions, then in a conventional approach additional sensors are employed for observation to bridge the absence of satellite signals. For pedestrian navigation, sensors such as a low-cost attitude sensor (digital compass) giving the orientation and heading of the person being navigated and a digital step counter or accelerometers for travel distance measurements can be employed. Using these sensors, however, only relative position determination from a known start position (also referred to as Dead Reckoning DR) is possible and the achievable accuracy depends on the type of tracking sensors used tp detect movement and the position prediction algorithm adopted.

For indoor positioning different techniques have been developed.They offer either absolute or relative positioning capabilities. Some of them are based on short-range or mid-range technologies using sensors such as transponders or beacons installed in the building (see e.g. Klinec and Volz, 2000; Pahlavan et al., 2002). An example is the so-called Local Positioning Systems (LPS) that has an operation principle similar to GNSS. The LPS systems claim to achieve a distance measurement accuracy of about 0.3 to 1 m (see e.g. Werb and Lanz, 2000; Sypniewski, 2000), but no details are given on the test results and the achievable accuracy on position fixing.

Other indoor positioning systems include so-called Active Badge or Active Bats Systems (Hightower and Boriello, 2001). These systems are mainly employed for the location of people and finding things in buildings. Also WLAN (Wireless Local Area Networks) can be employed for location determination. In this case, the signal strength of the radio signals from at least one WLAN access point installed in the building is measured. The location fix is then obtained with trilateration using measurements to several access points or through comparison with in database stored signal strength values from calibrated points (this method is also referred to as fingerprinting). Further information can be found in e.g. (Bastisch et al., 2003; Beal, 2003; Imst, 2004; Retscher 2004b).v

As the indoor radio channel suffers from severe multipath propagation and heavy shadow fading, the fingerprint method provides higher accuracies than trilateration. It is reported that positioning accuracies of about 1 to 3 m could be obtained in a test office building using the fingerprint WLAN positioning method (Imst, 2004).

Another alternative in indoor geolocation applications is the use of ultra wideband (UWB) systems that exploit bandwidths in excess of 1 GHz to measure accurate time of arrival (ToA) of the received signals for estimation of distance (Pahlavan et al., 2002). With results of propagation measurement in a typical modern office building, it has been shown that the UWB signal does not suffer multipath fading (Win and Scholtz, 1998), which is desirable for accurate ToA estimation in indoor areas.v vAlso Bluetooth, originally developed for short range wireless communication, can be employed for locating mobile devices in a certain cell area that is represented by the range of the device, typically less than 10 m. It can be employed for location determination using active landmarks. Locating the user on the correct floor of a multistory building is another challenging task. For more accurate determination of the user's position in vertical dimension an improvement can be achieved employing a barometric pressure sensor or digital altimeter additionally (see Retscher and Skolaut, 2003).

As an alternative for location determination in indoor and outdoor environments, mobile positioning services using cellular phones can be employed. Apart from describing the location of the user using the cell of the wireless network, more advanced positioning methods have been developed. Most of them are based on classical terrestrial navigation methods where at least two observations are required to obtain a 2-D position fix (see e.g. Balbach, 2000; CPS, 2001; Drane et al., 1998; Hein et al., 2000; Retscher, 2002). The achievable positioning accuracy thereby depends mainly on the location method and type of wireless network (GSM, W-CDMA, UMTS).

As advanced and more accurate methods, such as the E-OTD (Enhanced Observed Time Difference) method, require modification of the network as well as installation of additional hardware in the network and reference stations called LMU's (Location Measurement Units), they have not been widely deployed yet. Recent developments have therefore been concentrated on the reduction of network modification. The so-called Matrix method (see Duffett-Smith and Craig, 2004) does not need any additional hardware in the network apart from a SMLC (Serving Mobile Location Centre) where the location determination of the mobile handset is performed. Using this method, positioning accuracies of 50 to 100 m at the 67 % reliability level can be achieved in the GSM network.

2.2 Suitable Sensors for Pedestrian Navigation Services

Suitable sensors and location techniques for pedestrian navigation identified at the start of the project NAVIO. Table 1 gives an overview about the positioning methods and the sensors employed in our project. For absolute position determination primarily GNSS is employed. In the case of no GNSS availability it can be replaced by location techniques using cellular phones or indoor positioning systems (e.g. WLAN positioning). Apart from these sensors, relative DR (Dead Reckoning) sensors are employed for the observation of the travelled distance (from velocity and acceleration measurements), direction of motion or heading and height difference. The observables as well as their accuracies are summarized in Table 1.

Method	Sensor	Observations	Accuracy
GNSS	e.g. Garmin GPS 35 DGPS	y, x, z	6-10 m 1-4 m
Indoor Positioning	e.g. WLAN Positioning IMST ipos	y, x, z	1-3 m
Cellular Phone Positioning	GSM (e.g. Matrix method)	y, x	50-100 m
Dead Reckoning	e.g. PointResearch DRM-III Dead Reckoning Module	y, x z -	20-50 m per 1 km 3 m 1°
Direction of Motion (Heading)	e.g. Honeywell Digital Compass Module HMR 3000	-	0.5°
Acceleration	e.g. Crossbow Accelerometer CXTD02	atan, arad, az	>0.03 ms-2
Velocity from GNSS	e.g. Garmin GPS 35	vy, vx, vz	˜0.05 ms-1 ˜0.2 ms-1
Barometer	e.g. Vaisala Pressure sensor PTB220A	z	1-3 m

2.3 Integrated Positioning Using a Multi-Sensor Fusion Model

An integrated position determination, using observations of all available sensors is rarely performed in most common navigation systems. In vehicle navigation systems for instance the resulting trajectory is determined mainly based on the dead reckoning observations; GNSS is used for updating and resolving the systematic error growth of the DR observations. For guidance of a pedestrian in 3-D space and updating of his route, continuous position determination is required with positioning accuracies on the few meter level or even higher, especially for navigation in multistory buildings in vertical dimension (height) as the user must be located on the correct floor. The specialized research hypothesis of this work package is that a mathematical model for integrated positioning can be developed that provides the user with a continuous navigation support. Therefore appropriate location sensors have to be combined and integrated using a new multi-sensor fusion model. A Kalman filter approach is particular suited for the integration and sensor fusion in real-time. Extending basic filter concepts, a Kalman filter approach which integrates all observations from the different sensors will be developed. The model must be able to make full use of all available single observations of the sensors at a certain time to obtain an optimal estimate of the current user state (i.e., position, orientation and motion). For further information on the multi-sensor fusion model the reader is referred to Retscher and Mok (2004) and Retscher (2004b).

3. Practical Sensor Tests

Practical tests in our research project are carried out for the guidance of visitors of the Vienna University of Technology to certain offices in different buildings or to certain persons. Thereby we assume that the visitor employs a pedestrian navigation system using different sensors that perform an integrated positioning. Start points are nearby public transport stops, e.g. underground stop Karlsplatz in the center of Vienna or railway station Südbahnhof near our university. In the following, results of satellite positioning and first test measurements with the Dead Reckoning Module DRM III from Point Research as well as calibration measurements are presented.

3.1 Satellite Positioning Test Results

Figure 1 shows the GPS measurements for the path from the underground stop Karlsplatz near our University to our Institute building of the Vienna University of Technology in the Gusshausstrasse located in the fourth district of the city of Vienna using two different GPS receivers, i.e., the Trimble GPS Pathfinder Pocket and the Garmin eTrex. The length of the path is approximately 500 m and it starts at the exit of underground station Karlsplatz where open skies provide free satellite visibility. Then the pedestrian walks through a park (i.e., the Resselpark) with trees where satellite signals are frequently blocked over short periods. Both GPS receivers, however, are able to determine the track of the pedestrian with a reasonable positioning accuracy. It can be seen, that the track of the Garmin eTrex receiver is much smoother as this receiver performs some filtering or smoothing to estimate the receiver track compared to the Trimble GPS Pathfinder Pocket which provides the original GPS single point positions. After leaving the park, the path continues in a narrow street (i.e., Karlsgasse) onwards to our Institute building where 5-storey buildings with heights of typically 20 m cause obstructions of the satellite signals. The measurement result from the Garmin eTrex shows an increasing deviation from the true pedestrian path where the maximum deviation in the range of 13 m is reached at the intersection of Karlsgasse with Frankenberggasse.

Then the position changes quite significantly as more GPS satellites become available. In the following, the positions show again a drift from the true path. As the Trimble GPS Pathfinder Pocket receiver does not apply any filtering or smoothing, the positions in the Karlsgasse are much more scattered than with the Garmin eTrex. Maximum deviations from the true path of the pedestrian of up to 25 m are reached and in some parts no position determination is possible. These gaps have to be bridged using dead reckoning observations. At the intersection of Karlsgasse and Gusshausstrasse enough satellites are visible for positioning and the path ends in front of the building where our Institute is located.

Fig. 1: GPS measurements for the pedestrian path from the underground station Karlsplatz to our office building of the Vienna University of Technology.

3.2 Calibration of the Heading Sensor

The relative sensors need to be calibrated and checked before we can use them in a pedestrian navigation service. As an example, Figure 2 shows the set up for the calibration of the heading sensor Honeywell Digital Compass Module HMR 3000. For this purpose the sensor was mounted on top of a theodolite and the azimut was determined using a gyro theodolit. The results showed an offset of 1.8 gon for the heading sensor from the true azimut and the achievable relative accuracy lies in the range of ± 0.13 gon for repeated observations of the same heading with a maximum deviation of 0.44 gon from the true value. The absolute accuracy of the heading sensors shows a standard deviation of ± 0.44 gon.

Fig. 2: Theodolit with gyro GAK 1 from Wild (left) and with heading sensor HMR 3000 (right)

After the calibration the sensor was tested for the heading determination of a walking pedestrian. Figure 3 shows the measurement noise of the heading sensor HMR 3000 and its maximum and mean deviation from the true heading value for three different test persons walking along a straight street over a distance of approximately 146 m. Thereby test person one carried the sensor on the belt and the other two test persons carried the sensor in their hands. The maximum deviations reach values of up to 40 gon for the observations of test person one and 15 gon for the others. The standard deviation of the observations of test person one are in the range of ± 8 gon and for the others in the range of ± 5 gon. From the tests it can be concluded that the accuracies of the heading sensor are suitable for reliable heading observations of a walking pedestrian.

Fig. 3: Measurement noise of the heading sensor HMR 3000 (top) and maximum and mean deviation from the true heading value for three different test persons walking along a straight street (bottom)

3.3 Dead Reckoning Test Results

For measurements, the Dead Reckoning Module DRM III from Point Research (PointResearch, 2004) was employed. The system is a self-contained navigation unit where GPS is not required for operation. It provides independent position information based on the user's stride and pace count, magnetic north and barometric altitude. The module is designed to self-calibrate when used in conjunction with an appropriate GPS receiver, and can produce reliable position data during GPS outages.

The system consists of an integrated 12 channel GPS receiver, antenna, digital compass, pedometer and altimeter. The module is clipped onto the user's belt in the middle of the back and the GPS antenna may be attached to a hat. Firmware converts the sensor signals to appropriate discrete parameters, calculates compass azimuth, detects footsteps, calculates altitude and performs dead reckoning position calculation. A Kalman filter algorithm is used to combine dead reckoning position with GPS position to obtain an optimum estimate for the current user's position and track.

With the dead reckoning module and GPS integrated together, a clear view of the sky is only required for obtaining the initial position fix. The fix must produce an estimated position error of 100 m or less to begin initialization. Subsequent fixes use both dead reckoning and GPS data, so obstructed satellites are not as critical as in a GPS only configuration. The Kalman filter continuously updates calbration factors for stride length and compass mounting offset. The GPS position error must be less than 30 m before GPS data will be used by the Kalman filter, and the first such fix will also initialize the module's latitude and longitude. Subsequently, the filter will use any GPS position fix with an estimated position error of 100 m or less, adjusting stride, body offset, northing, easting, latitude and longitude continually.

The Dead Reckoning Module DRM III was first tested in an open area with GPS satellite visibility. As a test site, pedestrian paths in the park of Schönbrunn Palace in Vienna were chosen. Figure 4 shows the trajectory of the pedestrian as well as GPS and two different dead reckoning measurements. For the dead reckoning measurements the GPS positioning and the calibration of the stride length using the Kalman filter algorithm was deactivated. Without using the filter, GPS measurements are not employed to calibrate the stride length and the dead reckoning module uses the preset value of 800 mm for the stride length. The heading of the user is determined from measurements of a digital compass and a gyro. For the first dead reckoning measurement (No. 1), shown in Figure 4, both sensors were employed to obtain the heading; for the second measurement (No. 2), only the observations of the compass are employed. This results in larger deviations from the trajectory for the second dead reckoning measurements; they range from 17 m over a distance of 150 m and 29 m over 200 m. For the first dead reckoning measurement, the deviations from the trajectory are in the range of 7 m over a distance of 150 m and 20 m over 200 m. It can therefore be recommended that a combination of compass and gyro measurements be employed for heading observation.

Fig. 4: Test measurements with the Dead Reckoning Module DRM III in the park of Schönbrunn Palace in Vienna

An improvement of the dead reckoning measurements can only be achieved if the calibration of the stride length is employed to obtain a better estimate for the travelled distance. For comparison, GPS measurements from the internal receiver of the DRM III module are shown in Figure 4 that reach a maximum deviation of 7 m from the trajectory.

Figure 5 shows the measurement results of the DRM III dead reckoning module and GPS single point positions on a closed loop in the city of Vienna starting from the Resselpark about 160 m along Argentinerstrasse, then 200 m along Gusshaustrasse and 290 m along Karlsgasse back to the start point. The total length of the path is around 550 m. The streets are quite narrow with 5-story buildings with an average height over 20 m causing frequent obstructions of the satellite signals and high GDOP values. As can be seen in Figure 5, the GPS only measurements are quite far away from the true path of the pedestrian along most parts of the track and a reliable match to the correct street would not always be possible. Using the position estimates of the dead reckoning module the resulting trajectory follows the pedestrian track along the greater part of the path and the deviations are only in the range of a few meters.

Fig. 5: Test measurements with the Dead Reckoning Module DRM III along a closed loop on narrow streets in the city Vienna

Due to the large errors of the GPS postions, however, the calibration algorithm of the DRM III fails in the end and the resulting trajectory cannot follow the track of the pedestrian any more. Figure 6 shows the calbration of the stride length in the Kalman filter and it can be seen that the stride length gets smaller and smaller until it reaches nearly 500 mm which is not a matter of fact. In this case, it seems that the weighting of GPS positioning is too high in the Kalman filter calibration process for the stride length.

In our project, an improvement of the current position estimate of a pedestrian using observations of different dead reckoning sensors in combination with GPS and other absolute postioning techniques (see Table 1) should be achieved using a new multi-sensor fusion model based on an extended Kalman filter approach. Further information about this approach can be found in Retscher and Mok (2004) and Retscher (2004b).

4. Conclusion

In our NAVIO research project, the important variables in a pedestrian navigation service are investigated, i.e., integrated positioning, multi-criteria route planning, and multimedia route communication (see Gartner et al., 2004a and b). In practice, a specific pedestrian navigation service will need to identify the requirements for positioning, route planning, and communication. A prototype of the service has been used to guide visitors to the Vienna University of Technology to departments and persons. Further tests will allow us to evaluate and demonstrate the usability of the service, and thus, prove the project's findings.

With the "Integrated Positioning" work package, the integration of location sensors in the sense of a multi-sensor system to achieve a continuous positioning of the user of the service and a seamless transition between indoor and outdoor areas is needed. Suitable sensors and location methods were identified and the basic concept of a multi-sensor fusion model for integrated positioning has been developed (Retscher and Mok, 2004; Retscher 2004b). Special emphasis has been given on the location determination and navigation of a pedestrain in a multi-story building. Currently we are investigating the use of WLAN positioning for location determination in indoor areas.

Fig. 6: Calibration of the stride length using GPS observations in the Kalman filter of the DRM III Dead Reckoning Module

The second work package of the project NAVIO on "Pedestrian route modeling" has dealt with the ontological modelling of navigation tasks, deriving well founded criteria and optimization strategies in route selection; and the third work package on "Multimedia route communication" is working on models for context-dependent communication modes of route information. In general, it can be said that the results of the NAVIO project will contribute to the improvement of modern (pedestrian) navigation services.

---

top