The article is devoted to the construction of the motion model for agents with memory. Agents can be interpreted, for example, as mobile robots or soldiers. Agents move on the landscape consisting of squares with different passability. The model is based on the cellular automaton with one common to all agents layer corresponding to the landscape and many agent-specific layers corresponding to an agent’s memory. Methods for the random landscape generation are developed. The dependence between configuration entropy of the landscape, efficiency of the path-finding algorithm based on the cellular automaton was found. Also, the dependence of the average speed of the agents’ motion on the landscape configuration entropy was shown.