Timkin, I certainly see your point. I just wonder if the details of word choices are potentially changing the intentions. While he metioned "path finding" the descritions are much more in line with neuro control.

-Kirk

Quote:

...and that would be neuro-control, which is certainly achievable... however the OP stated he wanted to do pathfinding using a neural network, hence my skepticism.

Wait a second, maybe I've used the wrong terminology to describe what it is I'm hoping to do sorry Timkin :-/

I was under the impression that pathfinding was navigating around a world without the path-planning part that you would get from the likes of way points and an algorithm like A*.

I read a few robotics papers yesterday, and "neuro-control" does seem like a more appropriate description.

Quote:

If we're abandoning the idea of pathfinding and considering instead trajectory control, then certainly you can use an ANN; it's overkill for simple, tiled worlds, but it's doable. If you'd like some literature references, I have a ridiculously huge pile of papers on my desk on this topic. 8)

I'd be really grateful of any references you could provide me with thanks!

Quote:

Original post by cossie I was under the impression that pathfinding was navigating around a world without the path-planning part that you would get from the likes of way points and an algorithm like A*.

There is certainly a lot of confusion in terminology within the published literature, so it's not surprising that you've read something stating the above, or come to that conclusion from what you have read.

Commonly though, path-planning is used to describe the problem of finding a path in a state space, which within robotics will include the location space, but will not typically be just that. Path-planning is used to describe configuration space planning, for example, or planning in more complex, abstract state spaces.

Motion-planning is generally used only within robotics to describe the planned movement of a bot, although this is a phase space planning problem as it includes velocity and location.

Pathfinding is generally reserved as a description of finding paths only in the location space of a robot or virtual bot. It most commonly arises in computer game literature because (a) we most often only care about the path to follow through the location space; and, (b) many authors don't understand that what they're doing is not pathfinding, but rather either motion-planning or path-planning! ;)

Control, on the other hand, is a lower level problem. It's how one translates action descriptions into actual effects within the environment, using the actuators/affectors of the system. One can easily build velocity controllers for a robot or virtual robot. However, building position controllers is difficult if the environment is not linear and open (fully connected). One common solution to this is to solve a pathfinding problem in location space given the velocity constraints of the robot/bot and return a set of waypoints for which movement between them is achievable and occurs in an open space. A closed loop control strategy can then be applied to control the robot/bot to each waypoint in turn.

Quote:

I'd be really grateful of any references you could provide me with thanks!

I'll see what I can whip up for you. 8)

Sorry for the delay in posting these references. I've been at home looking after my sick daughter and so I didn't have access to my pile of goodies. Anyway, here is some (hopefully) useful information.

Many people working in the field of neuro-control would probably consider Kumpati Narendra to be it's 'father'. Certainly his work in the late 80s and early 90s provided a solid foundation for the subsequent 15 years of research in this area. Some papers you should probably therefore read are:

Narendra, K. S., and Parthasarathy, K. (1990) Identification and control of dynamical systems using neural networks. IEEE Transactions on Neural Networks, 1, 4-27

Narendra, K. S., and Mukhopadhyay, S. (1993) Intelligent control using neural networks. (Tech Report # 9307) Yale University, Center for Systems Science. Also printed in M. M. Gupta and H. K. Sinha (Eds.) Intelligent Control Systems, IEEE Press. 1994.

On a more technical front, you might want to read:

Levin, A. U., and Narendra, K. S., Control of Nonlinear Dynamical Systems Using Neural Networks: Controllability and Stabilization. IEEE Transactions on Neural Networks, v4, n2, pp192-206

and

Levin, A. U., and Narendra, K. S., Control of Nonlinear Dynamical Systems Using Neural Networks - Part II: Observability, Identification and Control. IEEE Transactions on Neural Networks, v7, n1, pp30-42


More recently, there are some good collected works. For instance,

Narendra, K. S., and Lewis, F. L. (Eds.) "Special Issue on Neural Network Feedback Control", Automatica, vol. 37, no. 8, 2001.

Some excellent recent work has been conducted by David Hill. Take a look at

Wang, C., and Hill, D. J., Learning From Neural Control. IEEE Transactions on Neural Networks, vol. 17, no. 1, January 2006.

Of course, you might also want to look into fuzzy-neural control, which is as big a field as traditional neuro-control! Probably the easiest place to get a good coverage of the central ideas for fuzzy-neural control is the book by Junhong Nie:

Nie, J., and Linkens, D. A., "Fuzzy-Neural Control: Principles, Algorithms and Applications. Prentice Hall, 1995. ISBN-13: 978-0133379167


There are some very specific problems one faces when using neural networks (and any other function approximation scheme) for performing control. One of the biggest is known as the problem of "persistancy of excitation". Another related problem is that online learning schemes don't actually learn, but rather continuously adapt. There are hundreds (if not more!) papers covering specific problems related to neuro-control and fuzzy-neural control. If you find you're having some problems, post them to the sight and hopefully I can direct you to the right material to solve them.

Good luck with your project!

Cheers,

Timkin

I was wondering how the progress was coming along on this project. Any updates??

I was wondering how the progress was coming along on this project. Any updates??

@ Timkin, thanks a million for the recommended reading!



@ kirkd, I'm actually not having much success at the moment with the project and I'm quite surprised TBH.

The best performing bot I can get just goes straight ahead in the world until it hits the wall and stays there, there is no movement towards the target whatsoever.

I don't know how to add images to my posts so I'll do my best to explain the setup:

I have a 20 x 20 grid world (with boundaries, so the actual array is 21 x 21) and at present the bots start in the bottom left corner and the target is at the top right.

At the end of each simulation run (of about 80 loops) I rank the bots fitness based on your suggested fitness rating but I use a totalMoves counter instead of any sort of timer.

e.g. fitness = 1 + ((relativeX + relativeY) * totalMoves);

I've based my code closely on Mat Buckland's Smart sweepers project apart from how the bots fitness is calculated and that his sweepers can move at any distance where as my bots can only move one square at a time.

I've not had that much time to work on it since my last post so I'll give it a bit more thought today.

Interesting. It would appear that minimizing your fitness function should give a reasonable result. I would double check your selection function and your mutation/crossover operators. The problems I've had on many projects I've worked on in past could be tracked down to those places.

-Kirk

BTW - you can post images and movies online through ImageShack http://imageshack.us/

Quote:

It would appear that minimizing your fitness function should give a reasonable result.

Sorry kirkd, I don't understand what you mean by "minimizing" ? :-/

The fitness function you have is:

fitness = 1 + ((relativeX + relativeY) * totalMoves)

For the best result, you want to be as close to the goal as possible in the fewest possible moves. Closest to the goal would be related to (relativeX + relativeY) - of course that is my assumption of how these values are interpreted. I assume the relativeX and relativeY are the X and Y distances to the goal from the current position of your bot. The number of moves is totalMoves, and we want this to be as low as possible. Thus, if we try to make the total fitness as low as possible - i.e., we minimize it - we should have a good result.

As I mentioned, I'm making some assumptions about how the details of the fitness function relate to your desired result. Please correct me if I've assumed incorrectly.

-Kirk