Genetic Algorithmn or Neural Networks for finding pathway in a maze?
Maybe if you were training an NN or GA to solve mazes in general without a foreknowledge of what the maze looks like. e.g. A generic maze traversing strategy. It would be interesting to see if a GA or NN came up with the "hand on the wall" solution.
Quote:Original post by InnocuousFox
Maybe if you were training an NN or GA to solve mazes in general without a foreknowledge of what the maze looks like. e.g. A generic maze traversing strategy. It would be interesting to see if a GA or NN came up with the "hand on the wall" solution.
Ahh good point. Since A* assumes your AI have perfect knowledge of the maze paths, an evolved general maze solver would be interesting.
To the OP, I think what are suggesting is feasible and you could train an AI model for each maze/level.
Not sure how worth it this would be for a 2D game AI, but as research it is pretty cool. A quick google for "neural net maze traversal" shows a few papers on the subject.
Quote:Original post by InnocuousFox
Maybe if you were training an NN or GA to solve mazes in general without a foreknowledge of what the maze looks like. e.g. A generic maze traversing strategy. It would be interesting to see if a GA or NN came up with the "hand on the wall" solution.
Mmm, I'd guess also it would be some of the classical graph traversal algorithm at the end. Just some Prim, Kruskal or a plain DFS/BFS.
Quote:Original post by InnocuousFox
Maybe if you were training an NN or GA to solve mazes in general without a foreknowledge of what the maze looks like. e.g. A generic maze traversing strategy. It would be interesting to see if a GA or NN came up with the "hand on the wall" solution.
It would be an interesting feat, but a worse waste of programming and computational effort than the OP's problem because it can be implemented by hand easily and exactly instead of imperfectly the hard way.
Generic "big hammers" need either more difficult problems, e.g. not only reaching the exit once leisurely but iteratively finding the shortest path, or higher performance objectives, e.g. taking advantage of all visible walls rather than a single hand on the wall.
It must be a problem where a good solution is as complex as the GA/NN infrastructure and approximate evolved solutions are competitive with too complex or too expensive exact ones.
Interestingly enough, I seem to remember that a problem similar to this, if not exactly the same, is covered early on in Mat Buckland's AI Techniques For Game Programming using a GA (I don't have the book with me to verify). Though I believe he noted what others here have already noted - there are much better solutions to this problem.
Quote:Original post by SnOrfys
Interestingly enough, I seem to remember that a problem similar to this, if not exactly the same, is covered early on in Mat Buckland's AI Techniques For Game Programming using a GA (I don't have the book with me to verify). Though I believe he noted what others here have already noted - there are much better solutions to this problem.
I read that book, and I tried using GA in maze pathfinding, but I failed
#-_-
Well, in a week from now I'll be moving back to my house (with the wife's family - on the other side of the country - for the summer) and my book is there... when I get there, I wouldn't mind working out the problem again. It could be fun.
Well, even with hard pondering, I cannot see a real way to use NNs or a GA in order to solve a maze, because they are totally different. And by totally, I mean totally.
A NN basically creates a hyperplane in some multidimensional dataspace which separates 2 classes of entities. Ok, you can use some techniques to create a hyperplane which can be interpreted differently, but you end up with a hyperplane in a multidimensional space.
Assuming you could solve the pathfinding problem with a NN, you whould have to find a general mapping f: Hyperplane -> Path in maze, thus, you basically need to map a n-dimensional vector to a sequence of movements. I dont think this can be done generally. You *might* be able to create a NN that separates solvable mazes and unsolvable mazes with a certain probability, but I do not think you can find the path somehow.
Same thing with the GAs:
A GA basically traverses a multidimensional curve and tries to find a minimum (not necessary a global minimum). Thus, a GA is going to take this multidimensional curve and create a vector on this curve which is a minimum. If you try to model the distance of the current field to the exit (for example using the manhatten-distance), and using actions as a vector, you basically end up with a brute-force-GAP-algorithm (try to find a way through a graph), because you are unable to easily combine existing solutions into new solutions, because there are some fancy restrictions called "walls" in there.
thus, the problem with GAs is even deeper, I dont see a way to model the problem.
If I had to build an algorithm to explore an unknown maze, I whould just use a variation of the djikstra-algorithm or some similar all-pairs-shortest-path algorithm using the intersections as nodes or something like that, because that will find the shortest path somewhen and once it found the path, further searchers can find the path very fast.
Greetings, Hk
A NN basically creates a hyperplane in some multidimensional dataspace which separates 2 classes of entities. Ok, you can use some techniques to create a hyperplane which can be interpreted differently, but you end up with a hyperplane in a multidimensional space.
Assuming you could solve the pathfinding problem with a NN, you whould have to find a general mapping f: Hyperplane -> Path in maze, thus, you basically need to map a n-dimensional vector to a sequence of movements. I dont think this can be done generally. You *might* be able to create a NN that separates solvable mazes and unsolvable mazes with a certain probability, but I do not think you can find the path somehow.
Same thing with the GAs:
A GA basically traverses a multidimensional curve and tries to find a minimum (not necessary a global minimum). Thus, a GA is going to take this multidimensional curve and create a vector on this curve which is a minimum. If you try to model the distance of the current field to the exit (for example using the manhatten-distance), and using actions as a vector, you basically end up with a brute-force-GAP-algorithm (try to find a way through a graph), because you are unable to easily combine existing solutions into new solutions, because there are some fancy restrictions called "walls" in there.
thus, the problem with GAs is even deeper, I dont see a way to model the problem.
If I had to build an algorithm to explore an unknown maze, I whould just use a variation of the djikstra-algorithm or some similar all-pairs-shortest-path algorithm using the intersections as nodes or something like that, because that will find the shortest path somewhen and once it found the path, further searchers can find the path very fast.
Greetings, Hk
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
