Session B3, Paper #1

Multi-sensor Fusion Using a Kalman Filter and Knowledge-based Systems
G. Retscher, Institute of Geodesy and Geophysics, Vienna University of Technology, Austria

Navigation applications require the integration of different sensors to be able to perform continuous position determination of the user. Apart from GNSS, alternative technologies such as Wi-Fi, UWB, RFID and aiding sensors such as MEMS acclerometers and gyros as well as magnetometers, low-cost INS, etc. can nowadays be integrated in a multi-sensor system. Sensor fusion for multi-sensor navigation systems is usually based on a Kalman filter. As a central element of the location determination module the Kalman filter provides an estimate of the current state of the user in real-time. Observation errors or an inadequate dynamic model can cause unsatisfactory filter results (e.g. large deviations of the current location from the truth) which can lead to a divergence of the filter in the worst case. Using a knowledge-based pre-analysis of the observations and an appropriate stochastic model of the Kalman filter such cases can be prevented. For instance, gross errors and outliers in the observations can be detected and eliminated before the observations are introduced into the filter. The knowledge-based component can handle the following tasks:
- Pre-filtering of all observations of the different location sensors, - selection of an appropriate dynamic filter model, - calibration of the multi-sensor system, and - management of the sensors.

The pre-filtering of the sensor observations runs parallel to the data acquisition and provides suitable observations for the following central Kalman filter. The knowledge-based component estimates from the obtained velocity and acceleration measurements the current user´s dynamics (e.g., standing, walking, running, etc.) and from the observations of the heading sensors the current geometry elements of the user´s trajectory (e.g., if it is a straight line or arc). Depending on this estimation, the dynamic filter model is selected. The system calibration consists of the initialization of the multi-sensor system in the beginning and necessary calibrations during operation to reduce the sensor drifts. The management of the sensors handles practical issues during operation, e.g. the activation of power safe modes for sensors which are currently not in use (e.g. deactivation of the GNSS sensor if the user moves indoors).

In this paper, this approach for multi-sensor fusion is discussed in detail. As a use case, the navigation of a pedestrian in a combination of an urban outdoor environement and an indoor environement is investigated. Field test results show that a pedestrian user can be located with a positioning accuracy in the range of 2 to 5 meters using such a multi-sensor approach.

[Return to Program]

Session B3, Paper #2

Estimating Motion Parameters of Head by using hybrid Extended Kalman Filter
S. Heo, O. Shin, C.G. Park, Seoul National University, South Korea

The problem of an aircraft pilot has grown because the avionic system with modern high techniques has been developed very rapidly. This complexity of use of the system reduces pilots´ ability to concentrate on attacking targets in battle or on controlling the aircraft. Many technologies have been developed to solve this problem. If a pilot can control targeting system or avionic system without seeing the control panel, we can severely improve pilot´s capability. In this case, the key solution of this problem is to estimate the motion of a pilot, especially the motion of pilot´s head. A helmet tracker system estimates the motion of the head. In particular, helmet tracking system is tightly related with head mounted display system and the more combined systems like weapon cueing system. These systems can provide several crucial advantages to the pilot to aid pilot´s situational awareness. In Aerospace field, the representative types of a head tracker are magnetic and optical types. The magnetic head tracker has the advantage of a small head-mounted sensor and high accuracy, but it is sensitive to distortion by metallic objects. The optical system has the advantage of low cost, but it is hard to implement because of high data throughputs and computational expense. Recently, with advancements in computing technology and digital image equipment, researchers have studied the optical head tracker actively. But it still has problems that suffer from a notorious lack of robustness and high computational expense. Especially, in case of tracking rapid motion, its low sample frequency (lower than 30Hz) can cause failures in vision tracking .

To overcome rapid motion problem, we extend our previous work of pure vision based tracking system to hybrid tracking system with two measurement channels of vision and inertial sensors. Inertial sensors are widely used for motion tracking. These sensors are self-contained and can be sampled at high rates (~1kHz). The latter characteristic makes them suitable for sensing the rapid motion. However, inertial sensors only measure motion rates or accelerations. The signal must be integrated to produce position or orientation. Noise or bias in the sensor signal integration produces a drift in the attitude computation that accumulates with elapsed time. To correct the accumulated drift, periodic measurements from other sensors must provide absolute pose data. With hybrid system, we estimate the motion of head based on a sequence of noisy images and inertial sensor data. The vision-based tracking system consists of infrared LEDs on the pilot´s helmet and infrared cameras, with a computer for signal processing. Infrared LEDs and infrared stereo cameras are used because they prevent the system from being affected by the light of cockpit devices. The image data of the helmet´s infrared LED is used to estimate the 3D motion of the pilot´s head with low frequency. The inertial based system uses IMU and estimate the motion of the pilot´s head with high frequency. A number of theoretical and experimental studies lead us to a framework with a two-channel motion-filter structure.

The two channels, one for the measurement from image sequence and the other for the measurement from IMU, process independently with different sample rates of each system. Because of owing the nonlinearity in the state model, we implement the system with an Extended Kalman Filter (EKF). By modeling the dynamics of the system as a function of time, the motion parameter of head can be extracted from the hybrid measurement. This algorithm uses image processing techniques of computer vision, inertial navigation techniques and filtering techniques to determine the position and attitude of the pilot´s head. The algorithm has two parts: the pre-processing to convert the measurement data to the motion parameter and post-processing to predict the state for motion parameter estimation. In pre-processing procedure, we convert the input image data from the stereo camera system to motion parameter. After a new frame is received from two cameras, an image segmentation algorithm identifies the 2-d coordinate of every blob feature. Then, 3-d position is computed for each correlated 2-d features via projective triangulation using the epipolar line and the geometric constraints. The resulting 3-d point is examined to find sub-structures (triangle pattern) that are similar to a pre-calibrate target by geometric hashing technique. In post-processing procedure, its position and orientation with respect to the tracker´s world coordinate system is calculated from the image data and the inertial sensor data. Then the result of motion parameter estimation is fed into a recursive filter. And the filtered result is handed to the pre-processing procedure to be used in the pattern matching process. The hybrid EKF has general framework except for that measurement comes from the two channels sharing a common prediction module. The filter has a predictor-corrector structure. When new measurement data comes, we first predict the filter state based on the prior state and then correct the prediction using the measurement data. In this process, it is important where the measurement data comes from. We implement the real system and Simulations with real sensor data has been conducted. The result show the successful tracking ability at the situation of rapid motion change.

