This Instructable details a number of tiny robots (e.g. a cubic inch sumo and a pager-bot that fits on a quarter) built by the author. If nothing else, it’ll give you an idea for just how difficult it is to build autonomous, programmable robots on this scale.

Building Small Robots: Making One Cubic Inch Micro-Sumo Robots and Smaller