Exploring Pathfinding Algorithms Using a Real Map of Amsterdam

A* (A Star) pathfinding algorithm visualized on the city streets of Amsterdam, comparing the shortest and fastest path.
As I continue my exploration of the A* Pathfinding algorithm, I wanted to share the difference between finding the shortest path and the fastest path, which are often not the same. By using the max allowed speed of a certain street we can calculate the minimal duration it would take to use that street.
You can find all the other explorations on this topic here • Pathfinding on Real Ma...
Using the A* Star path finding algorithm to find the fastest path instead of the shortest path. By taking in to account the max allowed speed of certain street and their length, we can calculate the minimal duration of using this particular edge. To calculate the heuristic for a node, the current speed (total distance / total duration) is applied to the heuristic distance (regardless of how we measure the distance). This will make sure that not only the edge with the lowest duration will be chosen next but also the path with the lowest duration to get to that point will be favoured.
I also take into account the allowed driving direction, this is why it might look like the animation is lagging sometimes. What actually happens during these moments is that it found another street connecting an already visited intersection but at a lower cost (or in this case, through a faster path) because of that it adds all the connecting streets again to the open list and recalculates all their edges with the new lower cost and less duration.
Thanks to Martin Raifer and his Overpass Turbo tool which I used for the initial data where intersections of streets represented as nodes and streets as edges

[@eliasforamitti]

A beautiful visualization!!!
But if I understand your heuristic for the fastest path correctly, than it is not admissible, I think (i.e. A* will not necessarily find the fastest path if it terminates at the first valid path)
Imagine a triangle with straight edges as a minimal example, where the direct connection from source (S) to target (T) is of course the shortest but has a medium speed limit, while the path S->A->T is of course longer, and S->A has an even lower speed limit than S->T, but A->T makes up for it, such that S->A->T is overall the fastest route.
S --- T
\ /
A
Distance(S,T) = 60
Distance(S,A) = 12
Distance(A,T) = 60
SpeedLimit(S,T) = 10
SpeedLimit(S,A) = 6
SpeedLimit(A,T) = 60
So A* will first generate A and T, with your definition of cost (c) and heuristic (h) the evaluation function (f) for those paths yields:
f(S->T) = c(S->T) + h(T) = (60/10) + 0 = 6
f(S->A) = c(S->A) + h(A) = (12/6) + (60/2) = 32
(where the current speed of 6 from S to A is assumed to continue for the remaining A->T)
Since f(S->T)A), A* will expand S->T next and then terminate, since T is the target. Even though c(S->A->T) = (12/6) + (60/60) = 3 is actually the cheapest path.
To ensure admissibility you would need to find some guaranteed upper bound for the speed and use that in the heuristic (e.g. use the overall max speed limit in the whole graph, or maybe you could find a more clever approach to find bounds in certain subgraphs), but using the previous speed is not admissible, since later speeds might be dramatically different.

[@nicogsplayground]

Hi Elias! First of all I would like to thank you for taking the time to comment and with such detail. Really appreciate it!
I still have no idea if my solution to this problem is correct or not, exploring the applications of A* star and how to implement it in different scenario’s as we speak, and contributions like your reply are very handy!
This scenario, with the goal node being directly connected to the source node, woud indeed not work, but I noticed I might have explained my heuristic calculation badly.
To calculate the heuristic it used the current duration and the current distance to calculate the speed at which we travelled followed the current total path(from start til where we are now), and this speed was used to calculate the duration heuristic.
If the next node is indeed the goal node, there could be a faster path, I think that any other scenario would work tho, as it will reevaluate the visited nodes when a faster path is available.
Do you think this way of calculating the heuristic is a good idea? (except from this scenario?)
Thanks in advance!
Cheers
Nicogs

[@eliasforamitti]

