Predicting walking routes using PyTorch

I'm working on a project that uses sensors to monitor a persons location. These devices simply record the current GPS coordinates and ping them back to a server (the coordinates will then be converted to a simple-grid representation to account for noise in GPS). What I want to try and do is after recording a users routes, train a neural network to predict the next coordinates, i.e. take the example below where a user repeats only two routes over time, Home->A and Home->B.

I want to implement a model that once trained, could then be fed with real-time coordinates e.g. (15, 4), (14, 4), (13, 4) and predict that the next location is (12, 4), or with the other route (15, 10), (15, 11), (15, 12) and predict that (14, 12) is next.

I had success using LSTMs in Keras before, but that was essentially a regression problem e.g. yearly sales. I initially assumed an RNN/LSTM approach would be best for this route prediction, but now I'm not so sure since each route is discreet, how would I decided what part of the sequence is designated input and which as output for training.

Any ideas, guidance on how to tackle this problem would be really appreciated! I appreciate that there might be better non-neural net approaches, but I really want to try and use deep learning to tackle this. I'm currently working in PyTorch if that helps in terms of implementation options.

Note: I wasn't sure if this was a better fit here or Stack Overflow, so please shout if it should be moved.

• Possible coordinates are only from 15x15 or it could be very large number? – podludek Jul 17 at 14:40
• Conceptual statistical/machine learning questions are welcome here, questions about implementation are off-topic. If you can highlight the conceptual parts that you need help with, you are likely to get better answers (and avoid having the question closed once the bounty period expires). – mkt Jul 17 at 14:50
• Can't help you if u can't define problem. – podludek Jul 18 at 10:58
• Apologies, I hadn't checked in. I guess the grid could be very large, e.g. if the area of interest is a city then the grid of coordinates will need to be large enough to cover that area. – Philip O'Brien Jul 18 at 11:31

RNNs are most commonly used as density models over some space of sequences. To be more precise, if we have some sequence $$X = x_1, x_2, \ldots, x_k$$ then our model describes the distribution

$$P(X) = \prod_{i=1}^k p(x_i | x_{

(which is valid by the product rule). More specifically, our RNN models each conditional term $$p(x_i | x_{ as $$x_i \sim \mathcal{N}(\mu, \sigma^2 = \text{RNN}(x_{ in the continuous case, or as is more common in language modeling, $$x_i \sim \text{Cat}(p = \text{RNN}(x_{.

I'm not so sure since each route is discreet

As the above examples show, RNNs can be used for both discrete and continuous valued sequences.

how would I decided what part of the sequence is designated input and which as output for training.

An RNN density model doesn't have an input or output in any conventional sense. Rather, you train by maximizing the log-likelihood, which nicely decomposes as $$\log P(X) = \sum_i \log p(x_i | x_{

predict that the next location

Just a note on this: generally, we prefer to model distributions over sequences rather than predict a single sequence. The reason for this is that regressing to a single mean sequence often results in unnatural or undesireable trajectories -- consider a car approaching a T-intersection, where it can either go left or right. But the mean trajectory is to go straight, where there is no road -- clearly there's no point in regressing such a solution.

What an RNN density model gives you is the ability to sample sequences from $$P(x_{\geq i} | x_{< i})$$, or to find the mode of such a distribution via beam search. The mode doesn't suffer from such problems as the mean often does, and it's probably what you want.

Discrete coordinates shouldn't be a problem since you can easily map them into [0;1]x[0;1]. Using any recurrent network would be fine (including LSTM), however, I suggest you look into an attention mechanism instead of LSTM which could be beneficial in your case.

As input you set mapped sequence of x,y from [0;1]x[0;1] as output you get a vector of current position [0;1]x[0;1] then you should map output into your discrete domain. Obviously, you can expect that NN output wouldn't fit perfectly into your discrete domain. In that case, you can estimate the nearest point or coordinate i. e. by simply rounding.

I suggest you first test your NN with optimization-based on RMSE. I think it could perfectly fit the problem, because of euclidean space.

If sequence length is fixed (like last 15 locations) or has only small fluctuations you can also apply convolutions layers instead of LSTM.