It is generally accepted that cognitive robots need to be able to represent and reason about the relevant aspects of the environment they operate in. Complications arise because sensors are noisy and the effects of actions are often uncertain. In this lecture I will briefly review a few milestones in the development of cognitive robots and then address some of the many research challenges that still need to be addressed in order to arrive at truly cognitive robots.