Despite over 50 years of research in robotics, most existing robots are far from being as resilient as the simplest animals: they are fragile machines that easily stop functioning in difficult conditions. The goal of this proposal is to radically change this situation by providing the algorithmic foundations for low-cost robots that can autonomously recover from unforeseen damages in a few minutes. The current approach to fault tolerance is inherited from safety-critical systems (e.g. spaceships or nuclear plants). It is inappropriate for low-cost autonomous robots because it relies on diagnostic procedures, which require expensive proprioceptive sensors, and contingency plans, which cannot cover all the possible situations that an autonomous robot can encounter. It is here contended that trial-and-error learning algorithms provide an alternate approach that does not require diagnostic, nor pre-defined contingency plans. In this project, we will develop and study a novel family of such learning algorithms that make it possible for autonomous robots to quickly discover compensatory behaviors. We will thus shed a new light on one of the most fundamental questions of robotics: how can a robot be as adaptive as an animal? The techniques developed in this project will substantially increase the lifespan of robots without increasing their cost and open new research avenues for adaptive machines.