# Predicting next action to take to reach a final state

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?

• Reinforcement learning with neural network can be tried for this Feb 20, 2018 at 6:54
• Sounds like the problem that Deep Blue was built to solve. Hopefully your decision trees are shorter.
– Mars
Apr 10, 2020 at 18:11

## 1 Answer

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.

• 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. May 13, 2016 at 12:36
• 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. May 13, 2016 at 15:24
• 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. May 13, 2016 at 15:28
• What about training data? Wouldn't generating that require to have an algo that can find the "next" action to take for desired state. May 13, 2016 at 15:35
• 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. May 13, 2016 at 15:38