Abstract: For building the consistent grid-based map of mobile robot only with laser range finder and odometer, this paper presents a novel algorithm that combines iterative closest point (ICP) algorithm with Rao-Blackwellized particle filter. It employs ICP algorithm to register one range scan to a previous scan so as to compute the relative robot position, then uses the result to replace the odometer reading and improve the proposal distribution. With an improved resampling method, the number of samples required is seriously reduced. Simulations on the real robot data sets illustrate the superior performance of our approach.