We present a method for sensor-based exploration of unknown environments by a mobile robot. The method is based on the randomized incremental generation of a data structure called sensor-based random tree (SRT), which represents a roadmap of the explored area with an associated safe region. Different exploration strategies may be obtained by instantiating the general method with different perception techniques. Two such techniques are discussed: the first, conservative and particularly suited to noisy sensors, results in an exploration strategy called SRT-Ball. The second perception technique is more confident, and the corresponding strategy is called SRT-Star. The two strategies are critically compared by simulations as well as by experiments on the MagellanPro robot.