The third installement of our Bot Navigation series is now online: Advanced Obstacle Avoidance.

In this issue, we discuss evolution in real-time noisy environments, practical optimisations for evolutionary solutions and representations enhancements that increase the model's performance.

http://ai-depot.com/BotNavigation/Avoidance-Introduction.html

Enjoy!

First off let me say you run well managed, excellent site, most likely the most comprehensive one on the Internet concerning this broad topic of AI.

I've read your 3 articles concerning Neural Networks for Bot Navigation on AI-Depot.com. I am quite happy I found them, and am anxiously waiting for the 4th. I am attempting something very similar for a mini-research project at university, only in my case instead of a first person shooter, it's a 2d real physics space combat game (a la Star Control).

I've put much time and thought researching my project, and I have some promising ideas (I hope :). But a few questions have risen that are hindering my progress - I'm unsure what to do. So, I wondering if I could ask a some questions concerning your experiences: (I hope you won't mind.. I have quite a lot.. :)

<ol>

<li>How did you come up with the idea of using a multi-layer perceptron NN? Was it based on research, or did you attempt multiple NN architectures and found that this approach was the best?</li>

<li>In the same context, why did you use the sigmoid function as activation? vs a step or a competitive (Ie: obstacle A is more important than B, so thus I will concentrate on B). Or a combination?

I find your general approach description a bit vague; possibly since I am not too familiar with the innards of the Quake engine. From what I understand it, the NN is expected to be run real time, outputting a rotation direction (yaw), I would think, running every cycle.</li>

<li>How exactly did you go about running the GA? Is it some modified Quake Engine or a some sort of complex script? Do you have an initial population, and for every genotype (bot), you run a script in quake on some level with the current NN, finally measuring its fitness? You do this for every bot in the population, and then repeat, generation after generation? If this is so, it must've taken quite a long time to run a GA...</li>

<li>Instead of using a traditional NN learning approach of back propagation, GAs seem like a good idea for an unsupervised training situation such as this. Your 3rd articles mentions the use of a binary crossover, (assuming it is just an array of node weights). How do you select the split point? Is it just halving the chromosome, or do half at each node layer? Or something similar?</li>

</ol>

Before I ask any further questions, let me take a moment and describe what I'm attempting to achieve. The idea at the moment is to create an AI that simply evades obstacles and attempts to stay alive as long as possible. There are many factors that I'm considering in hopes to create a robust AI:

<ol>

<li># of objects: I have the potential of having ALOT of objects flying on the screen, some more lethal than others. Most of them do have some sort of effect on what will be going on.</li>

<li>manoeuvring is more complex than in an FPS, instead of just moving up, down, left, right, the ship must thrust in the opposite direction to slow down. There are engines on both the front and the back of the fighter.</li>

<li>the notion of the pull of gravity from large objects</li>

<li>positions of obstacles, are threatening in multiple levels (bullets are fast and small, but a large asteroid you are hurling at sideways is just as dangerous)</li>

<li>the facing direction of enemy fighters (ie: he may be flying away from me but his guns are pointed right at me)</li>

<li>Would you advise, instead of using a GA, to manually attempt to create a custom NN architecture from scratch, and then manually, in real-time, dynamically change the weights, biases and/or activation functions in hopes of creating a robust AI? Is this intuitively possible in finite time?</li>

<li>In the last article you began mentioning advanced behaviours to be added to the NN: "This allows the speed to be controlled by high-level path-finding algorithms, potentially over-ridden by a braking force. A simple neural network could be trained to do this, using a sense of urgency in the proximity of the obstacles as heuristics. This is part of on-going work, and is showing great promise." - Interesting concept; something I haven't thought of. Would it be ideal to split up my scenario into multiple NN's possibly? For example, A) one strictly for obstacle avoidance, then B) threat avoidance C) attacking manoeuvres, etc? Or, in my case, would it be best just to combine everything into one NN (which would mean quite the number of complex inputs I would think).

There are a few options that I can do for the output of my network: 1) Outputting 2 values, a thrust (forward, back, or none) and a rotating (left, none, right). 2) Outputting a position "I want to go here" and then use another algorithm in the physics engine to figure out the proper thrust and rotational commands. I'm unsure which one would be the more ideal. In your opinion, is it best to keep the neural net simple and not let it bother with the details of (1) and do (2)?</li>

