To transform and improve the current approach of underwater robotic exploration, we took as a reference benthic marine animals with the aim of unveiling the principles behind their agile legged locomotion. Rather than avoid contacts with the environment as traditional underwater robots do, our robots exploit the interactions to obtain swift and accurate movements. Our approach has the aim of pioneering a new breed of underwater vehicles which can move over underwater structures without disturbing the environment, and could perform muscular works when needed.