Hidden markov improvements via hmm-lib

[karussell]

This change was done by @michaz who integrated GraphHopper with the "hidden markov" work from @stefanholder from the module currently available here: https://github.com/michaz/hmm-lib (minor changes were necessary for the integration)

Thanks a lot to all of them! Please try out and give us feedback!

git clone https://github.com/graphhopper/map-matching.git
cd map-matching
git checkout demoui
git submodule update --init --recursive
mvn package -DskipTests
./map-matching.sh action=import datasource=some.pbf
./map-matching.sh action=start-server
# open browser at localhost:8989 and click browse button to select a local GPX file you want to match

Keep in mind: the GPX track has to be entirely within the area you imported while action=import e.g. use this pbf and the attached GPX files

I also added a simple UI using the matching API.

Several improvements are still necessary and possible, like speed improvements, but the matching itself should already produce better results in most cases and the best: without tweaking any heuristic parameters, just the GPX distance error.

The failing tests needs to be investigated (DONE, mostly parameter tweaking to avoid too precise matching)

The original track is thin and black and the match is greenish:

[oblonski]

Cool. Thanks. I just followed your instructions more or less blindly and got this:

[ERROR] Failed to execute goal on project map-matching: Could not resolve dependencies for project com.graphhopper:map-matching:jar:0.7-SNAPSHOT: Could not find artifact de.bmw.hmm:hmm:jar:0.2.0-SNAPSHOT in sonatype-oss-public (https://oss.sonatype.org/content/groups/public/) -> [Help 1]
[ERROR] 
[ERROR] To see the full stack trace of the errors, re-run Maven with the -e switch.
[ERROR] Re-run Maven using the -X switch to enable full debug logging.
[ERROR] 
[ERROR] For more information about the errors and possible solutions, please read the following articles:
[ERROR] [Help 1] http://cwiki.apache.org/confluence/display/MAVEN/DependencyResolutionException
ls: matching-core/target/map-matching-*-dependencies.jar: No such file or directory
Error: Unable to access jarfile action=import

[oblonski]

Seems that it cannot find: de.bmw.hmm:hmm:jar:0.2.0-SNAPSHOT Apart from that the the name looks strange, do I need to install this manually?

[karussell]

strange, should build automatically. Can you try:

cd hmm-lib/
mvn clean install

if content in hmm-lib does not exist -> the command git submodule update --init --recursive was somehow not successfully

[oblonski]

Ok. This worked. Now it says: Started server at HTTP :8989. :). What is the url I need to get the map matching ui?

[karussell]

Edited it: localhost:8989

[oblonski]

I get

{"message": "Not found"}

[karussell]

Ah I need to fix the jetty.resourcebase which is ./src/main/webapp. See the next commit

[Piskvor]

After https://github.com/graphhopper/map-matching/pull/49#issuecomment-213425908 , I tried starting the server:

$ ./map-matching.sh action=start-server
Exception in thread "main" java.lang.UnsupportedClassVersionError: com/graphhopper/matching/http/MatchServer : Unsupported major.minor version 52.0
        at java.lang.ClassLoader.defineClass1(Native Method)
        at java.lang.ClassLoader.defineClass(ClassLoader.java:803)
        at java.security.SecureClassLoader.defineClass(SecureClassLoader.java:142)
        at java.net.URLClassLoader.defineClass(URLClassLoader.java:449)
        at java.net.URLClassLoader.access$100(URLClassLoader.java:71)
        at java.net.URLClassLoader$1.run(URLClassLoader.java:361)
        at java.net.URLClassLoader$1.run(URLClassLoader.java:355)
        at java.security.AccessController.doPrivileged(Native Method)
        at java.net.URLClassLoader.findClass(URLClassLoader.java:354)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:425)
        at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:308)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:358)
        at sun.launcher.LauncherHelper.checkAndLoadMain(LauncherHelper.java:482)

This is on Ubuntu 16.04 with Oracle Java 8; what version 52.0 is unsuitable, and how could I fix this?

[karussell]

@Piskvor Thanks for trying this out. What does "java -version" say and what "javac -version"? If 1.7 or lower you need to configure the default java to be at least 1.8

[Piskvor]

@karussell: Aha! Turns out that javac was correctly set to 1.8, but java was still pointing at the 1.7 install. Thanks!

[karussell]

Thanks - good to know - also let us know if you find problems with the new approach. We'll merge this very soon, potentially as optional for now so people can use both, not sure if the old version has advantages though (maybe calculation speed?)

[stefanholder]

The hidden Markov approach is certainly slower because it requires to compute the shortest path between all pairs of consecutive map matching candidates. If we assume a constant number n of candidates for each GPS positon then n² shortest paths need to be computed for each GPS position except the first. Instead of computing each shortest path individually, a single-source multi-target routing can be used to speed up performance. This is because only n single-source multi-target routings are necessary per GPS position. It seems that graphhopper already provides a single-source multi-target routing with DijkstraOneToMany.java.

To use single-source multi-target routing with the current hmm-lib API, one needs to compute and save all shortest paths before actually invoking the hmm-lib. The current implementation in MapMatching.java already stores all shortest paths so that the entire matched route can be retrieved later.

I am currently working on an improved hmm-lib API, which can be called iteratively for each time step. This allows calling the single-source multi-target router while the GPS trace is processed. Moreover, the paths between matched GPS positions (the entire matched route) can be retrieved from the hmm-lib after the complete GPS trace is processed, so the caller will no longer need to store all shortest paths. As these improvements still need some time, I suggest using the current hmm-lib API for now and migrating later to the improved version.

Another performance improvement would be to abort the routing as soon as the shortest path would be longer than what could reasonably be travelled in the time between the two GPS positions. In this case the transition probability needs to be set to zero. This is also described in the paper “Hidden Markov Map Matching Through Noise and Sparseness by Paul Newson and John Krumm”, Chapter 4.2.

[karussell]

Thanks, sounds good!

It seems that graphhopper already provides a single-source multi-target routing with DijkstraOneToMany.java.

We have a version in the map matcher implemented which is more lightweight per request. See CustomDijkstra

I am currently working on an improved hmm-lib API, which can be called iteratively for each time step.

I'll hopefully have a bit time this week to finally merge this PR. Maybe I keep both algorithms if not too much work.

as soon as the shortest path would be longer than what could reasonably be travelled in the time between the two GPS positions.

I think this is not that simple but we should try it :)

[karussell]

After several tests I've merged this. We'll work on performance and quality etc in the master. Currently the old algorithm is completely removed.

Thanks @michaz & @stefanholder !

[karussell]

@harregui saw you do a comparison of map matching for your PhD - would love to get feedback on this one here ... maybe @stefanholder too :)

[stefanholder]

Sure, this would be great!

[michaz]

Don't read my commit messages, please.