JPS+ pathfinding – faster than A* [video]

http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than

by babuskov • 11 years ago

118 53 11 years ago

gdcvault.com

ingenter• 11 years ago

http://mikolalysenko.github.io/l1-path-finder/www/

jessaustin• 11 years ago

https://github.com/SteveRabin/JPSPlusWithGoalBounding

opcvx4• 11 years ago

Precomputation takes O(n^2) complexity so this is great for static environments like Starcraft maps where the units don't evaluate units in their path finding.

Udo• 11 years ago

They do evaluate buildings though.

opcvx4• 11 years ago

I wonder how OP solved this, if at all. There are too many of them to partially rebuild. Maybe they combine two systems.

imaginenore• 11 years ago

Starcraft maps aren't static, as buildings and characters can block paths.

opcvx4• 11 years ago

Maps themselves are static.

lorenzhs3• 11 years ago

On road networks (Google Maps style routing) much much bigger gains have been achieved. Taking things to an extreme, Hub Labelling achieves sub-microsecond query times on continental-scale road networks [1]. More flexible algorithms (e.g. Multi-Layer Dijkstra aka Customizable Route Planning, which Bing Maps supposedly uses) achieve sub-millisecond query times, with preprocessing times for new metrics less than a few minutes. This allows full timely integration of traffic information etc.

On a 2D grid, there are a few differences, but even modeling it as a graph and applying road network algorithms (even simple ones like Landmark Routing) sounds like it would yield similar, if not better speedups.

[1] http://research.microsoft.com/apps/pubs/default.aspx?id=1456...

AnonymousPlanet• 11 years ago

Is there any kind of proper formal definition for the algorithm? The linked paper is a bit unstructured in this regard and seems a bit implementation focussed.

lorenzhs3• 11 years ago

Well, it's a paper from the Symposium on Experimental Algorithms ;) You can find a good list of interesting route planning papers, including hub labeling, at http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/route... (page is in German, but the literature is English of course)

lnanek22• 11 years ago

It would be nice if Google Maps started doing a decent job, though. I lived for years in NJ and I would typically require 3 roads and 20 minutes to get anywhere I needed to go shopping because I would drive to the highway, hop on, get off on the road to my destination, then be there. Even if I avoided the highway I would get there in 30 minutes with smaller roads, taking the minimum needed to go the right direction toward the destination.

Google Maps? It was a disaster. It would take the small roads since it couldn't bear to drive 2 blocks the wrong direction to get on the highway, then every small road it would alternate taking a left and a right and end up with dozens of turns when a human only needed 3 or 4. I actually met the ex-Googler who bragged about writing that algorithm that alternates left and right, I think he must be responsible for millions of hours of lost time for drivers just because he didn't realize turning has a cost and was trying to draw a diagonal as best he could.

Does it really make sense to brag about fast calculation speed when the calculation is a disaster? I'd rather wait a minute for a calculation and get the right one, than have the wrong one back in 3 seconds. I think the Google Maps engineers don't understand this.

lorenzhs3• 11 years ago

Actually, the algorithms used are provably optimal in regard to whatever metric is plugged into them. This means that no matter which of these algorithms you use (including Dijkstra or A*), you will get the exact same result. The difference is in the time and space required for precomputation vs at query time. That includes Contraction Hierarchies, which Google Maps uses (or used?). But if they screw up the optimization metric, then the algorithm can't save them either.

codeka• 11 years ago

I work on Google Maps and can confirm that it definitely takes the time required to turn left vs. right into account. If you send me an example of a bad route (you can use the web interface, which uses the same backend as Google Maps on your phone) I can take a look as to why it's routing you the way it is. My email address is in my profile.

mathgenius4• 11 years ago

I love the connections to the continuum case where these problems show up looking like ways of solving path integrals, Huygens principle, etc. In particular, some of these jump point rules look alot like diffraction (of a wave) around a boundary.

mathgenius4• 11 years ago

Ah, and it seems to be connected to ray marching also, as demonstrated so well by the fractal lab guy: http://sub.blue/fractal-lab

willvarfar• 11 years ago

How is it connected to ray marching?

I'm curious; my own playing with the area: http://williamedwardscoder.tumblr.com/post/26628848007/rod-m... http://williamedwardscoder.tumblr.com/post/28935319219/rod-m...

