Importance Sampling Kalman Filter for Urban Canyon Navigation
Yeongkwon Choe, Seoul National University, Republic of Korea; Jin Woo Song, Sejong University, Republic of Korea; Chan Gook Park, Seoul National University, Republic of Korea
Alternate Number 3
This work presents a complementary navigation algorithm to Global Navigation Satellite Systems (GNSS) in an urban canyon. In urban canyon environment, it is difficult to use GNSS (global navigation satellite system) because its signal is too weak to propagate through buildings. In this situation, UAV (unmanned aerial vehicle) generally uses IMU (inertial measurement unit) for navigation. However, UAV operable in the city usually carries low-cost MEMS grade IMU, which will diverge soon. Thus, we employ highly detailed 3D maps and measure the outline of buildings to prevent the fast divergence of estimation.
Soloviev and his colleagues have researched on scanning LADARs (laser radars) based navigation method for GNSS-denied environments. This method is based on the fact that a building can generally be regarded as a set of planar surfaces. They extract a planar surface from lots of distance measurements of RADAR and build a plane list of buildings. If a newly extracted plane is matched with the plane list, the position and orientation of a vehicle will be updated based on matching relation. This method does not require maps but requires a scanning LADAR that can measure a lot of distance data. To measure large buildings with a boulevard, a LADAR sensor should have enough scanning range for this method. Unfortunately, long-range scanning LADAR whose mechanical driving part is enough reliable is very expensive. Meanwhile, highly detailed 3D maps of urban canyons can be easily accessed by anyone. In other words, we do not need to make maps ourselves in well-known urban sites.
This paper proposes a navigation algorithm using multiple inexpensive rangefinders and 3D maps. The algorithm propagates position estimation using INS (inertial navigation system) and updates the estimation by comparing rangefinders with 3D maps. Although the outline of a building is usually linear in narrow scope, the outline of a whole building and arrangements of buildings are nonlinear. For considering this nonlinearity, the proposed algorithm utilizes an importance sampling method. Importance sampling is a method to estimate desired pdf (probability density function) by sampling based on importance density. Using this, it is possible to search densely on highly possible region according to an importance density. A particle filter is one of the famous method based on importance sampling, and it is also famous for demanding a heavy computational load. Since it is not feasible to estimate all 12 states using particle filter alone, it should be combined with Kalman filter via Rao-Blackwellization. This means that highly nonlinear states can be estimated effectively with reduced load, but it still needs multiple Kalman filters as many as the number of particles. Therefore, a particle filter is not suitable for our system which should calculate a burden of 3D models and filters with small size embedded computer.
For taking advantage of both Kalman filter and importance sampling, this paper proposes Kalman filter based algorithm that partially applies importance sampling to the horizontal position measurement model which can be highly nonlinear. The results of importance sampling are given in arbitrary pdf, so they should be approximated as normal distribution for use in Kalman filter. Since the desired likelihood function is greatly influenced by the arrangement of buildings, an importance density is based on the linearized model between the arrangement of buildings and position error. This method directly calculates the mean and covariance from pdf, so it will give a clearer description of the desired pdf than using a typical first order linearized model.
A Monte-Carlo simulation was conducted for performance verification. For a simulation, we employed highly detailed 3D maps composed of Level-of-Detail 4 (LOD4) grade 3D building database and one-meter resolution digital elevation model. The simulation results present that the proposed algorithm is a highly feasible method as a complementary algorithm for GNSS-denied environments.