5
$\begingroup$

Does anyone know of an algorithm that could be used to determine the next action to take to reach a desired state when trained on time-series data?

For example, a robot starts at a certain state, then takes an action to get to another state. This occurs continuously for many iterations (imagine the robot is randomly exploring a room). If the robot is at a specific starting state, and I desire the robot to end up in a different state, is there an algorithm that could recommend the best next action (or set of next actions) to take to reach that final desired state?

One approach I've tried is to use a neural network with the current state and the next state being the input and the action to get from the current state to the next state being the output. The network would know for a single state how to get to a next desired state that is one action away. The issue is, what if the desired state is many actions away?

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ Reinforcement learning with neural network can be tried for this $\endgroup$ – Steffi Keran Rani J Feb 20 '18 at 6:54
  • $\begingroup$ Sounds like the problem that Deep Blue was built to solve. Hopefully your decision trees are shorter. $\endgroup$ – Mars Apr 10 at 18:11
1
$\begingroup$

You can represent the problem as a directed graph where the nodes are the states and the edges are the action that signifies the transition from one state to another if the action is performed. Once this is done you can use various graph path finding algorithms to find the sequence of actions to reach a specific state from a starting state.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's a good idea, though with that approach I'm worried about the size of the graph getting too large if each state/action pair is stored. Ideally I was hoping for some type of regression or neural network that learned how to move from one state to any other state, even if it takes multiple actions to get there. This way it could learn a solution to the problem without storing all the state/action pairs and it could also do predictions for new inputs it has never seen before based on all its passed learning. $\endgroup$ – oalbrecht May 13 '16 at 12:36
  • $\begingroup$ You can use machine learning algorithms but I am not sure if they would work as well. All the problems that have been solved using machine learning are about where the input size and variation is more than the output size and variation whereas in your case the input is just 2 values - start state and end state - and the output is sequence of actions which could be a long vector in many cases. $\endgroup$ – Ankur May 13 '16 at 15:24
  • $\begingroup$ I would be fine with even just knowing the next single action to take to move towards the final state. So if a desired state is multiple actions away, I would like to know the next action to take from the current state that moves towards that final state. $\endgroup$ – oalbrecht May 13 '16 at 15:28
  • $\begingroup$ What about training data? Wouldn't generating that require to have an algo that can find the "next" action to take for desired state. $\endgroup$ – Ankur May 13 '16 at 15:35
  • $\begingroup$ As the robot is exploring, it will train itself for the state/actions it encounters. Initially the algorithm would move the robot mostly randomly until enough data has been collected to make better predictions for how to move from an initial state to a final state. $\endgroup$ – oalbrecht May 13 '16 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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