Well, that robot that Admin built probably could be autonomous with the right on-board electronics.
Going in a straight line was discussed in a thread here a couple weeks ago. The only real issue with climbing the walls with a design like that is having the robot align itself with the wall. Seems to me a couple good analog distance sensors (like the Sharp GP2D12) mounted on each side of the robot, facing forwards, would help in aligning the robot with a wall.
- Jon