Dijkstra's Algorithm vs. A* Search vs. Concurrent Dijkstra's Algorithm
Vložit
- čas přidán 23. 06. 2013
- A comparison of two traditional grid based path planning algorithms against a novel concurrent version of Dijkstra's algorithm. This video is aimed at comparing the algorithms from a theoretical point of view. An implementation of the concurrent algorithm in OpenGL+GLSL has recently surpassed the sequential CPU based algorithms due to advances in the number of shader processors in modern GPUs and the improving up and down data bus transfer rates between CPU and GPU based memory.
S. Cossell and J. Guivant, "Parallel evaluation of a spatial traversability cost function on GPU for efficient path planning," Journal of Intelligent Learning Systems and Applications, Vol. 3, No. 4, pp. 191-200, November 2011. (DOI: 10.4236/jilsa.2011.34022) - Věda a technologie
I'm not convinced at all. You are checking multiple cells each step with concurrent which will cost more time. If you can do multiple cells with concurrent, than you can check multiple cells with the other two as well, in which case A* should still come out on top. From everyone I talk to online, A* is the best choice, it's what is used in most top games out there.
+Neil Roy Completely agree. As you already mentioned, a step of concurrent Dijkstra cost more than a step of A*. And to make matters worse, the fact that it is concurrent doesn't really help you in practice. You're likely to be calculating paths for more than one object, in which case you could run multiple A* concurrently.
+Neil Roy Actually there is a new, much faster algorithm, called JPS (Jump Point Search). You should look it up, its a order of magnitude faster than A* and still gets the shortest possible way.
+Neil Roy It would be a decent comparacion if he checked all the nodes on the a* openset at once.
***** Well, I'm not sure I would call it a new algorithm. Looks more like an optimization to A*. That being said, it looks pretty bad-ass and I'll certainly use it over traditional A* next time I have a need for pathfinding.
+Neil Roy Concurrent creates a path for every point in the grid, which is better for precalculating paths, or periodically calculating paths for multiple seekers at once.
WTF you can't use concurrency but count it as one step.
Step is misleading, yes. But I think the idea is that in a given unit of time concurrent Djkstra check more cells than A* or Djkstra.
I call hax on Concurrent Dijkstra
It's much more cpu intensive than A*
yes. it is the stupidest one yet since he pretends filling 50 squares is the same as one it wins 100% of the time
These are theoretical points of view, but such a system can run on a machine that can compare multiple values at once, such as a GPU.
A* has been done on the GPU.
www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9620
By several orders of magnitude, take the very first example, he claims it found the goal in 4 steps, yet it actually had to perform 129 checks, so it used 32 times as many operations, or 3125% slower.
And it just gets worse with bigger maps. Not strange since it is nothing more than normal Dijkstra's algorithm, simply throwing more and more threads at the problem won't make up for the fact that its 2 orders of magnitude slower in 4 steps.
It's a bit cheating tough. The concurrent Dijkstra will always need exacly as many steps as the optimal solution. The length of the "wavefront", will require many parallel executions (worst case 8n after n steps). If you assume a limitation of 32 cores, the limit will be reached in 4 steps. In an optimal case A* will now outperform parallel Dijkstra.
What would be interesting would be parallel A*!
In theory, the concurrent algorithm will perform at least as well as A*. If the environment is unfavorable to the heuristic chosen for A* then the concurrent method performs better (like in the devious case in the video).
In practice, ~32 cores was an issue when I was using a 2007 model Radeon with 40 shader processors. It was less of an issue when I upgraded to a 2010 model GeForce with 448 cores. I can also go buy an NVidia Telsa today with 1000s of cores and it's good enough for practical use.
The difference between Dijkstra and A* is choosing which cell to evaluate next at a particular iteration. Since the concurrent method just evaluates all "next" cells at the same time it's sort of a super set of both Dijkstra's and A*'s decisions.
The closest thing I've seen to parallel A* (that's less flood gate and more selective) uses a Pseudo-Prority Queue to arrange "next" cells into buckets and evaluates a bucket of cells concurrently. I hope that helps.
+Pelle Reimers "What would be interesting would be parallel A*!"
www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9620
Are you using a quantum computer for the concurrent dijkstra algorithm?
close, a GPU
jajajja
i always see people always mistaken the usage of dijkstra. dijkstra shouldn't be use for real-time path finding as we can all see from the video.
dijkstra is best use in situation when a level is initializing or better yet, store in a file for loading during initialization. djikstra works well as peregrinated paths for all possible and best paths for all nodes in a GRAPH environment where node positions are fixed.
for example, you have a big map (like gta) and you need to move a npc from A to B you would pull the best path corresponding path pregenerated from dijkstra from initialization and be done almost instantly without having to try to find the best path during runtime which can be very costly. if you tried A* in such a big map, it can be very costly especially when you have 50+ npc running around.
note you can also use A* or any other algorithm to pregenerate paths, but from my experiment with dijkstra you can at least cache all paths for one node to all in one run instead of running it multiple times from the start to end with A*.
of course, there probably are better implementations and approaches than what i have been doing but it works well for what im doing and that's how ive been approaching these pathfinding algorithms. but videos like this are great for visualization and shows you how they work. kudos.
+Johnny Hang Also The concurrent would seem like a lot of lag in open world games...
u are comparing in step, not in real time, technically i can say each step Dijkstra's Algorithm spend 10 cpu cycles, and Concurrent Dijkstra's Algorithm spend 10000 cpu cycles, thus Concurrent Dijkstra's Algorithm is the worst.
The entire point is that the algorithm takes advantage of the parallel processing nature of the GPU. In real-world applications most performance metrics are heavily based on response (processing) time. Thus the fact that it takes more CPU/GPU cycles is moot as the real time performance is vastly improved. In addition most GPUs are more power efficient for this type of calculation than an equivalent amount of parallel CPU cores, thus the power-to-performance ratio is still better overall - an important consideration if this is being used on a mobile robot running on batteries.
+Jason Slater That only holds up if you're calculating very few paths. Otherwise you can just run a bunch of A* concurrently.
spikebarnett In my experience with real world SLAM in military robots rarely do you need or have more than a few paths. For edge cases where the search space is more broad and multiple valid paths may exist I found good performance using RRTs: Rapidly-exploring Random Trees. They don't guarantee optimal route but have good performance time and usually get the job done.
+Jason Slater True you wouldn't have much need for a multitude of paths in robotics, but that's not what I'm getting at. I'm thinking more like in a video game where you might need to calculate paths for many different enemies. I think in that case, running multiple A* in different threads at the same time would out perform a concurrent Dijkstra for each enemy. That's not to say it's not useful. Different algorithms have different use cases that they excel in. For example, it's not uncommon to see a quick sort used as a broad phase sort and then something like a heap sort used to finish the sorting.
+spikebarnett you don't need to run it concurrently for each enemy because it calculates a path for all nodes. you only need to run it once for all enemies.
Pathfinding is typically a CPU task where you only have a few threads. A* is better for that.
I think, the memory is going to heaven!
In fact, in addition to what has already been said, A* isn't even well implemented here since it should try lowest G scores first (here it doesn't, ex. at 1:31) .. u_u'
I made the same observation.
nice catch!
Great Work! I want to compare two different search algorithms on the same obstacle map. Is there anyway to encapsulate the information of the entire obstacle map in a single number? So I can understand the nature of complexity vs number of expansions. Thanks in advance.
-SP
How do you mark the neighbor cells values in concurrent? By iteration? Then it takes longer time in each step from my knowledge.
Interesting video. How is the concurrency achieved? What kind of weights did you have for your A* (if any?). Are you able to post your real/pseudo code? I'm interested in the concurrent aspect of this demonstration as A* can be paralleled as well.
I like the video, but it is not good comparison...
I don't fully understand the difference between Dijkstra's usal and Concurrent version...
I mean... Isn't the only difference the number of visualized debug breaks?
Except the concurrent version realy uses threading, but wouldn't that be very unefficent in case of performance when a map is huge with less walls?
can i use Concurrent Dijkstra in badminton to detect the racket to hit?
Its simple Big O notation.. sure there's fewer "steps" of the outer loop, but you still have to consider every single tile on the map fanning out within that loop, which will consume an unnecessary amount of time, especially in the more trivial cases.
why dont you use admissible heuristic for A*
What's the difference between concurrent dijkstra's algorithm and wavefront expansion?
Why would you ever use Dijstra's Aglorithm in a gridbased environment?
was about to ask the same damn thing
When you're creating an SRPG that requires all traversible tiles, or when you need to find the nearest target element.
Manas A* is still better
It depends, If you want to calculate the path from various points to the same goal then Dijkstra is going to be faster than A*. Dijkstra can also be used to pre-process a grid and make A* much faster
I have never heard of the Dijsktra or Concurrent path-finding algorithms before, but I know from looking at this that A* definitely and easily can return the shortest path to take. In this video, all that was returned was the number of times a block of code was run; however, can concurrent and/or dijsktra provide the exact path to take or just the length of the hypothetical shortest path? Because I feel when these algorithms are meaningfully used that finind the PATH is more important than quantifying the path's LENGTH.
The explored space can be stored in a graph/binary tree structure and then standard graph traversal algorithms can quickly compute the shortest path in something like O(log N) time. For small data sets A* will probably outperform but as the configuration space grows it is likely that the concurrent algorithm would have the advantage. Even in a few of the examples given here the concurrent algo space is complete for many cycles before A* finds a path, giving ample time to traverse the graph before A* completes.
Jason Slater This seems vastly based on assumptions. The current video is not very serious either.
Dijkstra only cares if a node is visited and all unvisited nodes are equal weight, it literally has no idea what is closer. It only knows that it has the shortest path to the next node. A* is basically a weighted flood-fill, so it has intelligence. But Djiksra's weight doesn't exist until the goal node is found, bc it's assumed to be max_val.
I like de Fast Marching Method and the Fast Interative Method, I would like to see a video with the algorithms and perhaps the Fast Sweeping Method. These methods no have the "zig zag" graph problem, they are based on the eikonal equation
May you tell me what you use to visualize the algotihms? I need an interface like that (just too lazy to make one)
i made one in allegro when i coded in c++ but you can make it in anything just use the arrays coordinates and put images on it.
this erroneous comparison vid has sparked a gold mine of path finding knowledge in the comments section, loving it.
how A* know where to go where all paths all equal cost?
So means everything is crap, learn A* basicly?
Am i missing a message here? please let me know.
Is the time for each step the same? I assume Dijkstra is faster than A* which is faster than Concurrent Dijkstra
Absolutely not, the so called concurrent version is an order of a magnitude worse after just a couple of iterations, it is no faster than the normal Dijkstra's algorithm, it just hides the horrible execution time behind abstractions.
Define step as checking all paths accessible from start point. This algorithm will only take O(1) steps.
Somewhat interesting but missing a step. After declaring all the empty space from point a to b. It needs to calculate the shortest path. Which is not shown in this video.
If we 're talking concurrency then I'd try a concurrent A* algorithm that would simultaneously go from start to end and from end to start. This would cut the time in half. Even use concurrency in same F cost cases.
this video hurts my brain, each cell in the concurrency still needs checking, just because you can animate it as 1 step doesn't mean thats what would happen on a processor, unless you somehow has an infinite number of processors
This feels like someone's going to rip it off into a mobile game and the ad will be noob vs pro vs hacker
Also.. how does checking 20 squares at once for the right side count as only one step?
Concurrent Dijkstra acts like BFS. How are they different?
+Derek Lun BFS goes level by level. BFS has no understanding of path costs. Dijkstra, on the other hand, goes from node to node. It updates the nodes with the current shortest path it has found.
In a grid, each level in the tree has a path cost of exactly one greater than the level above it. BFS gets path costs for free in this case. Eg, the squares adjacent to the origin are at level 1, with a path cost of one. The Squares adjacent to those are at level 2, with a path cost of two. So in this case, because level is equal to path cost, Dijkstra and BFS behave the same.
If he plotted BFS, it would look the same as his Dijkstra animation on the left of the first example. Concurrent BFS (where you treat all the branches of the current level as one step, for some reason) would look the same as the concurrent Dijkstra. His analysis is way out of whack though, because he gives concurrent Dijkstra a tonne of free evaluations.
It would be better to append the reference papers for each algorithms. :)
How a Concurrent algorithm works?
Can you share the source code plz?
This algorythm can only be run on a quantum computer. This is completely useless in programming terms. You're checking more than one cell at once.
+Olivebates It's concurrency. That is, multi-core. Each core checks one cell.
Each one with its own RAM for large maps, I think.
On a single core processor the D* lite algorithm is faster than A*. Dijkstra is simply to slow. Parallel computing can bring a speed advantage, but it doesn't have to.
0:43 Dijkstra pls get your shit together...
haha right
At least he fixed that nonsense later on :^)
yea :P
the thingis dijkstra is "blind" while A* sees if it got closer
and concurent dijkstra is just stupid floodfill
How does A* automatically know where the end-point is?
+Faroskalin Look it up
It takes distance to end point into account, when calculating
+Faroskalin It's as Zaim Zain is saying. Pathfinding is not an algorithm for finding an unknown destination, but rather for finding the shortest path to get to a known destination.A* is just a more enhanced Dijkstra algorithm which will first try paths which are currently the shortest, often used in games.
+Justin Smith "a special case of A* which is more general"
that's self conflicting
+Faroskalin it's pathfinding, of course it knows the end point.
Zer0kx No, no the way he said that is wrong but what he meant is actually correct
Best!!!=)
i think Concurrent Dijkstra have a wave behavior except reflection.
This assumes an infinite amount of kernals. you can't just execute n steps in one go no matter how big n is..
There are only some amount of kernals - lets say k kernals - in which case you will have created a dijkstra which is k times as fast. and in O notation it boils down to the same efficieny.. Weird video
Should've called it parallel, not concurrent.
2 steps for Concurrent Dijkstra's Algorithm is equal to 24 steps for A*
Yet the so called concurrent version is slower by an order of a magnitude, and on a larger map it would continue getting slower and slower, it is no faster than the normal Dijkstra's algorithm, it just hides the horrible execution time behind abstractions.
The concurrent version is meant to be run in a gpu where you have hundres of cores so it can evaluate all expanding nodes at once. It is by no means an order of magnitude slower
Could you send me the Source Code?
Look up any of these on wikipedia, they have Pseudo code on the website.
well if you are checking more than one cell at a time,(multi threaded) and concurently check each cell on the bounding shape...ofc it is faster...but also uses more resources...A* is still king...this does not mean we should not consider other methods...only that this video is sort of misleading....it is visually faster, but computationally...it is probably slower if this is all done on one thread....I'm curious how that would look?
How did I end up on the algorithmic side of youtube... I was watching vanoss
Concurrent litrslly checks the whole area soooooo thats take WAAAY longer
Dijkstra: Hmm… Let's just cover all space needed.
Concurrent Dijkstra: Let's flood every space!
A*: I'll be smart and see how close I am to the end.
What I'm saying is Dijkstra methods are stupid and A* is smart.
A* is poorly coded or simply wrong.
Concurrent takes more CPU though.
Massively more, at the step at 1:26 its 26 times slower than normal Dijkstra's and that's only at the so called 4th iteration. It is no faster than the normal Dijkstra's algorithm, it just hides the horrible execution time behind abstractions.
I currently on 'Flood Fill' pathfinding, which is like Concurrent , but a bit different, its just easier to understand and implement than the others.
after watching this i want some fried egg
What a load of nonsense. A fourteen year old could see that this is an absurd comparison.
this Concurrent Dijkstra is a plain shenanigan, and that Dijkstra is not Dijkstra at all!!! I clearly can see it doesn't have heuristic!! It should use Manhattan Distance Heuristic or any other
As far as I know Dijkstra doesn't use any kinf of heuristic just the cost of the movements (maybe you want to call that an heuristic ??), it is just like BFS but for weighted graphs. Dijkstra with heuristics is basically A*.
Definitely you have no idea what you are measuring here. Steps? WTF is step and how it translates between the algorithms?
Timer was the only thing you need here if you were trying to compare.
Why this nonsense is in my recommendations?