[Return to Program]

Session B3, Paper #3

Using OrthoSLAM and Aiding Techniques for Precise Pedestrian Indoor Navigation
C. Ascher, C. Kessler, M. Wankerl, G.F. Trommer, Institute of Systems Optimization, University of Karlsruhe, Germany

An integrated pedestrian navigation system (IPNS) for precise indoor localization and mapping is presented in this paper.
Reliable information about personnel positions and escape routes is a crucial factor in many security or first responder missions. Especially in indoor scenarios in previously unknown environments, precise localization within the explored surroundings is essential for effective coordination. Therefore, a robust and accurate indoor IPNS with mapping capabilities enables fast and successful missions and reduces risk for the deployed personnel.

However, the mentioned applications make high demands on navigational hard- and software. Tracking highly dynamic motions is required as well as providing a long-term accurate navigation estimation, even without reliable satellite navigation signals. The IPNS has to be portable, light and small, which leads to limited computational power being available. Deployment in unknown environments requires use of exteroceptive sensors and mapping techniques.

Our proposal is an IPNS comprising two inertial measurements units (MEMS IMUs), mounted at the foot and the torso, a magnetometer, a barometer and a two-dimensional laser scanner. A first navigation solution is obtained by a Strapdown approach, with Zero Velocity Updates used as aiding technique for the foot mounted sensor. This standard technique shows already promising results considering the use of MEMS sensors. But while using Zero Velocity Updates on the foot system, it is difficult to integrate this navigation solution with vision sensors which cannot be foot mounted due to high foot dynamics. This yields to the use of a second IMU, fixed to the laser sensor on the torso. The navigation solution of this torso system is also obtained by a Strapdown approach to record the dynamics of the laser and it is aided with both, dead reckoning and the navigation solution from the foot. Finally barometer and magnetometer measurements (torso mounted) yield to corrections in heading and height respectively. Although very promising results have been obtained, linearly increasing position errors occur due to magnetic disturbances and other perturbations. So we propose the use of a light weight laser scanner, fixed to the IMU on torso.

The laser scanner enables mapping of the surrounding structure and guarantees long-term accuracy of the position and attitude estimation. The scan data is processed using an Orthogonal Simultaneous Localization and Mapping (OrthoSLAM) technique. In this approach, a reduction of required computational power is reached by considering only straight and perpendicular structures. The laser scanner provides range vs. angle measurements. Corrupted measurements are detected and eliminated in a pre-processing step. Lines are extracted from the laser scan data using an Iterative End Point Fit algorithm. An internal map of orthogonalized lines is updated and corrected with the scanned lines. Tight integration of navigational data increases the robustness of the line association algorithm. Especially during phases without enough visible lines, combining the two subsystems is of elementary importance. The distances of horizontal and vertical lines to corresponding baselines are used as states in a Kalman Filter. OrthoSLAM exploits the fact that man-made buildings consist of orthogonal structures to a large extent and provides long-term stable navigation aiding. Focussing on the observed lines and neglecting unnecessary details at an early processing step reduces the computational cost compared to other SLAM methods. Therefore, this method is targeted to the special conditions of pedestrian indoor navigation.

First results indicate that the combined 2-IMU/magnetometer/barometer/laser system can meet the challenging requirements of pedestrian indoor navigation. The capabilities of our approach will be demonstrated using post-processed data obtained in real-world test scenarios.

[Return to Program]

Session B3, Paper #4

Integrate Attitude Determination Scheme of Single Baseline and Low-cost Three-axis Magnetometer
C. Zhai, W. Jin, B. Wang, Y. Zhang, X. Zhan, Institute of Aerospace Science and Technology, Shanghai Jiao Tong University, China

When the receivers of Global Positioning System (GPS), Global Orbiting Navigation Satellite System (GLONASS) and other such systems are equipped with multiple antennas, they can give attitude information. In many previous researches, the carrier phase differencing measurement equations were built in the earth-centered, earth-fixed (ECEF) coordinate, and then the coordinates were transferred in order to obtain final two or three dimensional vehicle attitude angles (yaw, pitch and roll) between body frame (BF) and local level frame (LLF)
.
The phase differences between signals received by the different antennas now constitute the key measurement. Since carrier phase difference measurements are ambiguous because of the unknown number of carrier signal cycles received, the estimated attitude is in principle ambiguous as well. Therefore, the resolution of the signal cycle ambiguity becomes a necessary task before determining the attitude.

In this approach, four works are highlighted. Firstly, based on the single differencing (SD) carrier phase equations established in LLF, a new algorithm is presented to resolve vehicle attitude determination problems in real-time. Secondly, presumed that the cycle integer ambiguity is known, the measurement equations have attitude analytical resolutions by simultaneous single difference equations of two navigation satellites in-view. In addition, the algorithm is capable of reducing the search integer space into countable two dimensional discrete points and the ambiguity function method (AFM) resolves the adaptive function within the analytical solutions space. Thirdly, attitude information provided by the magnetometer fastens the AFM processing. Therefore the procedures have very low computation consumption and time is saved greatly. Finally, the integrated scheme and filter algorithm of single-baseline and magnetometer are introduced to assess the integer ambiguity initialization and final attitude determination.