Would like to make it faster :)

darkmighty3• 11 years ago

Indeed light simply just uses a Dijkstra-like flood [1] fill :)

This isotropic propagation is the reason Fermat's principle [2] works.

[1] The flood pattern, or Huygens principle, in turns follow from the local (fundamental) and isotropic (for most media) nature of Maxwell's equations for electromagnetic propagation.

[2] https://en.wikipedia.org/wiki/Fermat's_principle

justinhj• 11 years ago

It's a bit misleading to call this faster than A* since it is still using A* under the hood. Most optimizations to path finding with A* involve changing the world representation somehow. Most do not use a simple grid, with navigation meshes being more common.

Very clever though, I like it.

andor• 11 years ago

It's also misleading because nothing optimal is faster than A* . Quote from AIMA:

"A∗ is optimally efficient for any given consistent heuristic. That is, no other optimal algorithm is guaranteed to expand fewer nodes than A∗ (except possibly through tie-breaking among nodes with f(n) = C∗). This is because any algorithm that does not expand all nodes with f(n) < C∗ runs the risk of missing the optimal solution."

bnegreve• 11 years ago

nothing optimal is faster than A* .

For what task? The speaker seems to be concerned with the problem of answering repeated path-finding queries for a single static map. With that problem in mind A* is indeed sub-optimal since it redoes all the computations for each query.

_delirium2• 11 years ago

In the general setting A-star is optimal. JPS (and JPS+) can speed it up if you have additional information about the topology of the search space: 1) search is on a rectangular grid, and 2) movement between adjacent grid squares has uniform cost. In that case, you can take advantage of certain properties/symmetries of a rectangular grid to safely "skip" parts of the expansion that A-star would normally do, while still being guaranteed to find the optimal solution.

The JPS paper from a few years ago explains in more detail: http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-g...

JulianMorrison• 11 years ago

What probably fudges around this, is that all the nodes get looked at before any routing code starts running. A* is coming to the graph cold.

darkmighty3• 11 years ago

In that sense nothing is faster than Dijkstra's. There are problems for which A* heuristic fails completely, and Dijkstra's is better. JPS exploits a more specific structure of pathfinding just like A* exploits structure given by an heuristic. We have to be very careful to the setting when we say something is 'optimal'.

idunning7• 11 years ago

Allowing precomputation seems a little suspect, or at least difficult to incorporate into a comparison. I could offline precompute all pairs shortest path, then I'll be 10^6 faster than Astar, for example. Where do you draw the line? In the Q&A someone asks this, and points out that the precomputation in the video has a lot/all of the shortest paths stored. The speaker says that requires too much memory to store - so basically, arbitrary line here (what is too much?)

Another problem is with heuristics in general: if you are not guaranteed to find an optimal path (which is possible with Astar variants), then you have a two-dimensional way to understand heuristics: run time, and solution quality. e.g. I can give you a bad path very fast.

Finally, implementation data structures and language. Two people implementing the same algorithm in different languages are going to have different performance.

Here is a preprint that addresses these questions for heuristics for two NP-hard problems (MAXCUT and QUBO): http://www.optimization-online.org/DB_FILE/2015/05/4895.pdf

Symmetry2• 11 years ago

Precomputing all shortest routes uses O(n^2) memory with the size of the map, though as opposed to the O(n) memory that this uses. For a Starcraft map that's the difference between a MB and a TB.

idunning7• 11 years ago

Sure, but thats exactly my point. Given a set of well-stated limitations (like, cannot use more than N^x bytes of storage for an instance of size N, using the same standard library of data structures etc) we can make meaningful comparisons. I could come along with a method that uses O(n log n) memory and crushes this (maybe) - how do we declare a winner now, without some sort of context?

bjterry• 11 years ago

This isn't a heuristic search, it's guaranteed to find an optimal path the same as A*. More generally, this isn't a talk for theoreticians, this is another tool in the toolbox for game AI engineers, and personally I find it very clever. Whether you can afford the memory cost for the precomputed data is a question that must be answered in the specific context of your application.

idunning7• 11 years ago