<li>And finally... Why did you limit the # of sensors (I'm assuming obstacles + places to go) to such a small number? Is it simply that only the most immediate information is relevant, and since the NN is run all the time, there is no need to look beyond a particular radius? If so, did you arbitrarily decide on this radius, or is it based on factors such as running speed?</li>

</ol>

Thank you for taking the time to read and answer my questions.

Regards,

Mark

Mark, thanks for the support, and welcome to the site!

Glad to hear you're interested in the topic, I personally find it fascinating too ;)

1) A hunch. I did a course about NN, feedforward seemed the simplest -- for a staring project. It turned out alright, as FFNN allow high-level pattern recognition and regression nicely ;)

2) Sigmoid allows detecting non-linear patterns too.

3) I modified quake and accelerated time. Each bot has a "think" procedure, which runs the NN solution and evaluates its fitness. This is done over k seconds. At first, all the bots belonged to the same population, but now each bot has its own GA inside it.

4) I use uniform crossover, but I would select the crossover point randomly for binary crossover (probably using phenotype-coherent breeding, as you suggest with the layers).

[...] next set of questions

6) No... it's time consuming, difficult, and inflexible.

7) This is something you'll realise as you experiment. NN don't scale well at all. Big networks usually have complex problems and huge-search spaces. That doesn't work well. Splitting it up is your job as an AI designer to help things work

Also try and keep things as simple as possible, hence try and make them relative to the current state (abstracting out unnecessary info). So using the "yaw" would be easier, relative position harder but possible (i think).

8) The limit on sensors is for speed. It takes some time to scan the data, and when you have more than one, the slow-down is noticeable.

I have the GA evolving the sensor layout, but the results are not conclusive yet; there are many working solutions. So I'm picking the radius myself based on the behaviour obtained. I do plan to change it dynamically to save processing, but haven't done it yet.

Well, I hope that helps a bit!

Alex,

Thanks for the response. A few things aren't still completely clear though..

3) So thus, you run each bot during the fitness evaluation stage through some map for a fixed amount of time. Do you use the map and same position for all the bots in the same generation, or do you randomize their positions? You mentioned using different maps, again, did you run an entire GA on a single map (possibly increasing the complexity of each map for each entire GA run), or did you use different maps for later generation to force fitness diversity into the population at a given generation?

I'm not sure what you mean by "each bot has its own GA inside it". Do you mean when you run your experiments, you have separate bots evolving with different fitness functions based on the interactions between them and the environment?

I'll add in two more questions for good measure:

A) How did you create the weight values of the NN? Simply randomly between the typical range of near zero (-0.25 to 0.25)?

B) Did you use much mutation to tweak the weight values of the NN? If so, what was the ideal rate that allowed your GA to converge in reasonable time? (Feel free to let me know what your crossover rate was as well.. :)

I think I'm done. Thanks again.

Mark

3) I've embedded my bots, which means they are physical entities that cannot be moved around for the convenience of GA. I run the fitness evaluation wherever it may be in the terrain. It also implies that each bot has it's own fitness function, and can't swap solutions with neighbours.

I use the same map, no need to increase complexity. The way I modeled the problem implies the cases are fairly simple and abstract, so it applies to a level of any complexity.

A) Random within the range [-1,1] but no constraints are imposed on the evolution.

B) Mutation rate is 0.001 and crossover is 60%/40%, as recommended in most of the GA literature.

Make sure to let me know if you get some interesting results!

Thanks for taking the time to answer all my questions, I'll be sure to let you know of my findings for my research project.

Mark

Hi Alex,

Just want to you let you know how things are going and to sneak in a couple more questions would help me out.

So far so good, things are working well, but alas, not well enough. My wee AI for my wee game seems to be avoiding the obstacles, but in relatively unusual ways: In the first run all tests converged to an AI that would spin around and thrust in the same direction, not really changing any state at all (it looks like summersaults in space!) – This conformed to my fitness function relatively well, so my second try penalized spinning and high velocity (both angular and transnational), and the 2nd run took the favour of bouncing itself off the least threatening target.. (in this case, a wall) multiple times until the simulation was over.

So it works yes, not the way I like it though.. :)

