Abstract. This paper presents an analysis of odometry errors in over-constrained mobile robots, that is, vehicles that have more independent motors than degrees of freedom. Examples of over-constrained vehicles are the various 6-wheeled Mars Rovers like Rocky-7, Rocky-8, or Fido. Based on our analysis we developed two novel measures aimed at reducing odometry errors. We also developed a novel method that serves as a framework for the implementation of the two new measures, as well as for other, conventional error reducing measures. One of the two new measures, called “Fewest Pulses Measure, ” makes use of the observation that most terrain ir-regularities, as well as wheel slip, result in an erroneous overcount of encoder pulses. The second ...