I can't second the suggestion of checking out David P Anderson's work enough. Here's his web page:
http://www.geology.smu.edu/~dpa-www/myrobots.html
In particular the YouTube video at the bottom of his page is 2.5 hours of autonomous robot insight well worth watching. Also his bots were built back around 2002 using a pro version of the MIT HandyBoard so they definitely could be done with Arduino technology.