Interesting results using gds.shortestpath.astar

Neo4j Graph Platform Graph Algorithms/Graph Data Science
1

Hello Community!

Can anyone help me explain this? I'm working on a navigation project and returning routes using both Dijkstra and A*. Both calculations use practically identical queries - except for the addition of the latitude and longitude parameters for A*. Something strange seems to be happening with the A* calculation though, because the path being returned is definitely not the shortest :slight_smile:
The data has been taken from OpenStreetMap and added/appended for routing.
This is the Dijkstra result:
image

This is the A* result with the same start source and target:
image

And here's the call being used :

MATCH(x:PointOfInterest)-[:TAGS]-(t:OSMTags) 
WHERE t.name contains('<Name-of-destination>') 
MATCH (p:ParkingSpaceNode) 
WITH x,id(p) as pId, distance(x.location,p.location) as d 
ORDER BY d ASC LIMIT 1 
CALL gds.shortestPath.astar.stream({     
    sourceNode:pId,     
    targetNode:id(x),     
    nodeProjection: '*',     
    nodeProperties:['lat','lon'],     
    relationshipProjection:{         
        all:{                 
            type:'ROUTE',                 
            properties:'distance',                 
            orientation:'UNDIRECTED'         
        }     
    },     
    longitudeProperty: 'lon', 
    latitudeProperty: 'lat',     
    relationshipWeightProperty:'distance' 
}) YIELD  nodeIds, totalCosts //include totalCosts for analysis
WITH [nodeId IN nodeIds | gds.util.asNode(nodeId).location] as coords
RETURN coords

A short explanation:

  1. I select a destination and derived the closest non-occupied parking space based on the "line-of-site" distance. (WITH... distance() ... LIMIT 1). This works fine.
  2. Calculate the path using A* or Dijkstra.
  3. The returned coordinates are then packaged in a GeoJSON and sent to a MapBox display.

The path calculation is undirected, and all relations (pathways) are "two-way"...
The example shown in the pictures calculate a 70m path with Dijkstra and 413m for A* :rofl:
Is anyone working with A* at the moment that could help explain what might be happening in the middle to divert the path so far out of the way?

Any ideas would be greatly appreciated!

Mike

2

before going any deeper, are you using directional relationships to represent directional streets? (and two rels if two way street?) at a glance it looks like Dijkstra is proposing going the wrong way up a one way street? but a* does seem to be taking the scenic tour (could it be cost or directional traffic?)

3

Hi Joel,
that's what I originally suspected, but I checked the relationships and everything seems to be undirected. Here's an example of a relationship for the area in question:

{
  "identity": 8881,
  "start": 699,
  "end": 696,
  "type": "ROUTE",
  "properties": {
"toRel": 3266,
"distance": 23.609465317591265,
"fromRel": 3268
  }
}

You're right, technically they are one way streets ;) And there is, in most cases, only one relation But the relationships are not marked as such. Do you think that could make a difference? I assumed specifying "UNDIRECTED" in the call would have taken care of that.

So I just tried duplicating all the ROUTE relationships and changing the direction.. Still the same result :frowning:

4

I'm embarrassed to say, but I found the problem...
At some point when I was adding nodes to the graph, I somehow managed to swap the latitude and longitude values of certain nodes. :blush:
Because Dijkstra relies purely on the cost of the path and A* requires the haversine distance for the heuristic, it decided that a point somewhere in the middle of Yemen instead of Austria wasn't a suitable route..
Can't understand that myself... :rofl:

Anyway, problem solved. A tip for anyone with strange A* routes.. Check your coordinates!!!

Mike