Autonomous robots require many types of information to obtain intelligent and safe behaviours. For outdoor operations, semantic mapping is essential and this paper proposes a stochastic automaton to localise the robot within the semantic map. For correct modelling and classification under uncertainty, this paper suggests quantising robotic perceptual features, according to a probabilistic description, and then optimising the quantisation. The proposed method is compared with other state-of-the-art techniques that can assess the confidence of their classification. Data recorded on an autonomous agricultural robot are used for verification and the new method is shown to compare very favourably with existing ones.Research highlights► Safe outdoor autonomous operations using fault tolerant semantic mapping. ► Stochastic automaton to model environment-distinctive areas and topological relations. ► Optimised quantisation of perceptual features according to probabilistic descriptions. ► Comparison with existing state of the art using an autonomous agricultural robot.