This thesis is about feature-based mobile robot navigation in unknown environments. The work is focusing on solving the problem of Simultaneous Localization and Mapping (SLAM) including feature extraction, estimation and complete map building solution. The robot platforms used in this work have the encoders for odometry and several laser scanners for exteroperceptive sensors. Simulations, real experiments and existing well known datasets are used in order to verify the performance of the developed algorithms. The algorithms developed in this thesis are features based meaning that instead of directly using raw sensory data geometric features are first extracted. This allows the filtering of noise from the sensors and the dynamics of the environment. More importantly, feature based approaches can reduce the amount of data needed to process, enabling the algorithms to scale in large environments. Another advantage of using features is the characteristic of better isolating informative patterns so that by exploiting specific knowledge of the environment, specialized algorithms can be easily adopted with different types of features. Several geometric features (points, lines, planes) are considered in this work. In this thesis, the relative mapping approach is adopted for solving the SLAM problem. This approach has many advantages. First, the mapping is decoupled from the estimation of robot pose so that the map estimation is independent from odometry errors. In other words, odometry errors do not affect and accumulate to the map estimate as in the absolute mapping approach. Second, the estimation does not involve the dynamics model of the robot which is identity in a relative mapping algorithm, meaning that only the observation model is considered in the estimation. A relative map has extra consistency problem compared to an absolute map. It is subject to the geometrical consistency problem which may generate an inconsistent absolute map after an transformation. However, having only observation model in the estimation gives an insight to separating nonlinearities from the iterative part of the estimator and thus minimize the effects of linearization errors. In this work, these subjects are investigated and reported. For some service robotic applications, especially for indoor office-like environments, we would like to have a fast, robust and lightweight approach which is capable to perform real-time SLAM on minimal hardware platforms. By exploiting some known knowledge about the structure of the environment, we claim to be able to achieve that goal. Particularly, the OrthoSLAM algorithm has been developed for building 2D and 3D maps. The algorithm adopts the Orthogonality assumption (or constraint) on the environment. First, the complexity of the SLAM algorithm is significantly reduced. Second, the linearization error from the robot heading uncertainty is removed and thus the map consistency is greatly improved. Implementations of the developed algorithms are tested on simulated data, on existing real world datasets and on robot platforms. Existing algorithms used in this work have been also reimplemented. The performance of the algorithms are analysed and compared on well chosen criteria. Particularly, the issues on computational complexity, linearization error, map consistency, map precision, realtime capability are investigated.