Lo que te va a resultar más fácil es usar motores DC con su correspondiente driver. En cuanto a sensores, los infrarrojos de corto alcance te van a dar mejores resultados porque con los ultrasonidos vas a tener ecos dentro del laberinto.
Yo utilizaría java directamente usando NetBeans para el MMI y una simple interfaz serie para comunicarte con el AVR (Arduino).