1) Most of my runs so far have converged relatively quickly; I fear that I’m hitting local maxima here. I would think that the whole concept of varying obstacles in different positions with different characteristics would lead to a very complex search space, one in which it be very difficult to find a good solution. I’m thinking of greatly increasing the population and minimizing the generations so it doesn’t take too long. What is your opinion on this?

2) On the same note – what is the selection scheme you use for your experiments? I use tournament selection, which weighs heavily on the concept of elitism; the best 50% of my population always make it to the next round. I wonder if this approach is doing more harm then good...

3) Another issue is the concept of Neural Network scaling. My NN consists of 6 inputs, 14 hidden and 2 outputs. I wonder if this is enough though. Most of past (unrelated) examples only had a single output node – I wonder if having 2 hidden layers would be more effective? Any thoughts on this?

Eagerly awaiting response...
Mark

Mark,

Thanks for keeping us up-to date, it's nice to see you putting it all into practice.

Ok, down to business.

1) I seriously doubt it's a local minima. I've experimented a lot with my model, and it seems a simple task to learn. In fact, when I improved the representation -- in the advanced tutorial, I could get random solutions to work well (1/8)! If you think your model is more complex to learn, then increase the population size a bit and let the GA run longer!

Btw, DON'T FORGET SYMMETRY REMOVAL! That's one of the key concepts of getting satisfactory results, and I'm quite pleased I came up with the idea ;)

Another observation, can your network turn left and right? If you use the standard unscaled sigmoid, then it won't give negative values!!

2) I use a random walk. My population is a 2D grid, and I move randomly from one point twice and pick the two best individuals encountered as parents. Thought I can't get good convergence on some problems, so I may change back to a steady state algorithm.

3) I think this definitely makes a big difference. In regression, you can complicate the search-space quite a bit by having two degrees of freedom. Hence my reason for locking the speed on full, and applying a breaking force instead. More hidden layers can give more complex functions with fewer nodes, but everything can be done with 2 layers (hidden,output). Try experimenting with different sizes; write a script that will do all the fitness testing over night, and compare the results.

Anyway, I personally think your fitness function that loop-holes, and the GA is taking advantage of them. The punishment for turning too fast and staying on the spot is a start, but there may be other things.

I wish things were simple for me. :)

1) The two outputs of the node range between 0 – 1, and I use a function to determine a “probability” in which the AI will do an action. The function looks like a steep parabola quickly levelling off at the top. (It’s an exponential actually) – the idea is this,: If the node returns a number less than 0.4, then there’s a good chance the ship will fire a “rotate left” event. If the number is greater than 0.6 then there’s a good chance if will fire a “rotate right” event. The slope levels off at 1 when < 0.2 and > 0.8, therefore the AI will definitely fire the respective event. Otherwise, no there is no action. This exact same approach is used for the 2nd node, only instead of rotate left and right, it’s thrust forwards and backwards.

One important thing to mention that unlike your output, where it’s “rotate in this direction by X degrees” with mine they are discrete values – one event only last for one cycle of the game. So a continuous rotation for the AI to pull a 180 would take a dozen or so (depending on the angular velocity of the AI) consecutive rotate events in the same direction to be able to successfully turn around.

2) Random walk? Interesting. Can you forward any links you may have concerning this selection approach? How do you represent your population exactly? What’s the X, and the Y in these cases?

3) Yep, I have a script handy for just those cases.. I was thinking of also splitting them up into two completely separate neural nets; one for rotation, one for speed – maybe even dumbing down to the point in which you had it initially, with a constant speed, and just attempting to manoeuvre around the obstacle course. Mind you, in my case when real physics are involved, some of those moving objects, when collided, may increase or decrease the velocity of the AI drastically, so I’d rarely end up with a constant speed.

I think your right with your suggestion concerning the fitness - I guess tweakage and experimentation are the only way around these things.

Mark

Mark: Have you tried your network on a much simpler task first before you tried obstacle avoidance? As Alex has mentioned ANNs seem to *enjoy* the obstacle avoidance task - its no big deal for them so you may have some overlooked bug in your code. (incorrect or missing biases is something that crops up a fair bit). Also selecting 50% of the population to go through is waaay too high. I'd recommend 2-5%. (I usually use a starting population of 50-60 for this type of task)

Alex: How do I change my password for this forum so I can have something I'll remember? ;0)

I'll tell you if you type something more suitable than "Re" in the subject every time ;)

Message Store > Account

