Memory of the past is required whenever failures and/or inadequacy arise in the perception layer of the robot thus affecting significantly its current representation of the world, forcing eventually to apply some sort of backtracking strategies.
Quoting S.D Whitehead and Long-Ji Lin in their paper "Reinforcement learning of non-Markov decision processes":
These non-Markov tasks are commonly referred to as hidden state tasks, since they occur whenever it is possible for a relevant piece of information to be hidden (or missing) from the agent’s representation of the current situation.
Hidden state tasks arise naturally in the context of autonomous learning robots. The
simplest example of a hidden state task is one which occurs when the agent’s sensors
are inadequate for the task at hand. Suppose a robot is charged with the task of sorting
blocks into bins according to their color, say Bin-l for red, Bin-2 for blue. If the robot’s sensors are unable to distinguish red from blue, then for any given block it can do no better than guess a classification. If there are an equal number of blocks of each
color, then guessing can do no better than chance. On the other hand, if the robot can detect color, it can easily learn to achieve 100% performance. The former case corresponds to a non-Markov decision problem, since relevant information is missing
from the agent’s representation. The latter case is Markov since once a color sense is
available the information needed to achieve optimal performance is always available.
In general, if a robot’s internal representation is defined only by its immediate sensor
readings, and if there are circumstances in which the sensors do not provide all the
information needed to uniquely identify the state of the environment with respect to the
task, then the decision problem is non-Markov.