Hi, I'm a student in master I have to do some research on the pathfinding using neural networks the idea is to make a neural networks use to store the distance between the different points on the map in real time strategy game. When the map is changing we learn the new distance. We are running this with a A* for example This should be faster than running the A* alone. But I dont find any information on this idea and I'm not sure if this will be faster? If you are any information about this let me know? Thanks Gazzall50

Quote: Original post by Gazzall50
I'm a student in master...

... which probably means you should be finding this stuff out yourself.

Quote: Original post by Gazzall50
I have to do some research on the pathfinding using neural networks the idea is to make a neural networks use to store the distance between the different points on the map in real time strategy game. When the map is changing we learn the new distance. We are running this with a A* for example

This should be faster than running the A* alone.

But I dont find any information on this idea and I'm not sure if this will be faster?

If you are any information about this let me know?

A* is quite good, which is why it is so well researched. A hardware based recurrent network would be able to solve the problem almost instantly. If you're looking for a software based solution, you really ought to think about why A* would be used if an ANN could do it faster.

Hi,

Thanks for your answer frob it did not help me and firstly in my country the master is not only research it is only 3 months to do this small research. And I still have class with other stuff to do (not only research)

I think I should try an other forum where I am sure I wont answer to me frob.

Gazzall50

Frob gave you a perfectly good answer. On top of what he said, debugging a path-finding algorithm is very hard as it is. I don't even want to imagine the nightmare of debugging a NN-based path-finding system.

Quote: Original post by Gazzall50
Hi,

Thanks for your answer frob it did not help me and firstly in my country the master is not only research it is only 3 months to do this small research. And I still have class with other stuff to do (not only research)

I think I should try an other forum where I am sure I wont answer to me frob.

Gazzall50

I'm not sure what the problem is. You originally said "This should be faster than running the A* alone."

I'm suggesting that in software, I doubt you will find such a thing. I'll try to make it more clear:

If there were such a thing, it would have probably been really big news and added on to pretty much every A* paper as a way to improve it. Therefore I suspect that such an improvement either is not practical at this time, has not been researched, or maybe both.

In hardware, a recurrent or relaxation network would solve the problem faster than A* ever could.

The idea with neural networks at the moment is that they aren't better than an algorithm that has been designed for a specific purpose, like the A* algorithm. I'm not too sure that you will be able to get better results than the A* algorithm.

Thanks frob for your new answer. umbrae the idea is not to find an other alogrithm than the A* the idea is to implement a neural network in the A* algorithm the neural network will be use to get a better heuristics function, the aim will be to return a better approximation of the different distance using the ANN whcih will learn them.

Gazzall50

Quote: Original post by Gazzall50
Thanks frob for your new answer. umbrae the idea is not to find an other alogrithm than the A* the idea is to implement a neural network in the A* algorithm the neural network will be use to get a better heuristics function, the aim will be to return a better approximation of the different distance using the ANN whcih will learn them.

Gazzall50

This would make sense if the performance of A* depended tremendously on the quality of the heuristic, or if the ANN could be evaluated very cheaply, compared with visiting one node in A*. The first thing is hard to measure, and the second is clearly not true.

I can think of three more problems with the approach:
1) In order to guarantee finding the best path, your heuristic must never overestimate the distance to the goal. It is hard to enforce something like this with an ANN.
2) As I mentioned before, testing and debugging a path-finding algorithm that uses ANNs is probably very difficult.
3) In many games the map can change very quickly and it would be hard to keep the ANN correctly tuned.

I can think of a situation where these problems would be very painful. Imagine there are two paths to go from one area to another. The short path is currently blocked, so the ANN learns that the two areas are far apart. Then someone removes the obstacle, but using the ANN as a heuristic, A* might keep returning the long path as the best, giving incorrect results and not learning the new configuration.

If you go ahead with the project, be sure to post your results here, whatever they are. Good luck!