Localization and mapping are fundamental tasks in mobile robotics. State-of-the-arts often rely on the static world assumption using the occupancy grids. However, the real environment is typically dynamic. We propose the feasibility grids to facilitate the representation of both the static scene and the moving objects. The dual sensor models are introduced to discriminate between stationary and moving objects in mobile robot localization. Instead of estimating the occupancy states, the feasibility grids maintain the stochastic estimates of the feasibility (crossability) states of the environment. Given that an observation can be decomposed into stationary objects and moving objects, incorporating the feasibility grids in localization yields performance improvements over the occupancy grids, particularly in highly dynamic environments. Our approach is extensively evaluated using real data acquired with a planar laser range finder. The experimental results show that the feasibility grid is capable of rapid convergence and robust performance in mobile robot localization by taking into account moving object information. A root mean squares accuracy of within 50cm is achieved, without the aid of GPS, which is sufficient for autonomous navigation in crowded urban scenes. The empirical results suggest that the performance of localization can be improved when handling the changing environment explicitly.