Several algorithms are proposed for solving the Simultaneous Localization And Mapping (SLAM) problem for mobile robots. An efficient representation is required for large scale environment exploration and long term navigation, which is the main concern of this the­sis. For this purpose, observations of sensors such as stereo camera or Microsoft Kinect are represented as a linear combination of atoms of a parametric dictionary by sparse model­ing technique. The parametric dictionary is composed of Gaussian functions. In order to perform loop closure detection, the Normalized Compression Distance (NCD) is employed from information theory. The performance of this technique is analyzed in some indoor and outdoor environments. In addition, it has been proved that the developed environ­ment representation is transformation invariant in the sense of Kolmogorov complexity. Furthermore, another environment is developed based on the Non Uniform Rational B-Spline (NURBS) for more accurate environment representation, simpler obstacle detection and smooth path planning. The NURBS-based environment representation is equipped with all of the sparse model benefits such as lower dimensionality, representation of infor­mation complexity, transformation invariance, parametric representation and uniqueness. Also, in contrast to the conventional environment representation methods, discrete sensor observation can be expressed in a continuous parametric space. This makes the obstacle detection simple and parametric representation of robot's path possible. The applicability of the proposed method is shown by several experiments on indoor and outdoor data-sets.