3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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: credits Udacity (picture from Udacity lecture about Deep Learning)

$\endgroup$
2
$\begingroup$

As someone who works on tracking and predicting algorithms for missiles to track targets, this type of problem is commonly tackled using things such as Kalman Filters. Typically for a tracking problem, one would assume dynamics of the object you want to track similar to the following:

\begin{align} \dot{p}_{x} &= v_{x} \\ \dot{p}_{y} &= v_{y} \\ \dot{v}_{x} &= \eta_{x} \\ \dot{v}_{y} &= \eta_{y} \\ \end{align}

where $p_{x}$ is the $x$ position, $p_{y}$ is the $y$ position, $v_{x}$ is the $x$ velocity component, $v_{y}$ is the $y$ velocity component and $\eta_i \forall i$ are random variables from a zero mean Gaussian distributions with some variance you may or may not know.

The goal of the Kalman Filter is to use Bayesian estimation to estimate the state variables, which include the position and velocity in this case. Once you have estimates of these states, you can use them to predict where targets will be in the future using closed form solutions to the differential equations.

The nice thing about Bayesian filters, like the Kalman Filter, is they continually refine their estimates as they get more data (assuming you have covariances and other terms tuned appropriately), work for an online stream of measurements, and are fairly efficient.

Also, it is feasible to include acceleration terms you wish to estimate instead of using random noise variables. The problem of tracking an accelerating object, whether a dog or something else, can be a challenge due to compiled noise from sensors and whatnot. But it is still a feasible thing to tackle.

$\endgroup$
1
$\begingroup$

My guess is that nothing is going to work, but the only way to know is to try it on some real data.

As a first cut, I imagine that periodically the dog makes a random change to its running, in such a way that past history before that change won't help you predict its movement afterwards. For instance, the dog might change direction, or suddenly stop to rest, or suddenly take off, or notice his tail and start chasing it, or whatever. A critical parameter will be how often this happens.

Suppose it happens on average about every $y$ seconds. Then one plausible approach is: using the last $y/x$ data points, try to fit multiple models to the data, and see which provides the best fit. One model might be a straight line (the dog running in a straight line, or sitting still for a rest), another model might be a circle (the dog running around in circles), another model might be a low-degree polynomial or spline (the dog running in a curved path). See which model provides the best fit to those data points, and use that to predict the next data points. This requires that $y/x$ be larger than the number of "degrees of freedom" of each model, to avoid overfitting.

But overall, my expectation is that probably you aren't going to get very good results.

$\endgroup$
  • $\begingroup$ Hey - thanks for the response. I agree, I'm not confident in getting good results. I think, as you point out, there are probably multiple models that well-suite the dog's current macro action (chasing his tail, running after a squirrel, ect.). However, predicting when to switch between models is difficult, and surely there will be large errors during the switch process. Additionally, data points obtained from a previous macro-action (ex. chasing tail), probably have no relevance once the action changes (ex. now chasing ball). $\endgroup$ – Kay Jan 20 '17 at 17:13
  • $\begingroup$ @Zed, yes. If you want a more sophisticated model, you could use a Hidden Markov Model, where the hidden state is the dog's current macro action (e.g., chasing his tail) and any associated state/parameters (e.g., the center and radius of the circle he's running in). The hidden state determines a distribution on outputs, and you can use standard methods to try to predict future outputs given the past. Also, you can express the probability of switching from one macro action to another in each time step. My answer proposes a simplified version of that. $\endgroup$ – D.W. Jan 20 '17 at 17:25

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.