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?
Predicting next action to take to reach a final state
machine learning;neural network;predictive modeling;time series;deep learning
The problem you've described can be formalized as a Markov decision process, the foundational problem of reinforcement learning. In broad strokes, reinforcement learning is concerned with how agents (robot) in a given environment (room) out to take actions (movements from one state to another) to maximize some notion of reward. Formalizing your problem requires defining a few parts of an MDP model:Set of states $S$Set of actions $A$A reward function $R(s)$, defining the reward of arriving in a given state. In your case, a simple scheme of $R(s) = \mathbb{1}(s = s_{goal})$ is one option.A transition function $T(s,a,s')$ giving the probability of winding up in state $s'$ having taken action $a$ from state $s$.(Note that you can model deterministic transitions by returning a value of $1$ for a single $s'$.)If the problem goes on infinitely, you'll also need a discount factor $\gamma$.In reinforcement learning, the term optimal policy describes a function that returns the best action to take from a given state. I.e., this gives the recommendation you're looking for.If you know all of the model components described aboveor can at least derive ones that match your problemyou can use a variety of planning algorithms to find the optimal policy, e.g. value iteration or policy iteration. If you don't know the rewards and transitionssay, for example, that the robot is seeking a sensor attached to a charging station and you don't know where it is or the size of the enclosing roomyou'll likely need to explore algorithms that observe action-outcome pairs and try to learn optimal policy from these learning episodes. A full description of these is beyond the scope of your question, but a good place to start is Sutton & Barto's Reinforcement Learning: An Introduction. An html version is freely available. Another resource is RL udacity course produced by Georgia Tech.In your example, you may also want to research potential-based reward functions. Very loosely, one potential might be the robot's distance to goal state, and the reward would be based on changes to this potential value. (This is described in a paper by Ng, Harada and Russell, and in unit 6 of the GA Tech course mentioned above.)