Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
1  
"it's not because these developers are unaware of RL" Are you sure? That seems to be a big assumption. –  Tetrad Jan 24 '11 at 9:10
    
Care to share some links or papers on RL in pathfinding? –  falstro Jan 24 '11 at 12:06
3  
Given the various optimality / bounds proofs for A* (and related algorithms), what do you think RL brings to the table for pathfinding? –  user744 Jan 24 '11 at 13:40
1  
Related (found this in a different Question): ai-blog.net/archives/000178.html –  Tetrad Jan 25 '11 at 20:17
add comment

5 Answers

up vote 9 down vote accepted

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.

share|improve this answer
1  
+1 for your statement on the reward function. And, no, I believe it's a fair characterization. RL can be great at what it does, but I would not expect strict pathfinding to be in that set. (Note that I am deliberately excluding motion planning from this discussion. RL has been successfully applied to that sort of problem). –  Throwback1986 Jan 25 '11 at 21:50
add comment

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.

share|improve this answer
    
From a quick glance, A* seems to be cheaper to implement, faster to process, takes less memory, is more predictable, etc. than RL. RL might, however, produce more realistic results. –  Jari Komppa Jan 24 '11 at 10:52
4  
On the contrary, RL agents tend to produce hilariously unreal results during their initial learning phase. A* with some small steering behaviors looks a lot more natural. –  user744 Jan 24 '11 at 13:42
    
Okay, more realistic results eventually =) –  Jari Komppa Jan 24 '11 at 14:48
    
RL essentially precomputes perfect pathfinding behaviour. It is faster and simpler than A*, but takes a lot more memory. It is when you try to bring the memory requirements down that it becomes complicated and/or inconsistent. –  Don Reba Oct 20 '12 at 8:21
add comment

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.

share|improve this answer
add comment

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).

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.