In this tutorial, we are going to make a walking or running AI from scratch in JavaScript, with matter.js as the physics engine. If you don't plan on using JavaScript or matter.js, you can certainly follow along, but you will have to rewrite the code. If you would like to watch a video about this, go here. The final project can be seen here, and the GitHub repository is here.
As a disclaimer, this is not an end-to-end tutorial. I explain the most difficult parts, but it is up to you to do the parameter-fiddling, graphics, and general structure.
What We Will Cover:
- Making the Robot
- The Machine Learning
- Getting the inputs
- Running the neural network
- Drawing the Robot
- Displaying Its (Currently Random) Gait
- The Genetic Algorithm
- How to Rank the Robots
- Which Robots Should Reproduce, and How Many?
- The Reproduction
- Parameters to Fiddle With
- My Final Result
Making the Robot
Over half of the source code is just making the robots exist. If you haven't used matter.js before, you can download it here. You can read the whole documentation here, but the functions we will need are:
//set up
const {Engine,Composite,Render,World,Bodies,Body,Detector,Constraint,Runner} = Matter;
var engine = Engine.create();
var runner = Runner.create();
// creates a static rectangle (can't move)
var ground = Bodies.rectangle(x, y, width, height, {isStatic: true, collisionFilter: {
category: 1
}});
//creates a rectangle that can be moved
Bodies.rectangle(x, y, width, height, paramsObject);
//creates a circle that can be moved
Bodies.circle(x, y, radius, paramsObject);
//draws a rectangle/circle/polygon in the HTML canvas
ctx.beginPath();
ctx.moveTo(verts[0].x, verts[0].y)// go to the first vertex
for (var i = 1; i < verts.length; i++) {
ctx.lineTo(verts[i].x, verts[i].y); // draw each of the next verticies
}
ctx.lineTo(verts[0].x, verts[0].y); //go back to the first one
ctx.fill(); // fill it
ctx.stroke(); // add a border
//makes an object that won't intersect with anything
var paramsObject = {
collisionFilter: {
category: 2,
group: Body.nextGroup(false),
mask: 1
},
// other parameters such as friction, density, etc. here
}
//and then pass paramsObject into where you create the rectangle/circle
//add something to the world
World.add(engine.world, [list of things to add])
Since more than one robot will race at a time, we will create a class called Bob (the robots are named Bob), and a list called bobs which will store all of the Bobs.
var ground = Bodies.rectangle(600, 600, 1200, 100, {isStatic: true, collisionFilter: {category: 1}});
var bobs = [];
class Bob{
constructor(weights){
// Make all of the body parts here.
// I won't include the code to make the body parts because it's too long.
// Go to graphics.js in the source code if you want to copy exactly how I did it,
// but I would recommend designing the robot on your own.
// add all of the body parts to the world
World.add(engine.world, [
ground,
this.rightThigh,
this.leftThigh,
this.rightShin,
this.leftShin,
this.torso,
this.head,
this.arm,
this.leftTorsoToLeg,
this.rightKnee,
this.leftKnee,
this.rightTorsoToLeg,
this.sholder,
this.neck
]);
bobs.push(this); //add this to the list of bobs
}
draw(col){
//draws each limb in the color specified
appearRect(this.leftThigh.vertices, col);
appearRect(this.leftShin.vertices, col);
appearRect(this.rightThigh.vertices, col);
appearRect(this.rightShin.vertices, col);
appearRect(this.torso.vertices, col);
appearCirc(this.head, col);
appearRect(this.arm.vertices, col);
}
}
The appearRect and appearCirc functions draw the rectangles and circles (you can write the functions yourself). Now, every time you want to create a robot, use new Bob([list of weights]). When you want to draw all of the robots, just iterate through the list bobs and draw() each of them. To remove all of the robots, you need to use:
World.clear(engine.world);
Engine.clear(engine);
bobs = [];
The Machine Learning
For this project, I did not use tensorflow.js or any other machine learning library. Implementing a very simple neural network and Genetic Algorithm from scratch is surprisingly easy if you understand the theory behind it!
I started with the most simple neural network possible, and never actually ended up needing anything more complicated. This neural network has neither biases (the biases actually made it worse) nor hidden layers. All it does is take 7 inputs with information about where the robot is, multiplies them by the appropriate weights, and gives 4 outputs which describe where the robot should move in the future.
Getting the inputs
Just like any other machine learning project, we need to start with the data preprocessing. We generally want all of the inputs to be from 0-1, but this isn't strict. If there is a specific input that you think is 5 times as important, try making it range from 0-5 instead of from 0-1.
// obj is the robot to be moved
var inputs = [
obj.leftTorsoToLeg.angleA/Math.PI/2, //angle of left torso
obj.rightTorsoToLeg.angleA/Math.PI/2, //angle of right torso
obj.rightKnee.angleA/Math.PI/2, //angle of right knee
obj.leftKnee.angleA/Math.PI/2, //angle of left knee
obj.torso.angle/Math.PI/2, //angle of torso
1/(1+Math.E**(550-obj.leftShin.bounds.max.y)), //lowest point off the ground of the left shin
1/(1+Math.E**(550-obj.rightShin.bounds.max.y)) //lowest point off the ground of right shin
];
Let's explain what each of these inputs are. First, we will break down 1/(1+Math.E**(550-obj.something.bounds.max.y))). 550-obj.something.bounds.max.y is the distance from the limb's lowest point to the ground, and 1/(1+Math.E**x)) is a sigmoid. We include a sigmoid because the distance from the ground can be extremely large or extremely small, and we need to normalize it.
obj.leftTorsoToLeg.angleA/Math.PI/2 is the angle of the left hip. We divide by Math.PI/2 so that all of the angles range from 0 to 1 instead of from 0 to 2PI.
Running the neural network
var outputs = [0,0,0,0,0];
for (var i = 0; i < 35; i++) {
outputs[Math.floor(i/5)] += obj.weights[i] * inputs[i%7];
}
The % operator is the modulus, or the remainder when divided by 7. The code above is a shorter way of writing
var outputs = [0,0,0,0,0];
outputs[0] += obj.weights[0] * inputs[0];
outputs[0] += obj.weights[1] * inputs[1];
outputs[0] += obj.weights[2] * inputs[2];
outputs[0] += obj.weights[3] * inputs[3];
outputs[0] += obj.weights[4] * inputs[4];
outputs[0] += obj.weights[5] * inputs[5];
outputs[0] += obj.weights[6] * inputs[6];
outputs[1] += obj.weights[7] * inputs[0];
outputs[1] += obj.weights[8] * inputs[1];
outputs[1] += obj.weights[9] * inputs[2];
...
outputs[4] += obj.weights[28] * inputs[4];
outputs[4] += obj.weights[29] * inputs[5];
outputs[4] += obj.weights[30] * inputs[6];
Each of the outputs is the linear combination of the inputs and its weights. The first output uses weights 0-6, the 2nd uses 7-12, the 3rd uses 13-18, the 4th uses 19-24, and the 5th uses 25-30.
obj.weights is a list containing all of the weights for that specific robot. For example, the winning weights in my program look like:
[0.18834910252749903,-0.42210118210117537,-0.282405069062347,-0.18779796377809643,0.35392962793905547,0.08652163281465311,-0.1683227913757347,0.27437336159984244,-0.15736460024327373,0.14172118611462192,-0.4330814082625428,0.28958751579459086,-0.2359942212566043,0.3178187768335743,0.13653278898043975,-0.45054794905994267,-0.06280852816771779,-0.3340736301275634,-0.1783600329925001,0.17661413127755907,-0.4968709401087665,-0.04941657163272649,0.0806457051422557,-0.10155357399245674,0.107063353032232954,-0.4223661866478451,-0.2831760111970353,0.3557805746944544,0.25778944810578747,0.24074724355018923,0.47785061674252083,0.2546941475880225,-0.2816248228446361,0.0388214927192042,0.39670983755588035,-0.08301800688060372,-0.05630540145803672,-0.09999896706725496,-0.008475885592672955,0.039582396033190456]
The genetic algorithm is the part chooses these weights. Until we make that, obj.weights can just be completely random.
Moving the robot
Now, once we have the outputs, we have to actually move the robot. In matter.js, it looks like this:
// move the body parts with the outputs of the NN
Body.setAngularVelocity(obj.rightThigh,activation(outputs[0]));
Body.setAngularVelocity(obj.leftThigh,activation(outputs[1]));
Body.setAngularVelocity(obj.rightShin,activation(outputs[2]));
Body.setAngularVelocity(obj.leftShin,activation(outputs[3]));
Body.setAngularVelocity(obj.arm,activation(outputs[4]));
var activation = x=>Math.sin(x);
This code sets the angular velocity of each of the limbs to the neural network's output. The angular velocity is basically how much the limb is turning. You canalso have the neural network control the angles themselves, or the angles of the joints instead of limbs, etc.
For the activation function, I found that a sine wave worked best. You can use a different (more normal) activation function if you would like to as well.
Displaying Its (Currently Random) Gait
We will need to display this gait, even though it is currently terrible. I will not go over the actual code for the graphics part, but 4 things are executed every 30 milliseconds:
- moves the time in matter js forward 30 milliseconds.
- displays the background and then draws each of the robots (64 of them run at a time).
- moves each the robots based on their (currently random) neural networks.
- checks if any robots died, and whether or not it should start a new generation.
The Genetic Algorithm
When you run the neural network now, it obviously won't walk, because it's random!
So, we have to teach it to learn. To do this, we will us the most simple possible genetic algorithm: asexual reproduction. This is split into three parts: ranking the robots, choosing which robots to reproduce, and the actual reproduction.
How to rank the robots
Once a robot's head goes below the red line (70 pixels off the ground), it dies. When a robot dies, it cannot move anymore. Also, to speed up training time, all the robots die after 10 seconds. The robots are then ranked by distance traveled before dying. Once all of the robots have died, the current generation ends and a new generation starts. You can tweak the ranking system, or completely change it, if needed.
//obj is the robot currently being moved
if(obj.head.bounds.max.y > 480 || timePassed > 100){
//kill a robot.
//sets each body part static so the computer doesn't spend effort moving the dead body parts anymore
Body.setStatic(obj.rightThigh, true);
Body.setStatic(obj.leftThigh, true);
Body.setStatic(obj.rightShin, true);
Body.setStatic(obj.leftShin, true);
Body.setStatic(obj.torso, true);
Body.setStatic(obj.arm, true);
Body.setStatic(obj.head, true);
obj.distanceTraveled = closestPos(obj); // the closest position to the starting line
numberBotsDead++;
if(numberBotsDead == bobs.length){
endGeneration();
}
}
function closestPos(ob){
var limbs = [
ob.rightThigh.bounds.min.x, // the limb's lowest x position
ob.leftThigh.bounds.min.x,
ob.rightShin.bounds.min.x,
ob.leftShin.bounds.min.x,
ob.torso.bounds.min.x,
ob.arm.bounds.min.x,
ob.head.bounds.min.x,
];
return Math.min(...limbs); //the lowest of each limb's lowest x positions
}
Which Robots Should Reproduce, and How Many?
Now, we have to choose which robots to kill, save, and reproduce. First, we need to rank the robots based on distance traveled:
// bobs is the list of robots in the previous generation
var sorted = bobs.sort((a,b)=>{
return b.distanceTraveled - a.distanceTraveled;
});
Now the first element in sorted is the best robot, and the last element in sorted is the worst.
Next, we will add the variations. We can't just add 64 of the best robot because it would prematurely kill new ideas.
Suppose the robots already found a pretty good way of walking. Then, one robot discovers a radically different way of walking, but doesn't go as fast as the original way. If we don't kill this new idea immediately, the new way of walking might evolve into something much better than the old way.
Because of this, we will add:
- Variations of the top 7 placing weights.
- 10 new, randomly generated weights.
- The best 5 placing weights from the previous generation, to make sure it never gets worse.
Note that these numbers are completely arbitrary, so feel free to change them.
haveKids(sorted[0], 25); //have 25 kids from the best one
haveKids(sorted[1], 10); //have 10 kids from the next best
haveKids(sorted[2], 5); //etc.
haveKids(sorted[3], 5);
haveKids(sorted[4], 4);
haveKids(sorted[5], 3);
haveKids(sorted[6], 2);
// ad 10 completely random ones
for (var i = 0; i < 10; i++) {
var weights = [];
for (var j = 0; j < 35; j++) {
weights.push(rand());
}
new Bob(weights)
}
// in order to make sure it never gets worse, add back the best 5 from the previous generation
new Bob(sorted[4].weights);
new Bob(sorted[3].weights);
new Bob(sorted[2].weights);
new Bob(sorted[1].weights);
new Bob(sorted[0].weights);
The Reproduction
Here, we will actually define the function haveKids(). Each "kid" is just its parent (one parent, not two) with some random changes. I call the amount of change the creativity (it's not a scientific term). As the robot is training, I can change the amount of creativity with a slider input (that's part of the HTML).
In your HTML:
Creativity:
<input type="range" min="0.001" max="1" value="0.5" step="0.01" id="creativity">
// numKids is the second parameter passed into the function haveKids
for (var i = 0; i < numKids; i++) { // repeat this code the number of kids times
var newWeights = parent.weights.slice(); // when we change newWeights, we don't change the old weights.
for (var j = 0; j < newWeights.length; j++) {
if(Math.random() < 0.1){ // only change a weight 10% of the time
var creativity = document.getElementById("creativity").value;
newWeights[j] += (rand()**5)*creativity; //changes the new weight a little
}
}
var newBob = new Bob(newWeights);
}
function rand(){
return Math.random()-0.5;
}
I use rand()**5, or rand() to the 5th power because it works best that way for me. Feel free to just use rand() or rand()/100, because that might work better for you.
And does it walk?
It most likely won't walk on its first try. If you're lucky, the robots might scoot on their first try. The final, most time consuming step is to fiddle with every possible parameter until it does walk.
Just like a baby, mine went from scooting, to crawling, to jitter-walking, to swinging their legs around their heads, to walking (all babies go through a leg swinging phase, right?). It took me approximately two weeks to get mine to walk as well as the video at the top of this article.
Parameters to Fiddle With
Here are a bunch of things that you can fiddle with to make your robot better. Everyone will have to try different combinations of these things in order to get their robot to walk.
- If it is vibrate-walking, only let it move its limbs twice per second, instead of moving its limbs every time the screen is drawn (33 times a second for me).
- Try making a more complicated genetic algorithm such as NEAT (I didn't try this, so I don't know if it is actually helpful).
- Tinker with the physics. Try changing the friction, restitution, density, etc.
- Change the inputs given to the neural network. For example, give the positions of the limbs instead of giving the angles.
- Change what the neural network controls. For example, instead of controlling the angular velocity, maybe control the angle itself.
- Maybe add hidden layers to the neural network? This may or may not be helpful, I haven't tried it yet.
- Change the ranking system (currently just who goes furthest before dying). For example, you could rank them by speed, make the robots evade a death line that moves towards them, or give them a complicated fitness score that is a combination of everything.
My Final Result
If you would like to see my final result, go here! If you would like to watch a video about this, go here. If you want to see my other projects, go to kiraprograms.com. If you want to see my fully commented code, see the github repository:
i8sumPi
/
bob-the-walking-AI
A simple, yet effective, walking AI.
Bob the Walking AI
Bob was created using matter.js for the physics and a very simple neural network, with no hidden layers or biases. I did not use any Machine Learning libraries for this; I did it from scratch in JavaScript (see ml.js). This uses very simple evolution: Bobs die if their head goes below the red line, and the ones that move furthest may reproduce and evolve. Also, the activation function is a sine wave because it works best that way. Surprisingly, after hours of intense coding and tweaking, Bob actually learned how to run and skip (I call it running and skipping, it's not exact)! This project is of the most complex ones I have ever done, and I am honestly shocked that I got it working. However, I can't stop it from falling after around 4 steps. This is from a competition between me and n8progrmas…
Oldest comments (1)
Very nice implementation!