The proposed algorithm for GPS resolution attitude determination is validated using many static and dynamic ground tests. The experimental results have demonstrated that the proposed approach is effective and can satisfy the requirement of real-time application in cases of GPS.

[Return to Program]

Session B3, Paper #5

Adaptive Updating Strategy for GNSS/IMU Integration
M. Lu, P. Li, Z. Feng, Tsinghua University, China

GNSS / IMU integration algorithms, such as Extended Kalman Filter (EKF), generally contain two major steps: prediction (or estimation) and update (or correction). In addition, the update frequencies of estimation and correction are usually constants, determined by the data updating rate of IMU and GNSS sensors respectively. A set of typical values are 100Hz for IMU and 1Hz for GNSS. When the measurement outputs of the GNSS is tend to be stable and accurate enough, the integration algorithm with such ´constant interval´ updating strategy works well. However, the ´constant interval´ updating strategy has drawbacks. The determination of optimized update interval is a trade-off between the accumulation of the estimation error, the precision requirement, the quality of the measurements and calculation budget. It is impossible to determine a constant optimized update frequency. First of all, the error accumulation speed is changeable, due to the IMU sensor quality, as well as the movement of the vehicle, and GNSS measurement quality. Given a well alignment, the estimation in a short period can provide higher accuracy than GNSS measurements. Furthermore, the accuracy of the GNSS measurements is not always guaranteed, particularly in some application with less reliable positioning systems. For example, in Beidou 1/IMU integration system, the integration results may be affected greatly by the less qualified measurements. An adaptive updating strategy (or named as ´double thresholds decision´ algorithm) therefore is proposed in the paper, in which the measurement update interval is changeable, and not all the GNSS measurements are used for correcting the state estimation. There are several advantages of this strategy. First of all, error accumulating speed of each estimate is monitored in real time. If the error is accumulated in a low speed, the update interval is comparatively large and makes full use of the high accuracy characteristic of INS in short range. In this way, the integration system mitigates the error sourced from the less qualified GNSS measurements. Secondly, when the estimation accuracy is deteriorated quickly, the update intervals are adjusted to be short, which enable the correction for the estimation error is made as fast as possible. Thirdly, some GNSS measurements are discarded for executing the update calculation. As a result, the integrating filter calculation budget is reduced, which benefits the real time applications.

The major function of the adaptive updating strategy is to maintain a decision-making process, which real time monitors the state estimation and the quality of the measurements and then make decision on whether the measurements are used for executing update or are discarded. Recorded GPS/IMU data are analyzed to explore the internal relationship among system parameters, which are related to the deteriorating speed of the INS estimation. The results of the real data analysis show that the movement of the vehicle has serious impact on the speed of estimation error accumulation. If the attitude of the vehicle is changing slightly (e.g. moving along a straight course), the error is accumulated slowly. However, if the vehicle has complicated movement, the quality of estimation is deteriorated with relatively higher speed. Furthermore, the analysis with real recorded data shows that the error covariance matrix P have relationship with the complexity of the vehicle movement. Based on this real data analysis above, the ´double thresholds decision´ algorithm is proposed. The error covariance matrix P, the difference between the estimation measurements and the GNSS measurements delta_z and the measurement noise matrix R, determined by the quality of the IMU, are chosen as the input parameters to the decision. To test the performance of the adaptive updating strategy, a method combining real data with the post-processing simulated data is adopted. Firstly, the dynamic raw data were collected from Leika GPS receiver ´GPS 1200´, and tactic IMU C-MIGITS II, which was mounted on the roof of a car. And then, the GPS data was post-processed together with the reference station data by using LEICA Geo OfficeTM software to get the centimeter level GNSS measurements.

The GNSS measurements and the IMU data were then processed by the traditional ´constant interval´ updating strategy to get the 100Hz trajectory, which is regarded as the reference trajectory. Following that, the additive white noise was added to the GNSS measurement to degrade the quality of the measurements. The less qualified measurements and the IMU data were processed with both the traditional method and the proposed adaptive updating strategy. The results show that the adaptive updating strategy adjusted the update intervals so that the update frequency increases when the vehicle is turning and decreases when the vehicle keeps moving along a straight course. The performance improvement by the proposed strategy can be revealed by comparing the integrated results with the reference trajectory. Comparison results show that the adaptive updating strategy improves the integration accuracy significantly in terms of covariance and merely in bias, even with 50% of the updating calculations budget of the traditional constant 1Hz updating strategy. The encouraging results demonstrate that the proposed adaptive updating strategy enables the GNSS/IMU integration systems application in the scenarios with less qualified GNSS measurements (e.g. Beidou 1/IMU real time integration system). It makes use of the accuracy of the stand-alone INS in short range and mitigates the negative effect of the poor GNSS measurement which accumulates error within the integration process. Moreover, it can reduce the calculation budget, and therefore enable real time applications in more flexible scenarios.

[Return to Program]

Session B3, Paper #6

Integrated Multi-aperture Sensor and Navigation Fusion
A. Soloviev, University of Florida; J. Touma, T.J. Klausutis, A. Rutkowski, K. Fontaine, Air Force Research Laboratory

