# 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?

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 above—or can at least derive ones that match your problem—you 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 transitions—say, 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 room—you'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.)

• Thanks, your answer was very thorough and helpful. I'll look into RL algorithms and check out that book suggestion. May 14 '16 at 18:14

I think you need to use Reinforcement learning Reinforcement learning. Pybrain library for python has an example similar with your task robot explore maze.

• I think this is what OP is looking for. Usually on this site we prefer longer answers, 1 or 2 paragraphs - so perhaps a short summary of why reinforcement learning is a good match to the OP's problem would improve the answer. May 13 '16 at 14:18

You can't know the next best step unless you know the whole best path. Your task is something similar to TSP (traveling salesman problem).

So, how to find the best path?

Probably you can add penalties (not known) to each state. Then you can define your goal as path with minimal total penalty.

(For robot from your example floor will have 0 penalty and some obstacles >0 penalty).

As I know you can't avoid brute forcing through all possible paths unless your task have additional restrictions.

You need to approximate penalties with data you already have. (So, penalties is parameters in your machine learning task) When you estimated penalties you can compute total penalty for each path, so you can find all paths by brute force and find "best" one.(with smallest penalty)