New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

MultiLevel Dijkstra (mld) research paper #4797

Closed
AnixPasBesoin opened this Issue Jan 15, 2018 · 11 comments

Comments

Projects
None yet
3 participants
@AnixPasBesoin

AnixPasBesoin commented Jan 15, 2018

TL;DR.
I'm looking for is the research paper that the current code implements.
My issue
I'm interested in the MLD algorithm implemented in the current version of OSRM.
As far as I've understood, the current implementation allows for independent customization of metrics of the road-network's graph. My first intuition was that this was an implementation of CRP, but after I've read the paper, and gone through some of the OSRM code, I've realized that the "partition" step differs from what was proposed in the CRP paper. This made me wonder if CRP was NOT what was implemented here.
So my issue is the following: I'm looking for is the research paper that the current code implements.

@TimMcCauley

This comment has been minimized.

TimMcCauley commented Jan 18, 2018

@AnixPasBesoin how about this? Maybe not a research paper.. but .. https://github.com/michaelwegner/CRP

@dmitry-akimov-dXgjvQjNiMuVYecJ

This comment has been minimized.

dmitry-akimov-dXgjvQjNiMuVYecJ commented Jan 18, 2018

@TimMcCauley That's correct - it is an implementation of the following research paper:

Delling, Daniel, et al. "Customizable route planning in road networks." Transportation Science (2015).
https://scholar.google.com/scholar?cluster=5188233396400795462&hl=en

The overall method is called "Customizable route planning," and the "Multilevel Dijkstra" is a part of that method, namely, the query phase.

@dmitry-akimov-dXgjvQjNiMuVYecJ

This comment has been minimized.

dmitry-akimov-dXgjvQjNiMuVYecJ commented Jan 18, 2018

@AnixPasBesoin The partition step is essentially the same - they just implemented it via a different algorithm, InertialFlow, that originally does a nested dissection, they adapted it to produce cells.

@dmitry-akimov-dXgjvQjNiMuVYecJ

This comment has been minimized.

dmitry-akimov-dXgjvQjNiMuVYecJ commented Jan 18, 2018

Below is a related issue I've posted and no one ever responded:

#4032

@TimMcCauley

This comment has been minimized.

TimMcCauley commented Jan 18, 2018

@dmitry-akimov-dXgjvQjNiMuVYecJ what does this mean exactly if this were a patent issue?

@dmitry-akimov-dXgjvQjNiMuVYecJ

This comment has been minimized.

dmitry-akimov-dXgjvQjNiMuVYecJ commented Jan 18, 2018

@TimMcCauley I guess, if the algorithm is patented, one cannot use it without Microsoft's permission, and it is probably not a good idea to put it into an open source project.

The question is whether the implementation in OSRM qualifies for the patent. I would say the method is essentially the same, so it might be the case.

Mapbox is a serious company and might have obtained such permission though.

Therefore, it would be nice if someone from Mapbox clarified this.

@dmitry-akimov-dXgjvQjNiMuVYecJ

This comment has been minimized.

dmitry-akimov-dXgjvQjNiMuVYecJ commented Jan 22, 2018

@TheMarex I see you are responding to other issues. Would you mind saying a couple of words regarding the topic being discussed?

@AnixPasBesoin

This comment has been minimized.

AnixPasBesoin commented Feb 4, 2018

After spending some time going through various parts of the current OSRM code, and reading some state-of-the-art papers, here are my conclusions:

  • MLD is (as far as I've understood) the first approach implemented in OSRM that uses Customizable Metrics. This misleads the reader to think that it's a pure implementation of CRP.
  • In order to provide a Multilevel Routing for MLD, a Hierarchical Partitioning of the road network is needed. I'm assuming that for Patent Issues (as @dmitry-akimov-dXgjvQjNiMuVYecJ mentioned), the OSRM team had to chose a different approach than PUNCH, and ultimately has opted for Inertial Flow.
  • At first, I thought that there must be a single paper describing the whole MLD pipeline, but shortly after, I realized that what I was looking for was the Partitioning Step, which is described in the paper I've linked above.
@dmitry-akimov-dXgjvQjNiMuVYecJ

This comment has been minimized.

dmitry-akimov-dXgjvQjNiMuVYecJ commented Feb 4, 2018

@AnixPasBesoin I am afraid I did not get what you meant in the part about the MLD and the "Customizable Metrics" - having customizable metrics is kind of the whole point of these algorithms, so what else could it be instead? The MLD is the query phase of the CRP, namely a modification of Dijkstra's algorithm that works on the overlay graph produced by the partitioning step. There is the bachelor thesis on the topic from KIT, which explicitly uses the term "Multilevel Dijsktra" for describing the CRP's query phase. (That bachelor thesis also makes up for a more comprehensive explanation of the method than the research paper, as it usually happens, i.e. if you want to understand a research paper better, find a thesis.)

The method used in OSRM is possibly not a "pure" implementation of the research paper, whatever that might be, but changing the partitioning method does not change the overall method, which is still the CRP to me, at least that is how I would refer to the method used in OSRM. There are other methods, and the OSRM's one is the CRP to me to distinguish it from others.

I must admit I have only skimmed through the CRP research papers, as I had dismissed the method due to the patent issues, and only skimmed through the OSRM source code as well, so I might be missing something, and would appreciate if someone corrects me.

The patent US20130231862A1 specifically mentions that any partitioning method can be used, and, indeed, it is again not important for the method in its entirety. The OSRM team have implemented InertialFlow, apparently, because it was the simplest method, even though it should produce suboptimal results and is kind of a hack, and proper partitioning methods are quite involved.

I have not gone through the subject in detail, but it still seems to me that the implementation in OSRM might qualify for the patent, and the method is essentially CRP.

I am personally interested in this subject because I have considered CRP as one of the methods I could use in my work, but I skipped it in favor of other methods because of the possible patent issues. I have also considered using OSRM's source code, and now it is unclear what to do with it, as it may be subject to the same patent issues also.

People from Mapbox seem to ignore my questions so far.

@AnixPasBesoin

This comment has been minimized.

AnixPasBesoin commented Feb 5, 2018

@dmitry-akimov-dXgjvQjNiMuVYecJ last time I checked this project, it was using CH. Now, in the readme page, MLD is presented as an alternative to CH. It is not said that what is meant by MLD is only the query phase of the new approach but is rather presented as the name of the whole. Knowing that CH didn't allow Customizable Metrics, it gets quite confusing to grasp what changes have been made since last time. That's what I meant to clarify by my previous comment.
For the patenting issue, I'd really want to hear more from the OSRM team... But this is not relevant to the issue I posted, that's probably why we're not getting any comments about this so far...

@dmitry-akimov-dXgjvQjNiMuVYecJ

This comment has been minimized.

dmitry-akimov-dXgjvQjNiMuVYecJ commented Feb 5, 2018

@AnixPasBesoin Well, the patenting issue is actually relevant to your original question, as it depends on whether the CRP is used here or not, so I had been basically interested in the same question as you, whether it is related to patents or not. Unfortunately, we did not get any comments from the OSRM team on this whole topic at all.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment