Roboterprojekt

...die Karte via REST abgefragt oder HTML visualisiert werden kann; Frage ist nat. ob hierzu die Rechenpower ausreicht.
Während der Fahrt kann eine Kamera und ein Mikrofon zugeschaltet werden um die Fahrt live zu verfolgen.

"HTML visualiseren" braucht keine Rechenpower auf dem Server, solange du an Text denkst. Vergiss Grafik, HTML = ASCII Text.
Wenn wie Verbindung zwischen webcam und Arduino aus einem digital Signal oder meinetwegen einem http GET oder POST für (Kamera an / Kamera aus) besteht, kein Problem. Für alles andere bin ich auf deine Projektvorstellung gespannt.

Phase 2:
Der Roboter der nun virtuelle Karten gelernt hat soll nun von einem beliebigen Punkt A nach B geschickt werden können und den Weg ohne aktive Steuerung selbst zurücklegen.

Was versehst du unter "gelernt" ? In Phase 1 hast du etwas gespeichert, was man "Karte" nennen kann. Unklar ist mir, wie daraus "eigene" Aktionen entstehen können. Aber ich bin kein AI Experte...

Wenn du sagst, das ist alles kein Problem für mein Android, nur die Räder und Motoren fehlen, dann ist ein Arduino auf jeden Fall richtig.

d) Speicher für die Karte?
Evtl. für Speicherung auf SD Karte?
Empfehlungen?
Im Auge habe ich: http://www.watterott.com/de/MicroSD-card-breakout-board-v1
Macht das Sinn: http://www.watterott.com/de/Adafruit-Data-Logging-Shield

Der eine kann microSD, der andere hat eine DS1307 Uhr, was für data logging sehr sinnvoll ist.

Und noch eine ganz dumme Frage hinterher? Wie verbinde ich die Shields am besten mit dem Board?

Du nimmst den Arduino in eine Hand, das Shield in die andere, und steckst beide so zusammen, dass es passt. Wie Lego, nur in einem anderen Rastermaß und elektrisch.
Bei einem Breakout Board (statt Shield) ist es etwas komplizierter. Da ist evtl. nur das Rastermass passend und du brauchst noch ein bisschen Bastel-Draht und ein Steckbrett für den Start. Ein paar LED / Widerstände sollte man auch zur Hand haben. Ob man sich ein Lernkit zulegt, in dem noch ein paar Spielsensoren sind, oder ob man gleich mit den Sensoren, die man kennenlernen will, spielt, ist eher Geschmackssache.