Aiming at the problem of low registration accuracy of traditional laser scan matching method under multi-obstacle environment, a matching method based on graph theory was proposed. In this method, concave and convex points were extracted from the data points, then the corresponding line segments were extracted and the attribute graph model was constructed. The point set registration problem was transformed into an attribute graph matching problem. The registration parameters were determined by comparing the observed graph model with the reference model. Compared with the traditional matching algorithm based on line segments, the proposed algorithm introduces more geometric attributes between line segments, which have better robustness in multi-obstacle environment or dynamic multi-obstacle environment. Compared with the traditional matching method based on points or feature points, the proposed algorithm constructs the attribute graph model based on the more specific feature points, say convex points and concave points. In this way, the proposed algorithm not only improves the operation efficiency, but also avoids the local minima problem in multi-obstacle environment and dynamic multi-obstacle environment.