Here is one of the simplest walking robots we have seen. It has one actuator and two rigid bodies. The robot is inspired by passive dynamic walkers. Here is how it works: the robot lifts its leg forward, which shifts its center of gravity so it falls onto its front foot. That creates clearance for the next leg to swing through.
[HT: College of Engineering, Carnegie Mellon University]