The integration/fusion of vision and inertial navigation sensors (INS) can provide the Air Force with a precision navigation capability in the absence of GPS. Inspired from biological systems, a multi-aperture vision processing system allows for accurate self-motion estimation by observing optical flow across all apertures. The multi-aperture approach is particularly well suited for resolving motion-ambiguity by providing a wide field of regard for detecting and tracking visual features. We propose a novel data fusion approach for multi-aperture sensors that integrates the vision processing into a single unified frame of reference by projecting imagery from each aperture onto the unit sphere centered on the navigation frame. Traditionally, vision processing is done on the image plane projections; however, we will reformulate the problem on the unit sphere. The unit sphere projection will allow for the seamless integration of multiple apertures into the natural angle-angle space of the navigation frame of reference.
The multi-camera system will be modeled as an omni-view camera with multiple overlapping and/or non-overlapping views. The spherical projection representation will require a reformulation of fundamental image processing mathematics onto the unit sphere. We will focus on the following key areas: feature detection and descriptors, scale invariant feature tracking, optical flow, structure from motion, and coupling with the on-board navigation system. To evaluate the novel processing strategy, we intend to test our algorithms on data collected from an in-house-built multi-camera system. A novel multi-sensor fusion algorithm and system performance will be presented for ground and airborne imagery for small UGV and UAV applications.

[Return to Program]

Session B3, Paper #7

Multi-sensor Fusion for Localisation - Concept and Simulation Results
D. Kubrak, Thales Alenia Space, France; L. He, F. Legland, INRIA, France; Y. Oster, Thales Alenia Space, France

The increasing demand for positioning in urban areas has raised a huge interest in location technologies. Many different techniques exist, which all are based on the processing of various types of measurement, such as Digital TV and mobile phone signals, GNSS (High Sensitivity and Assisted chipsets), WLAN (WIFI, UWB, Zigbee) or sensors (inertial, pressure, RFID). All the positioning systems and elements have their pros and cons, depending upon the environment they are being deployed and operated, as well as the desired accuracy to be achieved. From a general point of view, outdoor positioning can be well managed with GPS chipsets, which offer the advantage of being independent of any infrastructures. However, many issues arise when going between tall building, skyscrapers or inside buildings. The accuracy of the position solution degrades quickly and the service may become unavailable. To fill this gap, alternative positioning techniques such as WIFI or UWB can be used, with different level of constraints and success.

In this context, we started the development of a low cost hybrid indoor / outdoor seamless positioning system dedicated to pedestrians and sensitive objects, whose localisation is of great importance. This project is supported by the French National Research Agency (ANR) and is conducted by a consortium made of laboratories and companies. It is composed of three phases, with first a research activity on navigation algorithms, technology trade-off and simulation of the system performance. A demonstrator will be build afterwards taking into account the outcomes of the first phase and finally the performance assessment of the hybrid positioning system will be conducted in a real environment. The present paper focuses on the description of the hybrid positioning system, details the selected algorithms and presents the overall performance of the system assessed on the basis of simulations. The detailed description of the demonstrator as well as the field test results is left for another publication.

The first section of the paper aims at giving a clear picture of the architecture of the system. Basically, the system is composed of four segments. Firstly, a set of sensors and measurement modules at the level of the pedestrian (or objects to localize). Secondly the infrastructure made of ranging beacons. Thirdly the communication links made of WLAN access points (WIFI), and finally the central computer that processes all the measurements to compute the positions of pedestrians (or objects).

Each pedestrian is equipped with a smart phone and a sensor unit composed of a set of sensors (triad of magnetometers, accelerometers, gyroscopes and a pressure sensor). In addition to these elements, an RF module allows for getting ranging measurements between the sensor unit and beacons mounted inside the building where people have to be located. A specific device is finally included in the sensor unit in order to measure the distance between two users. The sensor unit communicates with the smart phone through a personal wireless connection (PAN). The smart phone is equipped with a WIFI chipset in order to perform RSSI measurements with respect to WIFI access points of the infrastructure, and also to transmit all the data available at its level to the central computer.

As compared to technologies mixing pedestrian navigation with UWB, WIFI or TV signals, the hybrid positioning system described in this paper rather relies on a diversity of measurements and their fusion in order to get the position of a pedestrian or an object. The approach is basically to reduce at its minimum for a given application (compromise cost / accuracy) the number of elements of the infrastructure (beacons and access points) taking advantage of the various types of measurement available for data fusion rather than positions computed from various systems.

The second part of the paper focuses on the description of the data fusion algorithm involved at the central computer level to merge the diversity of measurements coming from all the pedestrians and objects to localize. More specifically, the algorithm addresses the problem of indoor localization of a pedestrian user combining measurements in a global particle filter, which approximates the optimal Bayesian filter. Four different sources of information are considered as input to the particle filter:
" Drifting measurements of the pedestrian heading as well as noisy estimates of the walked distance provided by a Pedestrian Navigation System (PNS)
" Noisy measurements of the distance between the user and a ranging beacon, or merely a detection indication when the user is within some (small) distance of a proximity beacon. It is assumed that beacons are well-localized and well-identified, but there could be a limited number of these beacons in the whole building, so that these measurements are not frequently available
" Noisy measurements of the distance between two users
" Information of a different nature provided by a map of the building, which lists obstacles (essentially walls) to the user walk.

The particle filter is described in great details in the paper and typical issues such as computing the position from the particle cloud, taking the building constraints into account, monitoring the degeneracy of the particle weights and the sample depletion in terms of effective sample size, detecting track loss and recovering from a detected loss are addressed. Once the algorithm is described, simulations are presented for different grade of measurements, as well as different sensor combinations (many or few beacons, many or few user-to-user measurements, PNS with good or very bad accuracy.). First simulation results show the efficiency of having one beacon in wide areas, as well as map-based constraints that significantly improve the accuracy of the PNS positions. User-to-user measurements impact onto the overall performance of the system is currently under assessment.

[Return to Program]

Session B3, Paper #8

Development of Integrity Approach for Image-Based Navigation Systems
C. Larson, J. Raquet, Air Force Institute of Technology

