Alternative for GetClosestRoutableNode?

[uschmelmer]

Hi, I am working on an autonomous car project and have choosen osmscout for the high level navigation. But i am wondering if any one gets good (real world usable) results with the GetClosestRoutableNode and calculateRoute functions? See the attached screenshot, red is the gps position of my car. The router would now suggest to drive left first, because the function "snapped" to this node, because its nearer to my position. This there an alternative function in osmscout? I would also be very pleased if someone could give me a good practise workaround?

Best Regards, Udo Schmelmer

[Framstag]

Hello :-) Autonomous car project sounds very interesting. Does this have a commercial background?

Regarding your question:

The implementation

  RoutePosition SimpleRoutingService::GetClosestRoutableNode(const GeoCoord& coord,
                                                             const RoutingProfile& profile,
                                                             double radius) const

Returns the closest routing nodes of all nearby ways.

If you look at

  RoutingResult AbstractRoutingService<RoutingState>::CalculateRoute(RoutingState& state,
                                                                     const RoutePosition& start,
                                                                     const RoutePosition& target,
                                                                     const RoutingParameter& parameter)

especially at

    if (!GetStartNodes(state,
                       start,
                       startCoord,
                       targetCoord,
                       startForwardRouteNode,
                       startBackwardRouteNode,
                       startForwardNode,
                       startBackwardNode)) {
      return result;
    }

though you will see, that the routing algorithm itself does not require the start to be a rout node. It is only required that on the way there is at least one route node. In fact GetStartNodes() will try to find one route node in each direction. And if found, both route nodes will be added as possible starts into the routing algorithm.

What is missing is:

• Potentially pass a "current direction" into the routing algorithm to add additional costs for driving into the opposite direction.
• Allow via API parameter to disable on the route nodes, to enforce a certain direction.

Regarding the concrete problem: It should be no problem to change the implementation (and possibly the name :-)) of GetClosestRoutableNode() to not return the closest route node but only the closest possible routable node (which means,t he way must have a route node but the closest node itself does not need to be a route node itself). So in this case you should get a node that is even closer to the car position.

Would this improve the situation for you? Are you able to change the implementation and test it?

[Framstag]

Sorry, wrong analysis:

    for (const auto& way : ways) {
      if (!profile.CanUse(*way)) {
        continue;
      }

      if (!HasNodeWithId(way->nodes)) {
        continue;
      }

      for (size_t i=0;  i<way->nodes.size(); i++) {
        double distance=sqrt((way->nodes[i].GetLat()-coord.GetLat())*(way->nodes[i].GetLat()-coord.GetLat())+
                             (way->nodes[i].GetLon()-coord.GetLon())*(way->nodes[i].GetLon()-coord.GetLon()));
        if (distance<minDistance) {
          minDistance=distance;

          position=RoutePosition(way->GetObjectFileRef(),i,/*database*/0);
        }
      }
    }

GetClosestRoutableNode() already returns the closest note on a routable way.

So, one step back. Do you have actual data, e.g. the coordinate for the visual presentation above? As said, the router itself should inject two nodes as starting point. the one "below" the car and the one "above" the car. Checking this in actual data would make it simpler to see what happens. So please give us an geo coordinate for the car position and the target point you passed for the routing calculation.

[uschmelmer]

Hey, the project is still in backyard/garage stage, but who knows, many good things started in garages :-) Thanks for having a look at my problem! So, regarding to your question: Start position: Lat = 48.76152; Lon = 13.02806719; Target: Lat = 48.76210126; Lon = 13.02865294; I attached another screen shot: Green is now start, Red is destination, Blue is the way returned from the routing algorithm.

The problem also exists at the end of the route of course. If you need further information, just tell me :-)

Best Regards, Udo Schmelmer

[Framstag]

This is the input to the routing process (way id, node id, current, estimated and overall cost):

StartForwardNode:   Way 47805962 3758899070936162817 0.000955523 0.00110747 0.00206299
StartBackwardNode:  Way 47805962 3758899088110550785 0.0025786 0.00110747 0.00368607
TargetForwardNode:  Way 47808526 3758899088110550785
TargetBackwardNode: Way 47808526 3758899079580390145

Way 47805962 is equal to: https://www.openstreetmap.org/way/28044762 This way has three route nodes one for each crossing/exit. For the routing the crossing the crossing in the middle and the the north are used.

Target 28044764 is equal to https://www.openstreetmap.org/way/28044764 In this case the same crossing and the first crossing to the right are evaluated.

So formally the route from crossing to crossing should be the best, but it is not.

As you can see, the estimate costs for both start node sis the same, this is wrong. I'll will push a fix. Afterwards it still uses the more far away target node. I assume that the routing service terminates until one of the two target nodes is reached. But this does not necessarily result in the fastest/shortest route. I assume the routing must terminate only after both target nodes are reached (and the the shortest must be chosen). This is a research for the next day. Push for fixing the start node problem will come later in the evening

[Karry]

Hi. I dont think that this is something that should be solved in current low level routing service. But we are missing some service for navigation, that will consume computed route and will provide real-time instructions for current car position and while car is moving...

[Framstag]

