A ver, hagamos unos cálculos:
decías que tus servos van a un máximo de 60rpm. Si el disco marcado que le pones tiene, por ejemplo 20 marcas, eso serían 1200 interrupciones por minuto, o sea 20 por segundo, que es lo mismo que decir que tienes 50ms para hacer cosas entre interrupciones cuando el robot va a toda leche.
A en un micro a 20MHz, que furula a 4MIPS, le daría tiempo a ejecutar 200.000 instrucciones entre cada marca de la rueda. Sólo falta ver si serás capaz de apretar tu programa para que quepa ahí. Aunque siempre puedes poner menos marcas a las ruedas y perder un poco de precisión.