http://ai-depot.com/Messages/Account.html

I really should add a login on the main page...

;0)

ta

fup,

That's always the first thing I check. :)

This neural network code I'm using (a class actually) has been used several times with a couple different problem instances.. all of them working flawlessly. So I'm sure it isn't my code.

I'm sure it's my fitness function - well, that, and probably the environment. In my first two batches of tests I didn't really randomize the environment to any extent - so possibly memorization is another issue of mine. This time the fighters and asteroids appear in different places on map, greatly varying the scenario every time.

We'll see how it goes. My next task will reducing the population transition rate. I think you're right on this account, 50% is too high. I'll tell you one thing, it works really well on a TSP problem. :)

Mark

Do you have a screen shot (or even a simple executable) for us to look at so we can get an idea of the environment your bot is in? It may help us come up with suggestions

Sorry for the slight time lapse there,

I handed in my project after pulling an all-nighter and for a while I didn't feel like looking at it again. :)

Well, the was almost a complete failure. Almost I say, because my 2nd last attempt actually proved some better results: I randomised the environment and with the optimal neural network, my wee AI actually moved to avoid a few bullets or two, but alas, only a few, then it just continued to fire it's thrusters until the sheer speed of the ship colliding with the asteroid blew him apart. Oh well. At least it worked for about 3 seconds. :)

I could send you an exec or a screenie, sure, I'd get your e-mail but there's a javascript error preventing me from seeing your profile off this msgboard. (<-- for Alex :)

As for future endevours, I believe I have another approach to attempting this NN AI - recording human data and movement and then using that as proper training data with a standard back propagation algorithm to train the NN.

Greetings Alex!

Long time no chat. Well - I'm at it again - the same experiment that I did last year (see messages above) I am attempting once again in another AI course. I'm wiser this time, and am determined to get this obstacle avoidance in a newtonian environment thing working properly.

The most significant change in my experiment so far has been the fact that I've changed my NN representation to be similar to yours - I've written a discrete AI algorithm using fundamental math to handle the manoeuvring in a newtonian environment; now my NN only needs to output the change in yaw, and everything else is handled automatically. I've had some promising results so far.

If you don't mind, I have some further questions concerning you're resentation of your neural net:

1) Clarification on inputs: In youre 2nd article you found the best structure was 6 inputs: The first being the last output of the NN, and the other 5 being the distance sensors, something to the effect of: 1) directly in front of you, 2+3) 5 degrees to the left/right, 4+5) 10 degrees to the left/right? Is this corrent? What type of distribution of the sensors did you use? Just what was directly in front you? A wider range such as 130 degree? Or a full 360?

2) For the distance sensor inputs, in your 3rd tutorial you mentioned you first used raw distance values, then you decided to clamp them down to a maximum of one. How did you go about this? Did you just scale down the distances so that the maximum would always be 1, or did you use some absolute value that you divided by?

3) What specifically is the output of your neural net, numerically? I'm assuming it would be +/- a value in radians, with a range of -2pi to 2pi. Did you find that in your experiments the NN ended up converging automatically to this value? Or did you have to clamp the number some way artificially?

Thanks for taking the time for responding to my further questions.

Mark

I'll make it short...

1) With five sensors, I used 120 degrees field of view, spread evenly. I now believe 3 is more than enough, and much more efficient. I assumed a 90 degree field of view (-45,0,45).

2) A maximum of one corresponds to four steps (a good value). 6/8 is also fine, but the bot tends to prevent collisions too much and not get into interesting spots. Hence 4.

3) Output is [-1,1] corresponding to a full 180 left turn, and right respectively. You'll need to punish big changes to get good results (otherwise the bot just spins around fast).

Hope that helps!

Hi everyone,

I talked on the forum about doing the obstacle avoidance module for a quake2 bot a long time ago and i'm doing it right now as a school project with the FEAR library. Only 1 month left till the end of the project.

Right now, i'm at the point where i have the NN setup for the bot's brain and a GA that is done on all the bots in a map.

1) First of all, you say that each bot has his own GA inside of it, how does this work ? What is the population then ? I have one GA that takes all the NN from each bot, makes a new population and puts back the new NN in the bot. I have like 7 bots and i'm worried that this is not enough to make it converge to a good solution. I do put at least one fresh randomised bot at each generation to have some diversity.

