Path-finding is often associated with AI, because the A* algorithm and many other path-finding algorithms were developed by AI researchers. I've often heard talk of using neural networks or genetic algorithms in path-finding, and I'll describe why I don't see this as being terribly promising.
Neural networks are structures that can be "trained" to recognize patterns in inputs. I believe they are a good match for problems in which pattern recognition code is difficult to write (one knows the patterns but not how to recognize them) or in which the patterns are dynamic (one does not know the patterns ahead of time). Path-finding, in my opnion, is neither of these: we do know how to solve the problem, and we have a general algorithm that can handle all sorts of patterns (mountains, rivers, valleys, etc.) without special code. We want to do the same thing in all the cases: find a good path. If on the other hand, the problem was to do different things in each case (for example, meditate if you're on a mountain, swim if you're in a river, or run if you're in a valley), then you need to determine which type of landscape you're in, and for that it may make sense to use neural networks. (If you're using a static map, however, I would recommend that you simply mark the areas of each type.) For path-finding itself, however, I don't think we need a different technique for each type of landscape, so I don't consider it important to recognize the patterns in the landscape.
Genetic Algorithms allow you to explore a space of parameters to find solutions that score well according to a "fitness function". I believe they are a good match for problems in which it's not clear how to find a solution. They're also a good technique to use if you have little information available about what kinds of parameters are good. Genetic Algorithms are essentially a blind search over an area, with some feedback that tells you if you're getting closer. However, if you know something about the parameter space, you can do better than a blind search: you know which direction to travel in, and it's likely you'll get there faster if you know where to go. For path-finding, we know algorithms that can help us find a good path; why look for random paths and evaluate them? Genetic Programming takes Genetic Algorithms a step further, and treats programs as the parameters. For example, you may be breeding path-finding algorithms, and your fitness function would rate each algorithm based on how well it does. Again, I believe Genetic Programming works well if you don't know a good program to solve your problem, but humans tend to do better than random trial and error. John Koza at Stanford has shown me genetic programs that do a good job for some problems, but don't handle all the cases; also they're not the simplest or fastest program that can do the job. If you're a student of evolution, you know that nature has not produced the best solutions; it just finds those that are "good enough". Human reasoning can often come up with better solutions than evolution's blind search. Nature didn't come up with the wheel, with fire, or a cure for Polio. On the other hand, Genetic Algorithms and Genetic Programming can come up with solutions that humans just hadn't thought of, especially in problems that defy logic. Still, path-finding has been extensively studied and we have good algorithms; I think Genetic Algorithms are better suited for problems that we haven't found good solutions for.
Back: Walking Traps | Up: Home | Next: References |
Last modified: Sun Nov 18 11:32:17 2001 From Amit's Game Programming Site | Copyright (C) 2000, Amit J. Patel |