Motion Prediction Problem

Setup: Suppose you have a dog running around in a fenced yard (2D). Every x seconds, you mark down the coordinates of the dog. This dog is a puppy - easily distracted, full of energy, and very speedy :) Expect quick, jagged motions, running in circles, and periods where he needs to catch his breath :)

Problem: At any point, you would like to predict where the dog is going to be kx seconds into the future (k being an integer).

I would like to know what types of techniques may be most suitable for solving this? My knowledge breadth in this subject matter is very limited. I'd like to identify a few candidates that I could then deep-dive into

• My original thought was to use Langrange-form polynomials to interpolate the latest n points, then extrapolate. The dog's path is continuous, and smooth, so a polynomial approximation seems reasonable; however, the danger lies in forcing the polynomial through the available data. It seems like we want the polynomial that best approximates the data, rather then the lowest degree polynomial that exactly fits the available data - especially if x is substantial.

• Ideally, since every prediction can be measured against what actually occurred, there should be some method of learning on-the-fly. However, since the data isn't static, I don't know how I would apply techniques of somewhat aware of like SVMs or linear regression.

I apologize if I didn't use terms correctly, this is not my area of expertise.

I would try to train a Recurrent Neural Network for this problem, the LSTM architecture is particularly interesting for time series prediction.

Sources:

• karpathy.github.io/2015/05/21/rnn-effectiveness/

• colah.github.io/posts/2015-08-Understanding-LSTMs/

You would of course need a training dataset consisting of a sequence of events. Let's say $x$ and $y$ coordinates for every timestamp $t$, (possibly $z$ as well to predict a jumping puppy).

Both the network input layer and the output layer would consist of 2 units.
Then you would train your model to predict $(x_{t+1}, y_{t+1})$ given $(x_{t}, y_{t})$. Once the network is trained, you can predict the position of the dog at any point in the future.

Let $M$ be our trained model and let's say you want to predict the position of the dog at time $k$ and you know the current position of the dog at time $t$.

$M(x_{t}, y_{t}) = (x_{t+1}, y_{t+1})$

$t = t+1$

$M(x_{t}, y_{t}) = (x_{t+1}, y_{t+1})$

$...$ increment $t$ and keep predicting until $t+1 = k-1$

$M(x_{t+1}, y_{t+1}) = (x_{k}, y_{k})$

Put in pictures this corresponds to:
(picture from Udacity lecture about Deep Learning)

StackExchange Computer Science Q#68990, answer score: 4