Arduino and complex robots? Possible?

I want to build a larger robot that moves outdoors

Wheeled, tracked, or biped?
On grass, dirt, or asphalt?
Level or sloped? Steps?

About the only real difference between a small robot for indoor use and a large robot for outdoor use that I can see is that the outdoor version probably won't encounter carpet.

Well, that and it will be heavier, need more torque, and blow through batteries faster.