The navigation community has spent nearly two decades in development of GNSS integrity algorithms and continues to refine methodologies and investigate new approaches. As a result, the concept of integrity has been formalized for GPS to encompass fundamental criteria, including the ability to detect measurement errors and notify the user when the system should not be used because of potentially corrupt measurements. Ideally, the GPS integrity algorithm also provides a protection limit, essentially establishing a bound on the largest position error that would be possible for an undetected measurement error. Common Receiver Autonomous Integrity Monitoring (RAIM) and other approaches generally use measurement redundancy in order to detect measurement errors, and generally involve GPS-only positioning. A few algorithms have been developed to characterize integrity when a GPS is integrated with an Inertial Navigation System (INS).

While larger issues of integrity are seemingly well-understood for many GPS applications, to the best of our knowledge, no one has addressed rigorous integrity quantification with respect to image-based navigation systems. Image-based systems are increasingly being considered as viable alternatives to GPS in instances or environments where GPS signals may be unavailable, either intentionally or unintentionally. Key advantages in image-based navigation systems include independence from external radio-frequency transmissions and potentially low-cost implementations of camera and image processing suites. If these systems are to operate in addition to, or possibly in lieu of, GPS, there will increasingly be a need to understand integrity when using images for navigation.

This research examines and addresses the fundamental differences existing between the measurement models established for GPS and those of proposed image-based navigation systems. For example, GPS pseudorange measurements used in a position determination are provided as a single value per satellite. However, image measurements are inherently angle-based measurements and assumed to be provided as a pair of pixel coordinates for a mapped target. Under these conditions, consideration must be given not only to the units of the transformations between the states and measurements, but also to the fact that multiple rows of the observation matrix relate to particular error states in the image-based case. This is due the added dimensionality of the pixel pair measurements.

Further investigation also notes that specified integrity parameters for probability of false alarm and probability of missed detection are well established for GPS and that RAIM prediction can be made based on known time/orbit relationships. In contrast, the probability of false alarm and missed detection in an image-based navigation system are less concrete and influenced by external factors, such as the feature tracking algorithm. Therefore, the paper discusses the trade-offs in the detection threshold setting based on consideration of best performance with required integrity parameter requirements. In addition, although target coordinates with respect to some coordinate frame may be known, which targets will be visible at any given time cannot be perfectly predicted, precluding a prior prediction of expected integrity.

Lastly, the attitude of the sensor becomes a significant factor when using image measurements (unlike the GPS case, where only position is calculated directly from the GPS measurements). With image measurements, the attitude can either be solved for directly, or it can be considered known (such as if the camera was mounted to an INS with a sufficiently-good attitude determination capability to be considered a known attitude). In this paper, we show that, from an integrity perspective, there is a significant benefit of having known attitude information. This result may have significant implications for image-based navigation systems where integrity is important.

[Return to Program]

Session B3, Alternate #1

Maps and Floor Plans Enhanced 3D Movement Model for Pedestrian Navigation
M. Khider, S. Kaiser, P. Robertson, M. Angermann, German Aerospace Center, Germany

A model that realistically imitates real pedestrian movement can be used for numerous applications such as infrastructure design, evacuation planning, architecture, robot-human interaction or navigation. Within the scope of this paper, the purpose of such models is to quantitatively represent the stochastic nature of 3D pedestrian movement in order to generate a movement model for sequential Bayesian filtering techniques, such as particle-filtering.

A movement model in the sense of a first order Markov process can be used to represent and probabilistically predict human motion and behavioral parameters as a function of previous parameters and other affecting states. The prediction stage of sequential Bayesian estimation depends entirely on the movement model to determine the probability density function of the pedestrian´s location and motion at each time step. A movement model that accurately models the pedestrian´s motion determines the performance of the sequential Bayesian estimation algorithm, and ensures that measurement data used for positioning is correctly weighted with the movement model prediction. Furthermore, the model has to be efficiently implemented to that it can be employed in realizations such as Particle Filters. We note that the model does not need to predict the motion of a single pedestrian accurately in any singular experiment; it needs to correctly model the expected motion in a probabilistic sense.

In this paper, a three-dimensional movement model that is suitable for pedestrian navigation will be illustrated. Specifically, the knowledge of maps and floor-plans is used in our movement model and the performance gain of overall positioning will be investigated.

A combination of three-dimensional movement models will be used to model the pedestrian motion. The constituents are a three dimensional Stochastic Behavioral Movement Model and a three dimensional Targeted Movement Model. Some specific constraints are applied on the pedestrian movement while moving on stairs to have a realistic stairs movement.

3D Stochastic Behavioral Movement Model: Human movement is parameterized by physical parameters such as speed, direction and as a result the position. Building layouts are obviously amongst the main parameters that affect the movement of the pedestrian.

In order to add the third dimension, the model of [KKRA08] was extended to be able to predict the elevation of the pedestrian at each time step. A linear speed function is used for modeling the elevation. This vertical speed is designed to be a function of time, steepness of the stairs and "activeness" of the pedestrian. Accordingly, the probability distribution of the distance moved in the Z-direction can be calculated. The direction of vertical movement could also be modeled, but in order to have a more realistic movement in the stairs area, the direction is predicted using a targeted movement model described below. Outside the stairs area, the elevation is assumed to be constant.

3D Target Driven Movement Model: To represent target driven human motion, a so-called "diffusion movement" model [KKRA08] is applied. It is derived from "gas diffusion" in space studied in thermodynamics and is a standard solution for path finding of robots [ScA93]: The idea is to have a source continuously effusing gas that disperses in free space and which gets absorbed by walls and other obstacles. A path towards this source is computed by following the steepest gradient, starting at the current position. To model the stochastic nature of a human´s motion, the destination points are chosen randomly, and a Markov process models the fact that the destination may change.

