Self-localization of mobile robots in the environment is one of the most fundamental problems in the robotics field. It is a complex and challenging problem due to the high requirements of autonomous mobile vehicles, particularly with regard to algorithms accuracy, robustness and computational efficiency. In this paper we present the comparison of two of the most used map-matching algorithm, which are the Iterative Closest Point and the Perfect Match. This category of algorithms are normally applied in localization based on natural landmarks. They were compared using an extensive collection of metrics, such as accuracy, computational efficiency, convergence speed, maximum admissible initialization error and robustness to outliers in the robots sensors data. The test results were performed in both simulated and real world environments. info:eu-repo/semantics/publishedVersion