5 ms·

Allowing precomputation seems a little suspect, or at least difficult to incorporate into a comparison. I could offline precompute all pairs shortest path, then

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 http://www.optimization-online.org/DB_FILE/2015/05/4895.pdf

Symmetry 11y 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.
- idunning 11y 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?
  - Symmetry 11y ago
    I think the constraints are implicit in the forum the talk was given at. This is Game Developers Conference so the constraint is that the algorithm has to run on the computers that the game buying public possess. If you think you've got an algorithm that can blow the presenter's out of the water on a typical PC then I encourage you to test it and show it to the presenter if you succeed.
    - idunning 11y ago
      Implicit constraints kind of suck for the purposes of creating and sharing knowledge though, don't you think? Even constrained to the domain, there are a wide variety of devices people play games on, so I still think its misleading to say this is 1000x faster than an alternative without the huge caveat that benchmarking is multidimensional.
      - obstinate 11y ago
        No, they do not suck. For example, "This technique helps you build a frobble faster." "No, you can build a frobble much faster if you have sentient nanobots!" "We don't have those. I am speaking of techniques that actually work in reality." "But implicit constraints suck for sharing knowledge!" One of these two voices is saying something useful about how to do things better. To borrow a sports metaphor, it is moving the ball forward. That voice is not the voice that is complaining about the use of implicit constraints.
        idunning 11y ago
        Thats an explicit constraint, not an implicit constraint: The first person has an explicit constraint of "Lets consider only proposals that use existing technology". Thats exactly my point! Except in this case the implicit constraint was "must fit in memory for gaming applications", and I'm saying it should be made explicit. Its not that constraints are bad, just that they need to be shared along with the idea for it to be actionable. Implicit constraints are the enemy of doing things better, as they allow people to claim basically whatever they want with hidden caveats, which makes it harder for the non-expert to figure out what they need to actually get things done.
        Veedrac 11y ago
        I doubt a single person at the Game Developer Conference, watching a talk constantly referring to StarCraft, was at all struggling to understand that the technique was for game development. Even if they somehow managed to avoid that tidbit of knowledge, the memory and runtime costs were fully explained in the talk, so any reasoned developer would be able to consider the applicability to their situation.
bjterry 11y 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.
- idunning 11y 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.
- deleted 11y ago
  [deleted]
ketralnis 11y 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.
- idunning 11y 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?
  - darkmighty 11y ago
    You're missing the point here: this is a practical application. He's saying in the context that most people currently use A* his approach is much faster (and he does explain it uses more memory) -- the title is completely justified. You're nitpicking, really.
kevingadd 11y 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.
- idunning 11y 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.

Symmetry 11y 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.

idunning 11y 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?
- Symmetry 11y ago
  I think the constraints are implicit in the forum the talk was given at. This is Game Developers Conference so the constraint is that the algorithm has to run on the computers that the game buying public possess. If you think you've got an algorithm that can blow the presenter's out of the water on a typical PC then I encourage you to test it and show it to the presenter if you succeed.
  - idunning 11y ago
    Implicit constraints kind of suck for the purposes of creating and sharing knowledge though, don't you think? Even constrained to the domain, there are a wide variety of devices people play games on, so I still think its misleading to say this is 1000x faster than an alternative without the huge caveat that benchmarking is multidimensional.
    - obstinate 11y ago
      No, they do not suck. For example, "This technique helps you build a frobble faster." "No, you can build a frobble much faster if you have sentient nanobots!" "We don't have those. I am speaking of techniques that actually work in reality." "But implicit constraints suck for sharing knowledge!" One of these two voices is saying something useful about how to do things better. To borrow a sports metaphor, it is moving the ball forward. That voice is not the voice that is complaining about the use of implicit constraints.
      - idunning 11y ago
        Thats an explicit constraint, not an implicit constraint: The first person has an explicit constraint of "Lets consider only proposals that use existing technology". Thats exactly my point! Except in this case the implicit constraint was "must fit in memory for gaming applications", and I'm saying it should be made explicit. Its not that constraints are bad, just that they need to be shared along with the idea for it to be actionable. Implicit constraints are the enemy of doing things better, as they allow people to claim basically whatever they want with hidden caveats, which makes it harder for the non-expert to figure out what they need to actually get things done.
        Veedrac 11y ago
        I doubt a single person at the Game Developer Conference, watching a talk constantly referring to StarCraft, was at all struggling to understand that the technique was for game development. Even if they somehow managed to avoid that tidbit of knowledge, the memory and runtime costs were fully explained in the talk, so any reasoned developer would be able to consider the applicability to their situation.

bjterry 11y 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.

idunning 11y 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.
deleted 11y ago
[deleted]

ketralnis 11y 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.

idunning 11y 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?
- darkmighty 11y ago
  You're missing the point here: this is a practical application. He's saying in the context that most people currently use A* his approach is much faster (and he does explain it uses more memory) -- the title is completely justified. You're nitpicking, really.

kevingadd 11y 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.

idunning 11y 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.