PICO from Zac Wheeler of PoorRobot.com is claimed to be the worlds smallest autonomous, self powered robot. Zac attempted the robot a few years back but due to small components and power supply not being available to him at the time he put it on the back burner until now.
Pico has infrared obstacle detection and an onboard microcontroller.
12.5mm on a side
0.125 cubic inch / 2cc volume
15 minutes run time
0.5f/s - 0.15m/s Max speed
Head over to Zac's site for further design and build details, but don't leave before watching the video of his little creation below.