Co-evolution (i.e. the evolution of two or more competing populations with coupled fitness) has several interesting features that may potentially enhance the power of adaptation of artificial evolution. In particular, as discussed by Dawkins and Krebs , competing populations may reciprocally drive one another to increasing levels of complexity by producing an evolutionary “arms race”. In this paper we will investigate the role of co-evolution in the context of evolutionary robotics. In particular, we will try to understand in what conditions co-evolution can lead to “arms races” in which two populations reciprocally drive one another to increasing levels of complexity.