Why is Reinforcement Learning so rarely used in pathfinding?

Question

The venerable shortest-path graph theoretic algorithm A* and subsequent improvements (e.g., Hierarchical Annotated A*) is clearly the technique of choice for pathfinding in game development.

Instead, it just seems to me that RL is a more natural paradigm to move a character around a game space.

And yet I'm not aware of a single game developer who has implemented a Reinforcement Learning-based pathfinding engine. (I don't infer from this that the application of RL in pathfinding is 0, just that it's very small relative to A* and friends.)

Whatever the reason, it's not because these developers are unaware of RL, as evidenced by the fact that RL is frequently used elsewhere in the game engine.

This question is not a pretext for offering an opinion on RL in pathfinding; in fact, i am assuming that the tacit preference for A* et al. over RL is correct--but that preference is not obviously to me and i'm very curious about the reason for it, particularly from anyone who has tried to use RL for pathfinding.

Answer 1

I would imagine it's because, since you won't get any useful generalization of policy out of anything but toy problems, and the reward function is going to look suspiciously like an A* heuristic, the prospect of using RL tends to look like a really overbuilt, inefficient way of getting results that are identical with A*'s at best, but probably aren't going to be nearly that good.

This may be unfair to RL, and if so I'd be interested in hearing why, but I'm not really seeing anything to indicate that.

Many of us also remember what pathfinding was like in games before widespread adoption of A*, and aren't eager to inflict anything resembling those days on players, or suffer the market consequences of doing so.

Answer 2

I'm confused by the suggestion that RL is "a more natural paradigm". I don't see how reinforcement learning maps to the problem domain anywhere near as cleanly or accurately as graph search does. Typically you don't want an agent to learn - you've assumed that they already know the route. Instead, you want them to pick and use the most direct route available, and graph search facilitates that in a near optimal way. If you were to use RL offline to calculate the best direction to take at any given node for any given destination, that would end up bring broadly equivalent to A*, except requiring significantly more memory* and also requiring that the developers were very careful to ensure that all nodes were adequately explored during training. And that training will just yield a value that we can already approximate very well with the Pythagoras equation, due to knowing in advance that the graph obeys Euclidean rules of distance. (This is, of course, not the case for all situations where graph search and/or reinforcement learning may be employed.)

(Regarding the memory issue: If you had 1000 possible quantised positions on a map, that's 1000 nodes plus 1000 * M edges (where M is the average number of nodes reachable from any other node.) That, plus the heuristic, is enough for A* to operate. For reinforcement learning to work, at least in the way I envisage it, you'd also need 1000 entries for each of those 1000*M edges, to score the reward value of following that edge for any of the 1000 possible destinations. That's a lot of data - and every single bit of it has to be reasonably accurate to avoid loops, detours, or dead-ends.

Answer 3

Without knowing much about RL, I'll attempt to answer your question with other questions:

Using RL, can you determine if it's possible to reach point A from point B?

Can RL guarantee reproducible/consistent/testable navigation behavior?

How does memory and CPU run time requirements compare vs. A*? Likewise, how much can you precompute compared to, say, nav meshes?

How does RL fair in an environment with dynamic collision?

How much more difficult is it to understand and implement RL correctly vs, say, steering behaviors?

Are there any good middleware providers for RL?

Maybe those questions can help you with your answer.

Answer 4

Pathfinding is a relatively "solved" problem, RL is not.

With A*, developers can create heuristics quickly and improve them over time. RL (I'm talking about Q-Learning, when referring to RL here), takes time to compute the best learning rates and discount factors (time worth spending on other aspects of the game).

Answer 5

It really depends on the types of the game. If everything in the game is static, it's more efficient to use A* search. However, if there are other human players moving in the same area, A* search is guaranteed failure. A* search has no idea about where other players are heading. On the other hand, RL can model other players' behavior and find a better path which takes other players movement into consideration.

Answer 6

In general, I'd say that the choice between RL and A* comes down to one major part of the setting: is the terrain known in advance or not? If it is, A* should be used. If not, RL should be used.