A mobile robot that maintains a dynamic cognitive map will often find that the information in the map is contradicted by his perceptions, and is therefore incorrect. Such errors may be the result of an earlier misperception, an erroneous matching, an erroneous default inference, computational errors, a change in the world over time, or an erroneous previous error correction. Due to the complexity of inference in forming cognitive maps, domain-independent strategies for error correction, such as data-dependencies or conditional probabilities, are not sufficient by themselves to give a robust error correction scheme. Rather, domain-specific techniques and heuristics must be applied. We dis-cuss some of the basic issues involved in detecting, diagnosing and correcting errors in the cognitive map. We also discuss how a robot may decide whether to take actions in order to gather relevant information.