1
$\begingroup$

As far as i can tell, the markov assumption is quite ubiquitous in probabilistic methods for robotics and i can see why. The notion that you can summarize all of your robot's previous poses with its current pose makes many methods computationally tractable.

I'm just wondering if there are any classic examples of problems in robotics where the markov assumption cannot be used at all. Under what circumstances is the future state of the robot necessarily dependent on the current and at least some past states? In such non-markovian cases, what can be done to alleviate the computational expense? Is there a way to minimize the dependence on previous states to the previous $k$ states, where $k$ can be chosen as small as desired?

Improve this question
$\endgroup$
1
  • $\begingroup$ "Under what circumstances is the future state of the robot necessarily dependent on the current and at least some past states?" Such as if the robot were turned off, and moved to a different position before being turned back on? $\endgroup$
    – Mhz4.77
    Commented Dec 29, 2014 at 1:02

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If the sensors are not "up to the task", how can it even be possible to proceed with the task at all? It seems impossible. $\endgroup$
    – Paul
    Commented Jan 1, 2015 at 3:25
  • 1
    $\begingroup$ Failures can invalidate current measurements making a recovery system that can look at the past mandatory, and, most of all, uncertainties can always take place so that robustness can be increased only by means of some sort of memory. Then, to be honest, the Markov property in control theory is never ensured: just consider the simple case of filtering itself. $\endgroup$
    – Ugo Pattacini
    Commented Jan 1, 2015 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.