<p>It is important for legged robots to be tolerant of joint malfunctions, especially when working in extreme environments such as the surface of an extraterrestrial planet. However, it is not easy to guarantee tolerance, which requires either the robot structure and controller to be carefully designed for specific failure situations or prompt detection and diagnosis of the faults followed by quick controller reconfiguration. To solve this problem, this paper proposes a method using the automatic robot design method recently proposed by some of the authors. The core of the automatic robot design is in the method of updating the robot topology. In this paper, we combine two distinct robot topology update methods to make learning more efficient. Using a physical simulator, we simulate a situation in which several randomly selected joints malfunction. The simulation reveals that the proposed method efficiently trains a robot to walk even when some of its joints are malfunctioning without the need to switch the controller. Test results show that the obtained pair of robot structures and controllers perform well in situations not experienced during training.</p>