This paper reviews new challenges in the area of long-term navigation, and new approaches to environment representation and robots capable of coping with dynamic environments. As a result of this review, we propose an appearancebased simultaneous localization and mapping (SLAM) solution which represents the robot environment using an appearance-based topological map. Dynamic environment changes are dealt with using human memory and fixed action pattern concepts. The former is used to build a histogram to register local feature stability, the latter for robot navigation purposes. We take omnidirectional vision and laser range data to extract textured 2D scans as global features, and textured-vertical edges as local features for map updating and robot localization. From the navigational point of view, we consider visual potential field-based behavior to adjust high level motion commands.