Coding Challenge #69.1: Evolutionary Steering Behaviors - Part 1

hello welcome to a coding challenge boy this one is a doozy it is five parts long until I know four parts long but there's like a little fifth part bonus and what it is it is an evolutionary system where I evolved steering agents to effectively eat food and avoid poison and the poison here is a Indic is signified by the red dots the food is the green nuts this system has been running for a little while you can see some of them are maybe better than others and avoiding the food at finding the food and so this is what I'm doing it is part of my series on genetic algorithms there's a lot of videos that precede this one if you want to go and watch those this is also part of Session two of a course called intelligence and learning so it's part of that which is basically the same playlist and I hope that when you get to the end of this you will make something creative from it and share that with me so that this coding challenge is about to start it's in four or five parts a little secret if all our parts aren't published check the description you might be able to find the next one this won't be relevant to most of you because most of you will be watching this in the future when they'll all be published okay goodbye I mean that goodbye I'm going to be right back if from the past in the future to you goodbye not goodbye okay here we are I am going to first before I begin coding kind of map out the ecosystem the scenario the architecture all the pieces of this puzzle that I'm going to slowly build over time to create this coding challenge so there is going to be a world that world is a two-dimensional canvas in that world there will be dots that represent food maybe I'll make those dots green and there will also be dots that represents poison plot poison right cool boy and those will be red okay so this is going to be the world then in the world there will be agents you would call them particles or boys or vehicles whatever you know ants creatures what everyone call them your thing I'm going to call them vehicles because these are built on top of my examples that build on top of Craig Reynolds examples that build on top of this book called vehicles long story and by britain berg italian neuroscientist Frankenberg okay um so these vehicles the idea is that they need to they're going to move throughout this space in order to survive they need to eat food they don't eat food slowly over time they're helpful to window so I need I'm going to have a vehicle object the vehicle object is going to have a little physics engine built into itself so it needs its position it needs its velocity it needs acceleration but it's also going to need a property called health and that property is going to slowly go down over time now if it should happen to eat the green dot its health will go up if it should happen to eat the red dot its help will go down and what I want to do is I want to use an evolutionary strategy so I'm going to release a lot of these and all of them are going to have different properties that control how they move around through the space and those properties I want to evolve those properties over time so that I eventually have an optimal strategy for gathering and feeding all the green food the quickest and avoiding all of the red food now this might remind you of some demonstrations that you might have seen using a neural network based learning system and there is a technique I mean this is this technique is not exclusive to neural network based systems but called reinforcement learning and reinforcement learning is like hey why don't you you know vehicle move around the space and if you eat some food I'm going to give you a reward if you eat some poison I'm going to give you the opposite of reward a consequence and eventually over time you'll learn to do the stuff that were you to food to that that's an interesting topic boy am I excited to at some point in the future maybe you're in the future and it already exists come back and do a follow-up video about that particular topic but this is not what I'm going to look at today I'm going to use a different approach and evolutionary approach and if you don't know what genetic algorithms are I might encourage you to go back and watch a bunch of videos where I introduced the concept so I'm going to use this idea of a genetic algorithm to release a whole bunch of these into the world see how they perform and allow them to the ones that do well to reproduce and live longer and hopefully over time we're going to see agents that evolved to being very good at eating multitude and voids in poison okay so that I think makes sense now what else do I need to cover here in terms of what we're designing ah so I'm going to need an array to keep track of all the food locations an array to keep track of all the poison locations and I'm going to need an array to keep track of all of the vehicle objects and then there's one other important piece here I mean there's more but one more thing that happens described here on the whiteboard I need a function to determine something called steering so this is where I would say to you that if you haven't encountered steering behaviors and the work of Craig Reynolds before I would reference you to a link in this video's description of some of my videos where I go through via this topic in more detail in particular an algorithm called seek so I'm going to describe to to you briefly here but the idea is that if I'm a vehicle and I'm moving in a particular direction and what I'm desire to do is seek a particular target what I was a technique the steering technique that I'm going to use a pioneered by Craig Reynolds involves creating something called a desired velocity so if all my dreams were to ever come true I would simply be moving at maximum speed in this direction but I happen to be moving at this speed in this direction which is wrong so very wrong so what I need is some sore error and the error being with steering force that's going to push me back in that and from velocity in the direction design the reason why I got to looking at neural networks and learning based systems so much this is very very similar to looking at the output of a machine learning system and it's error the error here being the difference between the guests what my current velocity is and like desired output my desired velocity so the steering force is defined as the desired velocity minus the current velocity and if I apply this force to this particular vehicle it will turn and start to see over time alternatives or to seek the target now why is this interesting so in the one hand we I could just say right here right now I know exactly what these vehicles should do they should seek all the green stuff and they should repel avoid all of the red stuff so their desired velocity for green should point in the direction of the target and their desired velocity for red stuff should point away from the target so this is obvious and in some sense what I'm doing here is I want to reproduce the revolutionary system and obvious result why is that interesting I don't know how these kids to try but my hope is that if you can watch me do this as a code you could probably come up with a much more creative scenario where there are a lot of different factors at play maybe there are predators maybe there's some type of system where they have to collaborate and be next to each other to do something so I'll try to come back and offer you some suggestions towards the end but I'm going to troduce try to reproduce I'm going to allow these vehicles to make arbitrary random choices as to how they should interact with green and red and over time see if I can evolve them towards them being attracted to green and repelled from red that's the overall explanation and back over here with my computer oh hi computer nice to be here with you so I got to talk to me is it some day maybe you will that you are also just this string I say that okay here we go Tonetta edit that out or don't edit oh it's in there it's in there okay I'm here with my computer and I'm gonna start writing some code now here's the thing I usually start these coding challenges from scratch but to move this one along and since I've done this in other coding challenges and videos before I'm going to start with a base example that implements that steering behavior just having one single vehicle seeking a particular target so if you like to watch these videos and follow along coding along then what I would do is first there's a link in this video's description to the code where it is right now so you can go and grab pause grab that code and then come back but I'll talk you through what some of the pieces are in the code and then I also have a video where I cover steering behaviors and how this code works completely separately but um so I'll link to all that if you want to go back and watch that stuff before you continue with me right now here in this video okay now I am a conductor conducting nothing would be nice if you I just did that music just started I would know and make me so happy this doesn't all this stuff doesn't me be open but it's open okay so what's going on in this particular example so this example comes from the nature of code book there is a vehicle object the vehicle has all three of those properties I talked about before it has an acceleration has velocity has a position this dot R is its size property and has a maximum speed and maximum force which control its ability to seek a particular target it has a standard physics algorithm that I cover into my other videos where the position the velocity alters the position the acceleration alters the velocity and then the key thing here is this seek algorithm so this is key to us in how we're going to build this coding challenge so this is where Craig Reynolds steering's force is calculated the desired velocity is that is the target location - my position the target location - my position that's the desired velocity with its magnitude set to be maximum speed you know I'm to make knowledge of how p5 dot vector works and how vectors work so that's also something that you might want to look at some other videos about it that's new to you and then that force is that's the steering force that force is limited to some maximum strength and then applied to the object into its acceleration so that's all of this is and we can see here in the main program that I create a target which is I could call this target really instead of Mouse that's wherever the mouse is and then I draw something whoops I draw something at that target and then I say hey vehicle seek that target and that's the result that we have here so what do I want to do now what I want to do right now is the whole thing I can do everything but I got to start somewhere so I think what would probably be most useful it's for me to try something where I simply add the food the food elements into the window and then I have this particular vehicle just seek the food so let's do that so what I'm going to do is I'm going to create a variable called food and it's going to be an array and I'm going to say for VAR I equals 0 I'm just going to say let's add 10 pieces of food a food push create vector now where so I'm going to use a vector 4 to store an XY coordinate for each piece of food now we're sure that food B there's lots of ways I could approach this how about I pick a random X and how about I pick random Y yeah you might be able to do something interesting where you like seed the food locations based on a pattern you know that what was that Plus on distribution thing that I did or maybe you like pick all the bright spots of an image and you see all the food is like a person space but anyway I'm just going to pick some random locations and then what I'm going to do is right here in my name program I'm going to iterate through all of the food and I'm going to say I draw a little ellipse where the food is so at each food elements X&Y and I said the food should be green so I'm going to say fill with a green color and then I'm gonna I don't know it's a no stroke I make it up stuff just making it up as I go here we go so look there's all the food that's good step one done now here's the big on itchy nose today YouTube comments are going to talk about it okay so it's still seeking this like silly target thing so where is it so I got I got to do something about that so so what do I want to do here what I would like to do is figure out a way for this vehicle to individual seek a piece of food eat it and move on so what I want to do is instead of a seek target I'm going to pass in this entire array okay so if I'm passing food into the seek function and I'm actually what I'm going to do is I'm going to you know what I'm going to do I'm going to make a separate function I'm going to call it vehicle eat food because I have an idea of how I still want to use that seek function with one target in the same way I have before so what I'm going to do is I'm going to write a new function I'm going to call it this eat equals function and I'm going to give it some I'm just going to give it the argument is some list some list of things that's supposed to eat and what I want to do right now is I want it to find whatever piece of food it happens to be closest to I think this will work for us so I need to have a record a record distance what's the one that it's currently close to so at the beginning the record would be infinity you can actually just write infinity in JavaScript and it's like infinity so now what I need to do is I need to go through every element in that list and I need to look at the location and actually I don't need a separate variable what I want is the distance the distance between this objects position and the food position sorry that this is a long line of code but you can see here I'm looking for the distance between this I'm a vehicle my positions X Y and that particular piece of foods X Y and if if that distance is less than the record then guess what we beat the world record now the world record is that distance and I want to have a variable called closed fist and I'm just going to set it equal to no right now and then the closest is that piece of food okay so the closest is that piece of food there might be some issues you know I'm going to do closest index I'm going to keep the index because I might need the index later if it eats that if it happens to actually eat that piece of food I want to maybe remove it so anyway I'm thinking about this so I want to know what's the closest one so now I've done this loop to say what's the closest one and then I'm just going to say this dot seek but the element in that array that is the closest and I call this closest index I'm just going to call it closest okay so look at this this is a function now and this is why I wanted to keep that seek function because what I want to do is just look for there's a lot of things I could be seeking and I could do some kind of weighted thing where I seek a whole bunch at the same time but I just want to find what's the closest one and I want to seek it so now if I run this I've got an error cannot read property X of undefined vehicle dot look slowly deployed line twenty nine food index o food list it's interesting it kind of sure to work by accident because food was a global variable but let's try that list on lengths I I need list ed food this position distance list would be easier oh that's a good thank you Alka for that I'm going to do that but first I have to fix oh it's not pause its position the name of the variable is position position position and I suppose Alki and the chat is pointing out that if I say var D equals this position dot distance food index I it's going to be a nice sure there's a distance function in the P vector class P vector so I should say class because I'm here in JavaScript land but on in the P vaccuum the p5 that's your object that gives me the distance between this vector and this vector ok let's try this again so we can see it's just seeking write on boy let me get rid of this apologies let me get rid of this unnecessary mouse target now which is just distracting so we can see a limit only refresh because that was a little weird it picked oh look at that it's seeking whatever it happens to be closest to which right now is this one it's going back and forth so what I the next thing I want to do again I'm engineering the correct answer and then I'm going to try to go back and evolve the correct answer so to speak you'll see you'll see I got an idea in my head it's going to work I hope ok so what I want to do is I want it to eat that piece and move on and find the next closest one so the next thing I should do is actually where where am i in the vehicle is I want to say hey interesting what's that record distance actually less than I don't like 5 pixels I'm going to pick that arbitrarily but then I'm going to try to do something a bit more thoughtful in a second if it was then what should I do I should actually just get rid of that piece of food I ate that piece of food so I could say food dot splice I comma 1 so what is that doing splice is a function that removes a knot I sorry no I hear closest splice is a function that removes an element from the array and I want to I want to remove that one that it was closest to if it the close if it was actually within a certain distance like it got close enough to eat it so if it licks it I want to remove it and so that's the one I want to splice what's this one-four that's how many elements I want to take out of the array so for some reason not in this scenario I wanted to remove that element and the one after it that I would put it to there so let's see how this goes come back find another one there we go oh come back find another one so now you can see it's kind of eating them one at a time now I'm going to just for the sake of argument lower the maximum speed increase the maximum force just to make it a little bit better so now we can see look at it so this is just a nice little simulation of it doing exactly what we want it to do wonderful well and then there's none left so I got a that's the thing we're going to have to deal with but I'll worry about that later so I'm almost ready for part two this is kind of like my part one there's going to be a multi-part series you're just watching let's add the poison real quick just to see how that works because it's going to we're going to we're going to get some weird behavior that I'm going to need to deal with so let's add the poison let's do exactly the same thing with except instead of food let's add a whole bunch elements to poison at a random then let's draw and again there could be a more elegant way of you know encapsulating this so I'm not duplicating all this code but let's draw all the poison let's draw the poison as a red color those of you who are designers will make something much more beautiful so let's just first see that I see that okay so now we've got we've got the red is there but it's and it's just eating the green because it's not seeking the red so now let's also say vehicle eat poison okay let's see what happens here Oh what happened okay I know the problem is this is an issue like I'm music losing global but point I reason why I put that argument there and don't want to use food here is I want a general function that can receive any array and kind of apply the same behavior to it so what I want to do is not I can't use food here it's specific I want this function to be useful for the food and the poison so I should just use list there so let me now refresh and I got another error I save everything okay we run this again now what's going on this is what I expected to happen it's kind of stuck the reason why it's stuck is it's attracted to both a piece of food and a piece of poison and it's getting kind of stuck so if this was its behavior and it's still getting that error oh let's do them one at a time ah food food a list boy I'm really really making a mistake everywhere is that going to fix it yes okay so now let's see it's kind of stuck here so now we need to deal with this so I'm going to move on this is going to be the end of part one and you can stop and try to figure this out so what do I need to do next well now's where I really need to start thinking about the weight for those particular forces maybe I want it to be more attracted to food than it is to point me lastly what I want it to be is attracted to food and repelled from poison but in order for me to do that how can I do that in a flexible way where it learns that and that's what I'm going to start in the next video what I want to do is add properties to this vehicle that control how strong the that seeks that steering force is relative to food and relative to poison and by strong that could be in the positive direction or in the negative direction and I'm going to add that to the next video and start to get ready to evolve these agents I'll see you in part two if you choose to come along on the train [Music]

Channel: The Coding Train

Views: 86,476

Rating: 4.9803562 out of 5

Keywords: JavaScript (Programming Language), programming, daniel shiffman, creative coding, coding challenge, tutorial, coding, challenges, coding train, the coding train, nature of code, artificial intelligence, live stream, itp, itp nyu, neural network, intelligence creative coding, intelligence and learning, genetic algorithm, steering behavior, autonomous agent, evolution code, p5.js, evolution steering behaviors, evolution steering agents, evolution nature of code

Id: flxOkx0yLrY

Length: 23min 58sec (1438 seconds)

Published: Tue Apr 18 2017

Reddit Comments

[u/tehnod]

Found a minor bug in the code on github. If you let the thing run for just a couple of minutes all of your vehicles will die off and the canvas fills with food and poison. This and another issue (vehicles are allowed to occupy the same space.) may be fixed in later code though. I haven't been able to watch the full livestream yet. I did tweet /u/shiffman about the issue though.

edit- I was able to resolve the problem of all the vehicles dying by simply increasing the amount of food that appeared. A more elegant solution might be to tell the program that if the number of vehicles reaches zero it should start creating vehicles again.

edit again- I just fixed a problem that didn't exist. Somehow, I missed the mouseDrag bit to create new vehicles.