@@nicogsplayground Hi Nicogs,
ok yes, thanks for the more explicit explanation, but that matches how understood your original explanation from the video description already. (it's basically just the remaining euclidean distance divided by the average speed of the path so far)
This heuristic is not admissible, i.e. it will not always find the fastest path (it might still be useful in practice, since it might produce a good enough result on average on most real street data and might find its result quicker, but it comes at the cost of guaranteed optimality)
And my example is not the only case. There are infinitely many kinds of graphs, on which this heuristic fails. The problem arises, whenever the fastest path (however shaped and long it is) starts with a disproportionally slow section and only the remaining section of the path (which, however, is only reachable over this slow first section or even slower alternatives) makes up for it by allowing very high speeds. This way a path that is overall very fast can "hide" behind a slower first section.
You can for example arbitrarily extend my example from the last comment with intermediate nodes, and the problem will still remain:
S -- C -- T
\ /
A --- B
Distance(S,C) = 60
Distance(C,T) = 60
Distance(S,A) = 12
Distance(A,B) = 60
Distance(B,T) = 60
SpeedLimit(S,C) = 10
SpeedLimit(C,T) = 10
SpeedLimit(S,A) = 6
SpeedLimit(A,B) = 60
SpeedLimit(B,T) = 60
Euclidean(C,T) = 60
Euclidean(A,T) = 120
Euclidean(B,T) = 60
c(S->C) = (60/10) = 6
c(S->C->T) = (60/10) + (60/10) = 12
c(S->A) = (12/6) = 2
c(S->A->B) = (12/6) + (60/60) = 3
c(S->A->B->T) = (12/6) + (60/60) + (60/60) = 4
AverageSpeed(S->C) = 60/6 = 10
AverageSpeed(S->C->T) = 120/12 = 10
AverageSpeed(S->A) = 12/6 = 2
AverageSpeed(S->A->B) = 72/3 = 24
AverageSpeed(S->A->B->T) = 132/4 = 33
h(S->C) = Euclidean(C,T)/AverageSpeed(S->C) = 60/10 = 6
h(S->C->T) = 0
h(S->A) = 120/2 = 60
h(S->A->B) = 60/24 = 2.5
h(S->A->B->T) = 0
f(S->C) = c(S->C) + h(S->C) = 6+6 = 12
f(S->C->T) = 12
f(S->A) = 2+60 = 62
f(S->A->B) = 3+2.5 = 5.5
f(S->A->B->T) = 4
So expand S then S->C then S->C->T, since all of them have lower evaluation functions than S->A. But overall S->A->B->T would clearly be faster.
=====================
In general:
For common A* search to find the optimal path (in all cases) you need 2 things:
- your heuristic has to be equal to 0 in all goal nodes (this is trivial in your case; once you're at the target the euclidean distance to the target is of course 0)
- your heuristic has to be admissible, i.e. it may never overestimate the actual cost of moving from the current node to the goal node (on the cheapest path), or in other words the evaluation function (fixed cost + heuristic) may never be higher than the true cost of the cheapest goal path still achievable
You can see how the heuristic violates admissibility on the path S->A->B->T above, since f(S->A) is larger than c(S->A->B->T) (which is a goal path and reachable from S->A), i.e. the heuristic overestimates the true cost (since we used too low of an estimate for the upcoming speed limits)
The euclidean distance is fine, since no street will ever be shorter than the direct distance, but the upcoming speed limit might very well be higher than the average speed limit so far. The upcoming speed limits might even be better than any speed limit encountered thus far. So the only safe way is to use some global knowledge, like there is no street with a speed limit above 130 in Amsterdam, and using that is a fixed upper bound.
However, there is an inherent trade-off to this: The main reason why A* is usually faster than uniform-cost-search (i.e. Dijkstra's algorithm), is that the heuristic eliminates irrelevant branches by raising their evaluation function above the cost of the optimal path. In an optimal world, you could raise all those branches to their true cost, but in practice it is difficult to achieve this. So instead, we need to come as close to the true cost as possible (but without going over; otherwise we violate admissibility). A fixed speed bound is a relatively bad estimation (on average large underestimation of the remaining duration), so the runtime will be way worse than with your heuristic. That is why it might make sense sometimes to ignore admissibility (and with that guaranteed optimality), and allow some cases to overestimate for an overall better estimation of the cost. Depends on what you want to achieve.
If you want a more formal introduction to search algorithms, I would recommend the capitals on search algorithms in:
Artificial Intelligence: A modern approach (Peter Norvig, Stuart Russell)
or
Fundamentals of Artificial Intelligence (K. R. Chowdhary)
(if you need copies, feel free to email me mitti.leon[at]gmail.com)
or for a very formal introduction, here is a pre-print for something I wrote recently:
elias[dot]foramitti[dot]com/public_share/frontier-search.pdf
(sry, for the weird formatting; youtube often shadow-bans comments with links in them)
Cheers Elias

[@eliasforamitti]

My main email seems to have some issue right now. I updated the above comment to my secondary email. Please use that one instead, if you want to reach out

[@shailmurtaza9082]

@@nicogsplayground which tool you used to make this visualization?

[@nicogsplayground]

@@eliasforamitti sorry for the late reply! my next 2 video’s are going to show the mistake I made, thanks for correcting me!
Back in 2019 followed the Computer Science for Artificial Intelligence course by HarvardX, and eventually got my certification for it, but that was very basic. It’s from there I learned about A*, D Lite etc for the first time!
& I will mail you!
Thanks in advance for everything!!!
❤️

[@krns1695]

the firsr long street higlighted at 0:04 i used to take that almost everyday... i miss this city

[@nicogsplayground]

Kinkerstraat or the Overtoom? What’s holding you back from returning? 🙆‍♂️

[@behnamrahdari]

Nice visualization. 👌Would be nice to see shortest path and the fastest path compete side by side.

[@nicogsplayground]

Hi Behnam, thank you so much! I'm on it! Anything in particular that stood out for you?

[@behnamrahdari]

@@nicogsplayground Awesome. I really like the color scheme and the background audio.

[@ManiKanta-fp5qg]

can I get source code