First of all, thank you very much for your rapid and extensive reply. This is very much appreciated and really shows the great community that is behind the Arduino platform 
Then as to your reply: you make some excellent points. I was thinking and thought that perhaps I could also add a second battery pack and use that just to power the DC motors as a dedicated power source, correct? This would also prevent the board from crashing when power is low and the robot can still go on and scan the room, etc. although from a static position. Or am I wrong on this?
I'm happy to have a better understanding about powering the Arduino board, but I must say I am bit disappointed by the runtime I can expect from this power source. The point is that the batteries need about 18 hours of charging time, after which I can power the robot for 15 minutes. Hardly enough to map the entire room as I first imagined (I also bought a 180 degrees servo, ultra sonar sensor, a digital compas and Xbee shield + module; I don't really see regular NiMH batteries powering that all together for longer than a few minutes).
Are there any other options I could look into? Perhaps a li-ion battery? Does that provide a longer running time, or at least a shorter charging time? Are there any other options?
Also, is it possible to charge the batteries (or the li-ion if that's a good option to use) while they are connected to the Arduino? Using something like this: Lithium Ion/Polymer USB Battery Charger IC - MAX1555 - COM-00674 - SparkFun Electronics ?
Well, thanks again for your time. Very much appreciated
Kind regards,
Vincent