@Karry: The router is not returning the optimal route, so there is definitely a need for a fix :-). But of course there are possible improvements outside of the actual route calculation, as you mentioned. It would be interesting to know, what API real-time instructions would require? Is the current routing description algorithm missing information or does it just have the wrong API (or both)?

Also the arguments to the routing calculation might not be optimal. Instead of passing a node it possibly should pass an intersection point to the way. Also the caller is interested in having influence on initial direction of the car and turns required. IMHO Vladimir stated this long before.

[uschmelmer]

I also think that searching for the nearest way and than using the position at which the coordinate position is perpendicular to that way would be the best solution. The start/target positions should be within the road then. One more screen shot which shows how serious the problem is: The target way is defined by just two nodes which are very far apart. One on the left crossing, and one on the right crossing near to the river. But he gets snapped to a whole different way (yes, we have suspicious cities here in Bavaria ;-)) Target point is 48.76279004/13.02910579

Having influence to initial direction (eg. by compass heading) would be very nice but is not a must have :-)

BR, Udo

[Framstag]

That "snapping" effect is not clear to me. GetClosestRoutabeNode() returns one node. It does so, by finding a node on a routable ways which is closest to the given coordinate. This may or may not be correct but is the best we can do with no further information.

For the found ways (start and end) it tries to find the adjacent routing nodes. Currently adjacent to the given node (which has some granularity and thus may not represent the exact costs), if we would change the API, closest to the given position on the way. In both cases he same routing nodes will be found, it is just that the distance and thus the costs will be slightly different.

This would be done for start and target.

It should never be the case, that these up to two adjacent routing nodes are placed on different ways - though turns and crossing are of course possible.

So, where does the node marked with the red circle come from?

[uschmelmer]

Hi, the red circle is not a node. It's just the the target coordinates. Sorry if this wasn't clear enough.

So i want the autonomous car to drive on the roads (staying on the roads is implemented with lidar and cameras trough deep learning) and to reach the given coordinate. There it looks for something like a parking lot or a cargo station, also supported by deep learning. The given coordinates for start and target are not always directly on the roads, because of heavy gps distortion in urban regions. Thats why i place the locations always a bit off the streets for testing :-)

[Framstag]

I see. There is something like "low node density" on the "Lichtenwörther Straße", so actually it chooses a closer node on the "Gundelauer Straße". I have made a separate issue for this. See #442.

Just because I assume you might find other corner cases, too. How big is your interest in fixing some bugs yourself :-)?

[uschmelmer]

Hi, actually i would be interested in contributing :-) But as i am a bit unfamiliar with the internals of osmscout, i need some time to get used to it. And there is of course much other stuff to do ;-) But i'll try my best and dig into the code now. BR, Udo

[Karry]

Hi. Information provided by current route description postprocessing is fine from my point of view, but what is missing is some navigation service. I will create new issue and try to describe what I expect from it...

[Framstag]

I pushed another changed, that tried to calculate routes to both target routes and return the "better" route. The raw route returned consists now of only one node. Please check if the router now returns optimal routes in our case for the given start and end. In this case, please close it?

Issue #442 will stand for the changes required to return better start and target points.

[vyskocil]

I tried the latest code in Prague where I'm now and found a route calculation that don't work, maybe it's a corner case, it seems to loop (almost) infinitely at the very end of the calculation. I activated DEBUG_ROUTING and got a very very big log output...

./Routing --router routecar ~/Documents/OSM/Czech\ Republic.osmscout 50.06645 14.39931 50.08558 14.42164 No speed for type 'highway_residential_area' defined! No speed for type 'highway_service_area' defined! 97% 97% 97% 97% 97% From: 50.06636 N 14.39924 E Way 46525520[1 > 3763128732401035265] To: 50.08518 N 14.42149 E Way 47232749[3763130064375107329 > 2] Time: 2.492 Air-line distance: 2.6km Minimum cost: 0.0 Actual cost: 4.1 Cost limit: 13.2 Route nodes loaded: 721598 Route nodes ignored: 757271 Max. OpenList size: 842 Max. ClosedSet size: 720912 No route found! There was an error while calculating the route!

The destination is "Havelská Koruna", but if I choose a point on "Rytirská" road in front of "Havelská Koruna" the calculation is almost instantaneous :

[Framstag]

Looks like the router does not find a route. This is difficult to debug for such a long route. I would suggest to use Lukas new RouteAnimation tool or trying to reduce the route to a minimum (that still fails). It initially looked like there is no route to the target but a more detailed look showed that it should be possible.

The start is : https://www.openstreetmap.org/way/11015778#map=18/50.06622/14.39956 Target is: https://www.openstreetmap.org/way/127051758#map=18/50.08545/14.42162

It should be possible to reach target from the south.

[Karry]

Hi Vladimir and Tim. This route (Havelská) is unavailable by car for libosmscout, because both possible directions to Melantrichova (Rytířská; Michalská) has setup "motor_vehicle=destination", but Melantrichova has not this constraint - so you can't leave these ways to this direction... Funny is that both main OSM routing backends, Mapzen and GrapHopper allow this, it is possible that these backends detects this unsolvable situation and ignore rules...

[Framstag]

Interesting :-) So should be close the issue?

[Framstag]

I'm closing it.