  Legged locomotion is commonly studied and expressed as a discrete set of gait
patterns, like walk, trot, gallop, which are usually treated as given and
pre-programmed in legged robots for efficient locomotion at different speeds.
However, fixing a set of pre-programmed gaits limits the generality of
locomotion. Recent animal motor studies show that these conventional gaits are
only prevalent in ideal flat terrain conditions while real-world locomotion is
unstructured and more like bouts of intermittent steps. What principles could
lead to both structured and unstructured patterns across mammals and how to
synthesize them in robots? In this work, we take an analysis-by-synthesis
approach and learn to move by minimizing mechanical energy. We demonstrate that
learning to minimize energy consumption plays a key role in the emergence of
natural locomotion gaits at different speeds in real quadruped robots. The
emergent gaits are structured in ideal terrains and look similar to that of
horses and sheep. The same approach leads to unstructured gaits in rough
terrains which is consistent with the findings in animal motor control. We
validate our hypothesis in both simulation and real hardware across natural
terrains. Videos at https://energy-locomotion.github.io
