This paper describes a simultaneous planning localization and mapping methodology, where the robot explores the environment efficiently and also considers the requisites of the SLAM (Simultaneous Localization And Mapping) algorithm. The method is based on the randomized incremental generation of a data structure called Sensor-based Random Tree, which represents a roadmap of the explored area with an associated safe region. A continuous localization procedure based on B-Splines features of the safe region is integrated in the scheme. The approach is evaluated for accuracy and consistency using computer simulations and for effectiveness using experimental data from different real environments.