Algorithm for coherent motion. Which bus is app user on?

Question

I am currently working on an app with a map of the city, with markers for each bus. As a feature, the phone should show which bus the user is on.

To achieve this I am working on building a function that consumes a stream of a set of buses and their positions (Stream<Set<Tuple2<BusId, Location>>>), and a stream of phone location, to produce a Stream of bus predictions. The prediction should contain a confidence level.

The function should return the current prediction in real-time, and handle scenarios where the user changes the bus.

How could this be accomplished?

Both streams contain very precise locations at a rate of once every second.

Answer 1

You basically have a table as follows:

Time | Person | Bus1 | Bus2 | ... | BusN  |
=====+========+======+======+=====+=======+
  0  | (x,y)  | (x,y)| (x,y)| ... | (x,y) |
  1  | (x,y)  | (x,y)| (x,y)| ... | (x,y) |
...

x,y being the coordinates of that Person/Bus at a specific point in time.

You then calculate the distance for each pair of Person/Bus and timepoint and map each Bus-Person-distance column to its rolling average of approx. 20 to 60 seconds (depends on precision and stuff like this).

You can then map the distances for each time-segment to a probability to be in a specific bus (if the location data quality is high, this should be pretty easy).

If you then plot the probabilities over time, for most times a specific bus should be on top. If this probability gets lower and another one rises, the person is likely changing the bus (or the buses are near each other).

PS: If your location API has methods for distance calculations, use those. If you have to do it yourself, there are some formulas to get from latitude and longitude to something for which the Euclidean distance ($D = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$) works (using that with latitude/longitude is wrong in general: see here.

PPS: I am not entirely sure, whether this problem is actually related to Computer Science.

Answer 2

I ended up solving this using Tensorflow. For every app position recording, and every bus I created a timeline of displacement between bus and app position recording.

I got a CSV file looking like this:

displacement-30,displacement-20,displacement-10,displacement0,displacement10,displacement20,displacement30,timeDeviation-30,timeDeviation-20,timeDeviation-10,timeDeviation0,timeDeviation10,timeDeviation20,timeDeviation30,onBus
0.01,0.013,0.023,0.017,0.012,0.006,0.021,0.5,0.5,0.5,0.5,0.5,0.5,0.5,1
0.42,0.42,0.42,0.42,0.425,0.407,0.405,0.47,0.48,0.49,0.5,0.498,0.501,0.503,0
0.42,0.42,0.42,0.425,0.407,0.405,0.406,0.477,0.487,0.497,0.5,0.498,0.5,0.498,0
0.42,0.42,0.42,0.425,0.407,0.405,0.406,0.482,0.492,0.502,0.5,0.503,0.499,0.498,0
0.42,0.42,0.425,0.407,0.405,0.406,0.406,0.489,0.499,0.502,0.5,0.502,0.5,0.505,0
0.42,0.425,0.407,0.405,0.406,0.406,0.405,0.497,0.5,0.498,0.5,0.498,0.503,0.501,0
0.42,0.425,0.407,0.405,0.406,0.405,0.406,0.503,0.501,0.504,0.5,0.499,0.497,0.497,0
0.425,0.407,0.405,0.406,0.406,0.405,0.406,0.502,0.5,0.502,0.5,0.505,0.503,0.503,0
0.425,0.405,0.405,0.406,0.405,0.406,0.406,0.502,0.497,0.501,0.5,0.498,0.498,0.498,0
0.405,0.405,0.406,0.405,0.406,0.406,0.405,0.499,0.503,0.502,0.5,0.5,0.5,0.5,0
0.405,0.406,0.405,0.406,0.406,0.405,0.428,0.503,0.502,0.5,0.5,0.5,0.5,0.5,0
0.406,0.405,0.406,0.406,0.405,0.428,0.424,0.502,0.5,0.5,0.5,0.5,0.5,0.5,0
0.405,0.406,0.406,0.405,0.428,0.424,0.424,0.5,0.5,0.5,0.5,0.5,0.5,0.499,0

Each displacement is normalized as 0-1000 meters. The time deviation is used in case an incomplete timeline needs to be processed.

I will expand the features to include if bus was detected using Bluetooth beacons, the heading between bus and app position.