2)About symmetry removal, i understand that the behaviour should be symmetrical if we switch the obstacles in front of him in a symmetrical manner. However, i do not know how to implement it. The only thing i can think of is that for example, if i had 3 sensors, one in front and one on each side, i would only have 2 inputs into the NN, one for the centre sensor and the other one for the left or right one, depending on which ones had detected an obstacle. If it's the left one, take the output as it is and if it's the right one, flip the output to turn in the opposite direction. This method doesn't work if the bot detects an obstacle both right and left at the same time.

3) I'm using a sigmoid activation function for the neurons. My one output represents the direction in which the bot should turn. Since the sigmoid function outputs from [0,1], I offset it by -0.5 to have and output from [-0.5, 0.5], zero representing no turning. Should I offset all of my neuron by -0.5 or just the last one. By offsetting them all, if I have all my sensor inputs at 0 (meaning no obstacle), all the outputs from the neurons are zero, including the last one, which means no turning, which means the correct behaviour no matter what the weights are. Or should I leave them alone and let the weights evolve to the point where there will be no turning if they're no obstacle near ?

I'm somewhat tight on time so any improvements on the model and design before simulating and testing are done would be very helpful.

Thanks in advance

1) I just read your tutorial on making a GA class that pretty much answered my first question. Using that technique will solve my problem of having a small limit of bots in the game at the same time. I can have a few population going on at once too.

2) I searched the net and haven't found anything on it. Hopefully, i will find the answer to it soon.

3) After thinking about it, i don't think it's a good idea to play with the activation function that way because I could get a good fitness with completely bad weights. I think the best is to let the GA find the best weights.

2) I have three NN inputs still, but swap left and right distances if l<r (negate output too). This way, mostly left turns are learnt.

3) I use a bipolar sigmoid, which solves all those issues. Your way is fine too!

How's FEAR?

Thank you very much for the answers.

As for FEAR, i think it's great. The only thing at first was setting up the thing but i found my answers on the FEAR messageboard if you remember. That FEAR QUAKE 2 setting up guide you have can be hard to find. Maybe it's just me but i was looking for the link to it on the left menu when it was on the top menu which i didn't notice its presence after a few minutes of searching.

Once everything was setup, using the Example project made the brain and organs easy to understand and to use. SimulateWalk with the lines drawn in the games is very nicely done.

I'm doing the obstacle avoidance module with the NN & GA for a semester long project but for a lab in my AI class, me and some friends did the same module using fuzzy logic for the brain. It was extremely easy to plug it in the Think function and it worked nicely with fuzzy logic.

As for my own project, there's about 3 weeks left. I'll probably have questions along the way or stuff to share so I'll do it here.

Keep up the good work on the site and on FEAR.

I finished my project some time ago. I just wanted to recap some of the stuff here if anybody is interested.

I’m very satisfied with the end result. It worked pretty well. The best setup that I found was with 3 sensors, one in front and one on each side at a 30 degrees angle. The maximum distance of the sensors was 8 steps. The NN configuration was 3 inputs, 6 neurons in the hidden layer and 1 output.

I tried a few different setups such as 3 or 5 inputs, 3-to-15 neurons in the hidden layer, more than one hidden layer, 30-45 degrees for the side sensors, etc. The best one that I found was the setup describe in the previous paragraph.

One problem that I had was that I didn’t make it possible to write a script with the different setups and just run the GA for each setup. I could have tried more setups if it was easier. I didn’t implement that feature because I didn’t have the time.

The population of the GA was only 10 (starting with random weights). However, with 5 bots in the game, there were 5 populations going at once. Each bots was evaluated over 6 seconds at higher than normal walking speed. 10 bots * 6 seconds meant 1 minute per evolution. I noticed that 40 evolutions were enough, which meant 40 minutes for each setup. I only used 10 bots because 40 minutes per setup is pretty long and I didn’t want it to be longer if not necessary. It turned out that 10 per population were enough, which surprised me a little but I won’t complain.

For each setup, I picked the best bot and compared them to come up with what seemed to be the best of all.

That’s about all the essential that I can think of right now.

To finish off, I would like to thank you Alex for the site, the help through this message boards and for FEAR. FEAR is really great and easy to work with.

Oh yeah, big thanks to fup and his site at www.ai-junkie.com too. His tutorial on NN & GA helped me alot.

NT