In order to add the third dimension, the set of destinations can be distributed over all the floors. The stairs area is projected into a 2D area that can be included in the respective floor plan of each floor. Accordingly, the diffusion matrix calculation can be started at any of the floors. The diffusion matrix at the stairs area of the destination floor is calculated for the stairs going up and down and then copied to the stairs areas of the respective neighboring floors. The diffusion matrix is then calculated from the stairs area to the rest of the respective floor. The stairs diffusion matrix of the next upper or lower stairs is calculated using the values of the current floor and so on. Paths to the destinations are found in the same 2D manner but continuing to the upper or lower floors until the destination is reached.

Combined Model: If the pedestrian is outside the stairs area a top-level Markov process is used to determine whether to use the stochastic behavioral or the diffusion model; therefore, the model switches between motion that is more goal oriented or stochastic. The destination point for the diffusion model is kept until the destination is reached or until the top-level Markov process determines that the stochastic behavioral movement model is again used. When applying the diffusion model the path is computed in two steps: the direction is chosen to follow the gradient of the gas diffusion towards the target while the speed of the pedestrian is predicted with the stochastic behavioral movement model. If the pedestrian enters the stairs area then the three dimensional Stochastic Movement Model will be used to predict distances moved in X, Y, Z directions. These distances are passed to the Targeted Movement Model to be combined with the paths and obtain the new positions.

Maps and Floor-Plans: The effect of the advance knowledge of specific maps and floor-plans will be tested in an already available distributed simulation and demonstration system for mobility, and location estimation. The system allows us to integrate several types of sensors, Bayesian Filters, movement models, maps and floor plans. We will discuss quantitative performance improvements that our 3D movement model allows when combined with maps and floor-plans in the overall estimation process in pedestrian indoor/outdoor navigation applications.

References: [KKRA08] M. Khider, S. Kaiser, P. Robertson, M. Angermann, "A Novel Movement Model for Pedestrians Suitable for Personal Navigation", ION-NTM-2008, San Diego, California, 2008 [ScA93] G. K. Schmidt and K. Azam, "Mobile robot path planning and execution based on a diffusion equation strategy", in Advanced Robotics, Vol. 7, No. 5, pp. 479-490, 1993.

[Return to Program]

Session B3, Alternate #2

Effects of Navigation Sensor Errors and Map Quality on the Performance of Map-matching
N.R. Velaga, Loughborough University, UK

Most of the Intelligent Transportation Systems (ITS) applications require real-time precise vehicle location information on a spatial road network map. The navigation module of ITS services is generally supported by a range of positioning systems such as Global Navigation Satellite System (GPS, Galileo), dead reckoning (DR) system and inertial navigation systems (INS) etc. Map-matching (MM) algorithms integrate positioning data from navigation sensors with a spatial road network map with the aim of identifying firstly, the road segment on which a vehicle is travelling from a set of candidate segments; and secondly, determining the vehicles precise location on that segment.

Sometimes, these MM algorithms fail to identify the true road segment from candidate segments; this phenomenon is called wrong matching or mismatching, which severely degrade the algorithms (2-D) horizontal positioning accuracy. For most of the ITS services (for example: navigation and route guidance, GPS based variable road user charging, emergency vehicle routing, and automatic announcement of bus stops) the wrong road link identification could mislead the users, and makes the service ineffective. The mis-matchings are due to many factors including missing road links or extra road links in the network; error associated with map digitization, accuracy of vehicle heading measurement; errors in map-matching process such as candidate link identification, threshold values, weight score errors etc. It is important to understand and quantify the individual error contribution for each mismatching to enable the further improvement of navigation module of ITS services.

The main objectives of this study are:

(1) Identify the reasons of mis-matching.

(2) Test the algorithm using an extensive positioning data collected in three different countries: UK, India and USA.

(3) Analyze each mismatching case individually for the above three data sets, and quantify the error sources associated with navigation sensors, digital map and map matching process.

(4) Present a summary of GPS performance (in stand-alone navigation mode), with respect to satellite availability, dilution of precision, positioning accuracy compared to the central line of true travel path etc, for the above data sets separately.

(5) Provide future research directions to improve the successes rate of map-matching.

Description of the MM algorithm used in this study:

Previous research by the author had developed an enhanced weight-based topological MM (tMM) algorithm (Velaga et al., 2009). The MM process is divided into: initial MM, matching on link, and MM at junction. The algorithm selects all the links which are inside and touching the error bubble as candidate links. Among these candidate links, correct link identification is based on total weight score, which is sum of heading, proximity, connectivity, and turn restriction weights. For initial MM, only proximity and heading weights are considered. whereas for MM at junction, all the four weights are considered. In case of MM on a link, the vehicle is assigned to the previously selected link for the earlier positioning point. The relative importance of each weight score for different operational environments, urban, suburban and rural areas, were identified using an optimisation test. The detail description of this algorithm can be found in Velaga at al., (2009).

Positioning data collection and digital road map: In this study, all the mismatching causes are critically analyzed using positioning data collected in three countries: UK, India, and USA. Altogether, 62,887 position fixes (with approximate trip durations of 17.5 hours) are map-matched and carefully analyzed. Total test route trajectory length (i.e. travel distance) is about 812 KM with mixed locational characteristics of dense urban, urban, suburban and rural areas.

Data set A: 42,231 Positioning points were collected in the United Kingdom (from Loughborough to London, in central London and south part of London).

Data set B: 16,757 positioning points were collected in Mumbai metropolitan area, India.

And data set C: 3,900 positioning fixes were collected in urban roads of Washington, DC.

These three data sets were obtained from controlled field tests which were carried out on a pre-planned route. It was also noted where exactly vehicle took turn. So, we know the correct road segment on which vehicle travelled for each positioning point. The test routes were selected carefully to ensure that the vehicle travelled through a good mix of characteristics such as tall building, bridges, flyovers, and dense road network, congested urban roads, open areas, construction sites, motorways, village roads etc. In this research, to analyze the above data sets three separate digital road maps, UK map, Washington DC map, and Mumbai map, were used. For all these maps, roads are represented with road central line. Also, digital map scale for the above three maps are different.

