Routing instructions with complex junction

[Karry]

When some junction is mapped in detail, routing instructions may be misleading.

For example this junction in Prague:

when routing from the north to south-east, routing just generates "name change" instructions, but user would expect "turn left" at least.

./Demos/Routing  czech-republic 50.10355 14.53185 50.06029 14.55739
...
----------------------------------------------------
     At| After|  Time| After|
----------------------------------------------------
  0.0km         0:00h        Start at 'Start'
                             Drive along highway_primary 'Průmyslová (601)'
  3.7km  0.0km  0:04h  0:00h Way changes name from 'Průmyslová (601)' to 'unnamed road'
  3.8km  0.0km  0:04h  0:00h Way changes name from 'unnamed road' to 'Černokostelecká (333)'
  4.3km  0.0km  0:05h  0:00h Way changes name from 'Černokostelecká (333)' to 'Kutnohorská (333)'
  5.6km  0.0km  0:06h  0:00h Pass: Frolík & Rataj
  5.7km         0:06h        Target reached 'Target'

[Karry]

Testing other routing engines:

• OSRM (OpenSource routing machine) is wrong too

    | 1. Start on Průmyslová (601) | 3.8km
    | 2. Slight left onto unnamed road | 30m
    | 3. Turn left onto Černokostelecká (333) | 400m
    | 4. At the fork turn right onto Černokostelecká (333) | 80m
    | 5. Continue on Kutnohorská (333) | 1500m
    | 6. Reach destination |  

• GraphHopper is closer to the result that I would expect:

    | 1. Continue onto Průmyslová | 3.8km
    | 2. Keep left | 400m
    | 3. Continue onto Černokostelecká | 1.5km
    | 4. Arrive at destination |  

• Valhalla is confusing IMHO

    | 1. Drive southeast on Průmyslová/601. Continue on Průmyslová. | 3.8km
    | 2. Take the exit on the left. | 40m
    | 3. Bear left toward 2/Mladá Boleslav/Hradec Králové. | 300m
    | 4. Keep right to stay on 333. | 1.5km
    | 5. Your destination is on the right.

• mapy.cz are fine, but they are not using OSM data in Czech republic and their routing engine is not open-source
• maps.google.com are fine too

[Framstag]

I see a few suboptimal descriptions in our solution:

• We miss the turn left - why? Our turn detection is simple. Why does it fail in this case? This is the place where "hat happens in reality" badly fail.
• The mentioning of the unnamed road is correct but misleading - We could fix this by some heuristic post processing. If we have turns a short "unknown road" we skip the unknown road....on the assumption that this can happen in complex junctions.
• The change to "Kutnohorská" is correct? Though I miss a "keep right" at that fork of the road?

The principle problem is that we do not have a junction explicitly mapped. There is no tag "junction". We could write a post processor that tries to take some heuristics to detect junction and set a state, that could be used by another postprocessor to clean up or change behavior. But such a state machine can make things worse if state is calculated wrongly, and especially not resetted correctly. Think of a few junctions in a row or similar...

What would be the ideal description you would expect or find helpful?

[Karry]

Hi Tim. Do you have any experience with machine learning? I'm considering that some kind of ML would be able to generate instructions for such complex junctions. I just chat about this possibility with ChatGPT, it was fun ;-) It is wrong in some aspects (like suggesting proprietary software when I was asking for open-source libraries), but it provides me some hints...

[Framstag]

I've read a book a few years ago about (classical) machine learning, which uses mathematical approached for data categorization. I have also implemented a italian card card application years ago and tried to use a neuronal network to train a computer opponent. I however failed after a few days because I did not get the neural network stable. There was always the idea to come back and use a library for the low level stuff and concentrate on the handling of input, lerning and replay. I never had time :-/

AFAIK for training a neural network you need:

• A good technical description of the problem
• Training material (good routes, bad routes)
• Possibly post processing to get the training material in good shape
• Or a very good evaluation functions that allows you to give the neuronal network the required feedback for training (normally you have training material because if you have a good evaluation method you likely can just program it). For a card game an evaluation function should be OK, since the game is short and offers a clear winner ;-)
• CPU or better GPU power

The question in the concrete context is first: What should it learn? What exactly is the problem?

• Getting a feeling for curved roads and crossings?
• Possibly, learning, how people build roads?
• Should we have a trained neural network for the world, for each country? Where and what is the "hidden rule"?

The concrete problem: Where do you get (much) training material and how do you know what is right and wrong? If you are google and have traffic information (you know how people drive over the crossing) the would be a way. But what would the system learn from it? If I give it the entry to the crossing and the exit of the crossing and the form of the crossing it might learn how people would drive through the crossing (and how not). But is this the problem to solve? You must also be aware, that the solution of the system might not match to actual crossing it is just the generalized behaviour for crossing that look alike.

Looks like the ChatGPT answer is similar (but not that specific to the concrete problem). I would take another appoach as described above. I would try to find a generalize image-like description of crossing with start and end point and possible hint points or similar. Trainig data would offer actual car navigation tracks. The system then have to "guess" the tracks from "new" material with given, start, end and hint points.

I do not think a decision tree would be helpful, but of course might be in error.

For general navigation information you "just" teach the KI how people drive on a given road and through given turns with given parameter (max speed, state of the road, angles...) and it is able to reproduce this information. If you a driving races on streets this might be (very) helpful but for a more general use!?

Do not trust ChatGPT. It is just the statistical most relevant answer of the internet. I assume most people on the internet have no good idea of KI, so likely you will also not get the best answer. IMHO ChatGPT does not "know" it just has a feeling for how likely the sentence will continue.

Just my 2 cents and ideas :-)

[Karry]

What exactly is the problem?

I don't want to improve routing now. It works good enough. I "just" want to get better route description with voice commands. And better voice commands for car navigation may be just beginning. Once I saw video with proprietary app for navigation of blind people (or with eye defect) in the cities. It was amazing how good this navigation was describing environment around... There is no such open-source app AFAIK.

How to get training data? We may start with random junctions and current voice instructions that we generate. Then we may improve learning data manually (correct instructions)...

[Karry]

I will just store bookmark here... Paper solving similar problem (instructions for pedestrians) with graph neural network: https://typeset.io/papers/generating-landmark-navigation-instructions-from-maps-as-a-1bm3wvbrcd