I didn't see a portable power source for your robot. 
Maybe you want to get one of these to power the Arduino using a 9V battery.
You may also want to get a separate battery holder to power the motors (maybe you can power them using rechargable batteries).
http://www.sparkfun.com/commerce/advanced_search_result.php?keywords=battery+holder&x=0&y=0&search_section=products
Sounds like a cool project, please keep us posted here.