lHallo,
für die Ultraschallsensoren gibt es hier eine gute Schaltung:
http://www.rn-wissen.de/index.php/Ultraschall-Interface
Ich würde das ganze noch mit Odometriesensoren kombinieren, dann könntest du dich schon recht gut im Raum orientieren.

Dein 2x2m Labyrinth kannst du in Raster zu ca. 10x10 cm einteilen also insgesamt 400 Rasterteile.
Im Atmega kannst du dann eine Rasterkarte anlegen, sagen wir für jeden Rasterteil ein Byte (geht sicher auch mit weniger um noch mehr Platz zu sparen) das wären dann also rund 400Bytes; ich denke das geht schon.
Schlimmstenfalls mannst du ja noch mit einem exgernen Ram nachhelfen.
In die Bytes kommen dann Informationen, wie z.b hier war ich schon oder hier ist eine Wand.

Dass sich der Atmega dann wirklich im Labyrinth zurechtfindet ist dann sicher noch ein Aufwand, aber ich denke mit genug Experimentierfreude sicher machbar.

PS: Der Ram ist übrigens nur 2kb groß. 32kb isr der Flash also dort wo das Programm gespeichert wird!