Join the community at Nodes 2022, our free virtual event on November 16 - 17.
β06-04-2021 12:02 AM
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
The data has been taken from OpenStreetMap and added/appended for routing.
This is the Dijkstra result:
This is the A* result with the same start source and target:
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:
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*
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
Solved! Go to Solution.
β06-04-2021 03:05 PM
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.
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...
Anyway, problem solved. A tip for anyone with strange A* routes.. Check your coordinates!!!
Mike
β06-04-2021 11:00 AM
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?)
β06-04-2021 02:10 PM
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
β06-04-2021 03:05 PM
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.
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...
Anyway, problem solved. A tip for anyone with strange A* routes.. Check your coordinates!!!
Mike