Performance analysis of the algorithm:

It is revealed that the enhanced tMM algorithm has 96.7 %, 91.8% and 95.93% success rate of correct road link identification for data set A, B and C respectively. Every case of mismatching is examined carefully and exact source of error (i.e. navigation sensors, digital map, and MM process) is quantified for each data set individually. For example, for the data set B, the percentage of mismatchings due to missing links or extra links in the digital map and digitisation errors are 46.8% and 24.8% respectively. Google earth (satellite image) is considered as base map to identify the digital map errors for each mismatching case. The detail methodology and step-by-step process to examine the mismatchings in vehicle navigation module output will be explained in the final paper.

After analyzing each failure case (mismatch), for the three data sets that use different quality maps, the paper discusses the future research directions (especially in MM process) to improve the successes rate of map-matching algorithms.

Reference:

Velaga, N. R., Quddus, M. A., and Bristow, A, L., 2009, ´Developing an Enhanced Weight Based Topological Map-Matching Algorithm for Intelligent Transport Systems,´ Presented at the 88 th Transportation Research Board (TRB) Annual Meeting, Washington D.C., January 2009.

[Return to Program]

Session B3, Alternate #3

A New GPS/RFID Integration Algorithm Based on Iterated Reduced Sigma Point Kalman Filter for Vehicle Navigation
J. Peng, RMIT University, Australia & National University of Defense Technology, China; M. Zhu, F. Wu, RMIT University, Australia; F. Wang, National University of Defense Technology, China; K. Zhang, RMIT University, Australia

Global Navigation Satellite System (GNSS) is the most well known satellite-based radio-navigation system that provides accurate positioning and timing on the global basis. It has been widely used in all kinds of fields such as military, aerospace, survey and communication due to its high accuracy, reliability and all-weather capability. However, it performs poorly in the area of limited satellite visibility or the area where the GPS service is unavailable, such as the tunnels, the canyon areas packed with skyscrapers, the weak signal environments.

Radio Frequency Identification (RFID) is a new technology which is used in logistics applications. Recently, it shows potential advantages in pedestrian and indoor positioning, blind guide and healthcare systems due to its low-cost and its capabilities in harsh environments.

When GPS signal is blocked up or reflected by high buildings or tall trees, the quality of GPS measurements will become worse and the accuracy of positioning extremely degrades. In order to obtain an accurate positioning in such limited satellite visibility areas and enhance the availability of GPS, some researches on GPS/RFID positioning algorithm for outdoor vehicle navigation have been conducted in recent years. It has been shown that the integrated GPS/RFID system has a potential to provide positioning information more accurately and continuously than GPS standalone.

In the conventional GPS/RFID method, the location information such as the absolute coordinates of the tag, the relative coordinates between the tags, street name, and all the necessary information for vehicle navigation is stored in each RFID tag. Unfortunately, it would be infeasible in reality, particularly in a high velocity environment due to the memory constraints and communication speed of RFID. Generally, RFID tags are installed on the road according to a certain RFID map, in which the Received Signal Strength
(RSS) of each tag is stored as a fingerprint in a database, and the vehicle position can be obtained by a dense RFID grid which covers the positioning area. Nonetheless, this method needs a large number of RSS data to achieve an accurate positioning, and it is difficult to design and implement. Obviously, the hardware cost and the memory constraints on RFID tags will limit the application of GPS/RFID method.

In this paper, a new positioning algorithm based on GPS/RFID with sparse RFID tag map is proposed, which is able to acquire stable and continuous positioning for outdoor vehicle, particularly in limited satellite visibility areas. The algorithm is based on the RSS measurement to measure the distance between RFID tag and vehicle to estimate the position of vehicle with the assistant of known positioning information.

Considering the memory constraints of RFID tag, the accurate positioning information is stored in a database in advance, and the tags are installed in the limited satellite visibility area according to a sparse map. When a vehicle with RFID reader passes through the area covered with sparse RFID tags, the tags are activated and only the necessary information such as tag ID is transmitted to the vehicle even at a high velocity. Then the distance between tag and vehicle is obtained by the RSS measurement, and the position of vehicle can be calculated by solving the distance equation with the known position information of tags. Moreover, the positioning result obtained by the aid of RFID technique would enhance the performance of GPS positioning filtering as an accurate input of the positioning filter.

To improve the accuracy of positioning, a novel iterated Newton-Gaussian Reduced Sigma Point Kalman Filter (RSPKF) is used to enhance the performance of the integrated GPS/RFID system as well. This novel filter proposed in this paper enable reducing the computational complexity dramatically without
sacrifice of estimation accuracy when compared with the standard iterated SPKF method. In the standard SPKF implementation, it needs 2N+1 sigma points to calculate the sigma point set, where N is the dimension of state random variable, it will increase the computational complexity dramatically when the dimension of state vector is very large, especially in the iterative process. Due to this reason, the RSPKF method uses reduced sigma points sampling method with only N+2 sigma points to reduce the computational cost. With iterated RSPKF, it can achieve an approximate maximum a posteriori estimate and the noise of RSS measurement caused by the outdoor harsh environment and RFID antenna orientation can be restrained effectively. To valuate the performance of the new algorithm proposed, a series of experiments are carried out in a typical urban environment in the City of Melbourne, Australia. GPS observation data is collected by using Trimble R8 receiver with a sampling rate of 1Hz. The RFID tags are installed on both side of street with a distance of 5 meters. Reference trajectory is provided
by the network RTK results based on the GPSnetTM Continuously Operation Reference Station (CORS) network in the State of Victoria. The experimental results show that the accuracy of GPS/RFID positioning is improved 75% than the results without the aid of RFID positioning information when satellite
visibility is limited, and the availability of GPS is increased efficiently. The experimental results also show that, with the help of the new iterated RSPKF filter, the estimate accuracy of the GPS/RFID positioning filter is improved 26.3%. It demonstrates that the proposed GPS/RFID integration method based on an iterated reduced sigma point Kalman Filter with sparse RFID map can improve the accuracy and availability of GPS positioning significantly for outdoor vehicle navigation.

