Sign in to follow this  
Malamute

Genetic Algorithmn or Neural Networks for finding pathway in a maze?

Recommended Posts

Malamute    100
I want to have an algorithm that computes a path through a 2d maze like this: I was thinking of having a NN where each node is a tile on the maze the input is a 1 or 0 that corresponds to filled or not and it outputs a path through the maze in the same format, where 1 indicates a tile on the solution path and 0 indicates a tile not on the solution path. You could also do a GA where the solutions are 2d tilemaps where all the tiles that belong to the solution are filled in. This would keep the solutions DNA at a constant length. So will this work?

Share this post


Link to post
Share on other sites
Palidine    1315
Quote:
Original post by Malamute
I know about a star but I want to do something different!


That's fine as long as you're just doing it to play around with different AI algorithms. Otherwise, both those approaches are just plain bad choices for pathfinding. Pathfinding through a maze is pretty close to a "solved" problem.

If you really just want to play around with those algorithms it might be a lot more useful if you pick some problems that they're actually good at solving. (google can fill you in on those)

-me

Share this post


Link to post
Share on other sites
Sneftel    1788
GAs and NNs are not appropriate tools for this. It's like asking "How do I drive a nail into a piece of wood with a duck or echidna? I know about hammers, but I want to do something different."

Share this post


Link to post
Share on other sites
Sneftel    1788
I suppose it might. It certainly wouldn't work well. It would most likely be a disappointment. But you could probably make it work some of the time on especially simple mazes (like, 4x4 or something).

Share this post


Link to post
Share on other sites
dmatter    4826
Out of those two options I think a GA is a better option than an NN, but as mentioned previously neither are overly suitable options for the task. As a side note I dont think DNA is common terminology for GAs, 'Genomes' are and 'Chromosomes' maybe, but DNA stands for Deoxyribonucleic acid which a GA doesnt encounter - I think its just too 'low level'?

I used to design/program for micromouse robots and we used to use a weighted flood-fill algorithm, give it a look.

Share this post


Link to post
Share on other sites
AngleWyrm    554
If the entrance and the exit to the maze are both on the 'outside', then place one hand on a wall and just start walking. You will eventually find the exit. This does not work if the exit or entrance is on an island in the middle though.

--
This hammer is good enough to drive a railroad spike! Now where's that roofing nail?

Share this post


Link to post
Share on other sites
FippyDarkpaw    154
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
LorenzoGatti    4442
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.

Share this post


Link to post
Share on other sites
SnOrfys    200
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.

Share this post


Link to post
Share on other sites
lexchou    152
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
#-_-

Share this post


Link to post
Share on other sites
SnOrfys    200
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.

Share this post


Link to post
Share on other sites
Hk    132
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

Share this post


Link to post
Share on other sites
LYH1    122
If you want to slove problem using NN/GA, I think the problem most likely is how to feed the data in to the NN and GA. Better data representation make life more easy.
GA is a random search and NN is emulating some formulas,Feeding appropriate data structure they can do the exactly same thing of A*

If talking advantage and disadvantage between A* and NN/GA,
NN and GA need a long time to learn before they can use but A* will need more caulation in each search.

To make a NN/GA learn how to Survive in maze, converting the path into sequence of Direction or a graph is a good start.If the maze is not too complicate, the GA may find a path to survive in a finite sequence of Direction .
If the maze is really too complicate, add a bonus to the path which is more near to the exit than others so it may find a point that is most near to the exit. Start another training at the last postion it stay, find the more best point and so on, after a few times it can reach the exit.

Share this post


Link to post
Share on other sites
Drigovas    509
Well it sounds like it would really depend on the type of maze you're talking about. If it's the same maze every time, or if it's a maze that is generated using some sort of discoverable rule set, then you can use the various adaptive algorithms to find an optimal path. All the algorithm will be doing though is discovering the rule set by which you created the mazes [like, for example, blue floor means go forward, red floor means turn left, unless left is blocked then turn right, etc]

GA's and NN's will both fail miserably at finding their way through a random maze [if you can get them to succeed at all, without succeeding by sheer luck of the draw in the case of GA's, and even then you didn't find a solution to the problem of arbitrary maze-solving, just an anomaly]

In any case, the tool is wrong, as has been said.

Quote:
Original post by Sneftel
GAs and NNs are not appropriate tools for this. It's like asking "How do I drive a nail into a piece of wood with a duck or echidna? I know about hammers, but I want to do something different."
Beautiful. Love it. Even if I did have to wiki 'echidna'.

Share this post


Link to post
Share on other sites
cdrwolfe    126
What are peoples views on reinforcement techniques (Q learning, machine learning/Learning classifiers) for a task like this, seems to be swept under the carpet, or hardly mentioned, though i may be ignorant of the techniques.

Regards Wolfe

Share this post


Link to post
Share on other sites
Palidine    1315
Quote:
Original post by cdrwolfe
What are peoples views on reinforcement techniques (Q learning, machine learning/Learning classifiers) for a task like this, seems to be swept under the carpet, or hardly mentioned, though i may be ignorant of the techniques.


In a simulation, there's no point. You already have the complete maze information perfectly stored. There's nothing to learn or be reinforced. You just find a path ( A* ) through the known graph. It's easy and robust.

The short is that this is one of those "solved" problems.

The parts that are on the fringe are: how do you make it cost effective for hundreds/thousands of entities to simultaneously path and/or dynamically avoid each other along the way

-me

Share this post


Link to post
Share on other sites
Timkin    864
Quote:
Original post by Palidine
The parts that are on the fringe are: how do you make it cost effective for hundreds/thousands of entities to simultaneously path and/or dynamically avoid each other along the way


My suspicion is that cdrwolfe was asking about the use of ML techniques for learning a maze solver that could be applied to any new maze. Certainly, this is an interesting problem, as it summarises the task of solving problems by analogy. Unfortunately, one maze is NOT a good instance of any other maze (so using a small, finite set of mazes to train a maze solver would not necessarily provide you with anything more than something that kept getting lost and relied on an underlying (default) random search to find the exit).

You might be able to solve classes of mazes by analogy; for example, labyrinths.

Ultimately, the problem in using a GA to search for a solution path for the maze is how to encode candidate path solutions. The underlying problem is that paths vary in length, so you need a way to make your chromosome encoding invariant to path length, or your genetic operators robust to variable length chromosomes in parents during reproduction.

As for using an ANN to solve this, the only practical way I could see would be to use a recurrent architecture.

Cheers,

Timkin

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this