Roadmaps, generated by pre-processing of the known environment, have recently been a popular approach to robot motion planning. Generally designed for static environments, roadmaps are often invalidated by any anomaly between the real world and the model of the environment. We investigate the effect on roadmaps when sensor information indicates such an error and describe an algorithm which, by performing further pre-processing on the known environment, generates a mapping between points in the workspace and the roadmap. Used during on-line planning the mapping enables a valid, although not necessarily connected, roadmap to be maintained if such an error is discovered. We then present a divide and conquer algorithm which uses guided random motion to attempt to reconnect paths affected by the error.This is a first step towards a global planner that could be used in evolving environments.