[Return to Program]

Session B3, Alternate #4

The Merits of UKF and PF for Integrated INS/GPS Navigation Systems
S. Saeedi, N. El-Sheimy, University of Calgary, Canada

Inertial Navigation System (INS) and Global Positioning System (GPS) technologies have been widely used in a variety of positioning and navigation applications. Both systems have their unique and complementary advantages and drawbacks. Therefore, integrated INS/GPS systems critically overcome each of their drawbacks and improve each of their benefits. Bayesian nonlinear filtering techniques are then needed to fuse the collected data from INS and GPS sensors in different configurations. In this paper, we loosely update the nonlinear mechanization equations of low cost MEMS based IMU with the measurements of DGPS sensors. Then, the INS error states, together with any navigation state (position, velocity, and attitude) and other unknown parameters of interest, are estimated using GPS measurements. In a high performance system, it is expected that all states will be precisely estimated. Although it has been noted that both the quality of the dynamic model and measurements, specification of the platform and trajectory and characteristics of the problem will have impacts on system performance, an evaluation of different filtering techniques is still lacking. In the integrated navigation systems, the most successful filtering techniques for navigation state estimation are Bayesian filters such as Kalman filters (KF) [1]. Bayes filters recursively estimate posterior probability distributions over the state of a system. The key components of a Bayes filter are the prediction and observation models, which probabilistically describe the sequential evolution of the system and the measurements returned by the sensors, respectively.

This paper will address this issue through an exclusive investigation and comparison of two main classes of nonlinear state estimators which can be distinguished as: (i) Unscented Kalman Filter (UKF) which is a Kalman filter designed specifically for nonlinear systems with Gaussian statistics and has been shown to be the best performing algorithm of the Kalman filters. (ii) Particle Filters (PF) which is designed for nonlinear systems that allows arbitrary distributions for the underlying states and noise estimates and belong to the most popular Monte Carlo methods. UKF and PF extend the concept of sequential filtering to nonlinear settings which have been successfully employed in a variety of applications. UKF which is introduced in 1996 by Julier and Uhlmann [2] overcomes the drawbacks of KF by estimating the statistics of the state vector propagated through the nonlinear state space model. The key concept in UKF is the unscented transformation. Accurate statistics of the propagated vector are estimated from a deterministically chosen set of sample points. These carefully chosen points are called sigma points. PF have recently been increasingly proposed as an alternative filter for complicated non-linear state stimations. This filter was first introduced by Gordon, Salmond and Smith in 1993 [3] and further variations and enhancements by these and other workers have followed and now all such filters tend to be embraced by the term ´particle filters´. The main advantage of PF over UKF is that it does not constrain the statistics of the noise and the states to be Gaussian. The PF algorithm is based on sequential Monte Carlo technique where probability distributions are represented in terms of randomly picked samples (particles) and these particles are then recursively updated using Bayesian estimation procedures. In order to evaluate the potential of UKF and PF algorithms through real data analyses, an experimental setup has been developed in land vehicle environment.

Three field tests were conducted on using a navigation grade IMU (Honeywell CIMU), the MMSS group MEMS IMU (Analog Devices Inc. sensors) and two NovAtel OEM 4 GPS receivers (for providing DGPS as a reference GPS solution). In Navigation applications, not only precise state estimation, but also fast computation and convergence to the real states are necessary. In this paper, three criteria have been investigated to compare the filtering methods. (1) The root mean square error (RMSE) is used to evaluate the performance of the filters due to the precise state estimation. (2) The reliability and time of convergence of the algorithm is investigated through different initial condition for the experiments. (3) The computational cost of each method is evaluated for on-line navigation application. The UKF has been shown to offer superior performance to that of the Extended Kalman filter, particularly in terms of the filter´s stability. Except for a few special cases (such as linear Gaussian state space models), the performance of UKF is comparable with PF. However, when the non-linearity is pronounced then even the best-fitting Gaussian distribution will be a poor approximation to the posterior distribution, and the particle filter is an effective solution to the challenge of non-linear, non-Gaussian navigation state estimation. Based on the "convergence" criteria, when the initial conditions deviate significantly from the true values, UKF filter gives an unbiased estimate, but its convergence is slow, leading to an overall high estimation error. The PF estimates converge faster, but the high computational costs limit the real-time performance. Also, its performance heavily depends on the tuning. To conclude, the Particle filter is computationally expensive in compare with UKF; consequently, for online navigation application UKF is more suitable. Nevertheless, using the Extended Particle filter, or (preferably) the Unscented Particle filter, one can place particles more intelligently than with the prior proposal. Therefore fewer particles are needed and so computational expense is reduced. References [1] Sinpyo Hong, Man Hyung Lee, Sennior Member, IEEE, Ho-Hwan Chun , Sun-Hong Kwon, and Jason L Speyer, Fellow, (2005) IEEE "Observability of Error States in GPS/INS Integration", IEEE Transactions on Vehicular Technology, Vol.54, NO.2, March 2005 [2] S. Julier and J.K. Uhlmann. A new extension of the Kalman filter to nonlinear systems, (1997). Proc. of AeroSense: The 11th Int. Symp. on Aerospace/Defence Sensing, Simulation and Controls. [3] D.J. Salmond N.J. Gordon and A.F.M. Smith, (1993). Novel approach to nonlinear/non- Gaussian Bayesian state estimation. IEE Proceedings - F, vol. 140, no. 2, pages 107-113.

[Return to Program]