Agree that everything must be contextualized. My point is, you saw this presentation and liked it because it seems like a good idea, and the performance is apparently good relative to something else. For an engineer (or a theoretician) to reason about that claim of improved performance there needs to be a systematic way to understand it. All I'm saying is that way this was done doesn't allow us to understand it very well - precomputation being a big part of that.

ketralnis• 11 years ago

You're focussing a lot on whether they an algorithm can say that it "wins" and trying to find a way for them to say that fairly. I don't think that's important at all.

It seems like it's probably better for some problems and not others, like where some precomputation is both practical and helpful. So if you want to see if that's possible for a particular problem, try it and see.

idunning7• 11 years ago

"Try it and see" will be pretty definitive (assuming you can implement it correctly, which is nontrivial), but it has scaling problems.

I'd argue thats exactly what this talk is about: the presenter claims to have a new method that "wins", i.e. beats something else (A* and some variants on it). So the presenter at least thinks its important, as does the competition he mentions in the talk. He thinks you should try it, because he is saying its better. I'm claiming that without more care, its hard for me to take action on that claim because "better" is not a single dimensional thing, its a rich trade off between at least run time, precomputation time, precomputation memory, and arguably implementation difficulty. It'd be nice to not have to try everything yourself for your particular problem, don't you think?

kevingadd• 11 years ago

Precomputation is extremely common in realtime, high quality pathfinding scenarios like games - I wouldn't be shocked if realtime navigation (google maps, apple maps etc) uses it too. In that context something like this that leverages precomputation to be fast & accurate makes a ton of sense.

Most game level formats I'm aware of these days include some sort of precomputed navigation mesh that's used to guide intelligent pathfinding.

idunning7• 11 years ago

Oh for sure, precomputation is essential. Hell, on a 100-1000 node sparse graph you can store all pairs shortest path info in a really small amount of data (like, PC game feasible for sure). For a game situation I'd be willing to burn a lot of time to crunch down pathing times, but memory pressure is real - so there is a "pareto"/nondominated set of algorithms that explore the tradeoff between memory consumption and run time, and the question is not whether you are 100x faster than another algorithm, but whether you are improving that "efficient frontier" of algorithms by using the same memory as another algorithm but running faster, or running as fast as another but using less memory.

striking• 11 years ago

uniform cost grids

There are very many grids that do not fit this in real (not theoretical) applications. I honestly can't think of when I'd use this algorithm.

mathgenius4• 11 years ago

Well, yeah, but the whole question of extending this algorithm to arbitrary (weighted) graphs is still very interesting: it seems to rely on some kind of discrete [1] version of parallel transport.

[1] http://ddg.cs.columbia.edu/

andrepd• 11 years ago

As a side note, I love the index on the left hand side of the player, that lets me quickly jump to any section of talk, instead of having to fish for the part when he starts talking about the algorithm, for instance. An awesome feature I wish other websites had too.

h1fra• 11 years ago

Same note, at first I was like "another video I won't watch watch because I'm only curious about one point of the talking" then I saw the menu. Very cool feature, greatly optimize user experience in a simple way

bsdetector• 11 years ago

On a side note, you can increase performance of presentations by 25% by not leaving time for questions. I find Q&A is often the best part and I wish the conferences left more time for it.

wesleyy• 11 years ago

Did you mean by leaving time rather than "by not leaving time"?

jokoon• 11 years ago

seems like optimizing something always involves precalculations.

kbwt2• 11 years ago

But how does it compare to A* on a reduced[1] visibility graph?

[1] http://kovan.ceng.metu.edu.tr/~kadir/academia/courses/grad/c...

obstinate2• 11 years ago

That page claims it's about 40% faster than A*. Multiply through the ratios and you'll have your answer. (1000x faster is a lot more than .4x faster, so I guess it compares quite favorably.)

kbwt2• 11 years ago

That's for A* on a complete visibility graph, which is much faster than on a uniform grid. I only added the link so that the reduced terminology is clear to everyone.

beefsack• 11 years ago

I believe JPS only works for unweighted graphs, so you can only compare it to A* for that particular case.

_delirium2• 11 years ago

More specifically, JPS works on unweighted grids (not arbitrary graphs). That allows it to use properties of a grid topology to figure out where it can safely "jump" without sacrificing optimality.

JPS+ pathfinding – faster than A* [video]

Related Stories