We explore how different types of memory can aid spatial navigation in changing uncertain environments. In our simple foraging task, every day, the agent has to find its way from its home, through barriers, to food. The world is non-stationary: from day to day, the location of some barriers or food may change. The agent’s sensing is limited, and its location information is uncertain. Any map construction, and use such as planning, needs to be robust against such uncertainties. Any learning should be adequately fast. We look at a range of strategies, from simple to sophisticated, with various uses of memory. We find that the agent that builds and keeps updating a map, even though the map is partial and noisy, can be substantially more efficient than the simpler agents, as task difficulties such as distance to goal are raised, as long as the uncertainty, from localization and change, is not too large.