CS81 Adaptive Robotics¶
Lab 3: Evolving Neural Network Controllers¶
Due next Monday before noon¶
Lab goals¶
- Understand how to use NEAT to evolve neural networks
- Use NEAT to evolve a robot controller to solve a coverage task
- Experiment with which sensors allow the robot to achieve the best coverage
Getting started¶
Use the github server to get the starting point Jupyter notebooks for this lab.
Remember to do the following command in your terminal window to activate the virtual environment for this class: source /usr/swat/bin/CS81env
Introduction¶
In this lab you will experiment with an evolutionary computation method called NEAT (Neuro Evolution of Augmenting Topologies) developed by Kenneth O. Stanley. NEAT operates on both the weights and the structure of a neural network, allowing connections and nodes to be added as potential mutations.
First you will evolve solutions to XOR. Open the EvolveXOR notebook.
Once you understand the basic mechanisms of NEAT, then you will evolve neural network controllers to produce motions that maximize coverage of the world. We will define coverage by dividing the world into a grid of possible locations. The fitness will be based on the percentage of grid locations visited by the robot over the course of a trial where it gets to move for many steps while being controlled by an evolved neural network.
For example, the image below shows the best performing network from one run of NEAT. The purple line shows the trail of the robot. It begins in the center facing North, and spirals outward until it gets stuck in the bottom left corner.
Note that each run of NEAT will be different, and the types of sensors you provide will have a big effect on the types of behaviors that emerge.
from jyro.simulator import *
from math import pi, floor
from random import random
from neat3 import config, population, chromosome, genome, visualize
from neat3.nn import nn_pure as nn
import pickle
import numpy as np
Calculating Coverage¶
The following Grid class is used to create a fitness function for calculating how well a robot's motion covers a given environment. To construct a grid, you must pass in the desired grid width and the environment's width. Make sure you understand this class and its methods.
class Grid(object):
"""This class creates a grid of locations on top of a simulated world
to monitor how much of the world has been visited. Each grid location
is initally set to 0 to indicate that it is unvisited, and is updated
to 1, once it has been visited."""
def __init__(self, grid_width, world_width):
self.grid_width = grid_width
self.world_width = world_width
self.grid = []
for i in range(self.grid_width):
self.grid.append([0] * self.grid_width)
def show(self):
"""Print a representation of the grid."""
for i in range(self.grid_width):
for j in range(self.grid_width):
print("%2d" % self.grid[i][j], end=" ")
print()
print()
def update(self, x, y):
"""In the simulator, the origin is at the bottom left corner.
Adjust the row to match this configuration. Set the appropriate
grid location to 1."""
size = self.world_width/self.grid_width
col = floor(x/size)
# adjust the row so that it matches the simulator
row = self.grid_width - 1 - floor(y/size)
self.grid[row][col] = 1
def analyze_visits(self):
"""Calculate the percentage of visited cells in the grid."""
cells_visited = 0
for i in range(self.grid_width):
for j in range(self.grid_width):
if self.grid[i][j] > 0:
cells_visited += 1
percent_visited = cells_visited/self.grid_width**2
return percent_visited
Testing Coverage¶
Let's create a world and robot. We'll allow the robot to move around randomly. As it moves, we can record the (x, y) locations that it visits. Test the grid several times. Try different grid sizes, such as 10 or 20.
def make_world(physics):
physics.addBox(0, 0, 4, 4, fill="white", wallcolor="black")
def make_robot():
robot = Pioneer("Pioneer", 2, 2, 0) #paremeters are x, y, heading (in radians)
robot.addDevice(Pioneer16Sonars())
return robot
def random_act():
return random()*2-1, random()*2-1
def test_grid():
robot = make_robot()
vsim = VSimulator(robot, make_world)
robot.useTrail = True
robot.display['trail'] = 1
grid = Grid(15, 4)
action = random_act()
for i in range(100):
vsim.step()
if i%20 == 0:
action = random_act()
robot.move(*action)
x, y, a = robot.getPose()
grid.update(x, y)
grid.show()
percent = grid.analyze_visits()
print("Percent visited", percent)
test_grid()
Configuring NEAT¶
Set key parameters of the NEAT experiments here.
%%file configCoverage
#--- parameters for the robot experiment ---#
[phenotype]
input_nodes = 3
output_nodes = 2
max_weight = 30
min_weight = -30
feedforward = 1
nn_activation = tanh
hidden_nodes = 0
weight_stdev = 0.9
[genetic]
pop_size = 30
max_fitness_threshold = 1
# Human reasoning
prob_addconn = 0.1
prob_addnode = 0.05
prob_mutatebias = 0.2
bias_mutation_power = 0.5
prob_mutate_weight = 0.9
weight_mutation_power = 1.5
prob_togglelink = 0.01
elitism = 1
[genotype compatibility]
compatibility_threshold = 3.0
compatibility_change = 0.0
excess_coeficient = 1.0
disjoint_coeficient = 1.0
weight_coeficient = 0.4
[species]
species_size = 10
survival_threshold = 0.2
old_threshold = 30
youth_threshold = 10
old_penalty = 0.2
youth_boost = 1.2
max_stagnation = 15
Sensor inputs for achieving coverage¶
What are the best sensors for allowing NEAT to find good coverage solutions? Here are some options to consider:
- all or some subset of the scaled sonars
- stall
- scaled timer (either counting up or counting down)
- bias (some constant value)
- current coverage
For example, the following function uses just three sensors: the scaled minimum of the front sonar sensors, the stall sensor, and a count down timer. The count down timer gives the robot a sense of how long a trial will last. A count down timer starts at 1.0 and decreases linearly to 0.0. A count up timer works in the reverse direction. It starts at 0.0 and increases linearly to 1.0.
Remember that all inputs and targets to a neural network should be scaled to match the range of the activation function. In our case, this will be tanh which has a range of [-1,1].
def get_sensors(robot, steps, i):
sonars = robot["sonar"].getData()
scaled = [min(v/5.0, 1.0) for v in sonars]
timer_down = (steps-i)/steps
inputs = [min(scaled[3:5]), robot.stall, timer_down]
return inputs
Fitness¶
We will tie a network's fitness directly to the percent of grid locations a robot visits. Notice that on each time step, the eval_individual function is running a non-visual simulatator and uses the get_sensors function to determine the inputs to the networks.
def eval_individual(brain, robot, sim, show_trail=False, steps=1000):
robot.setPose(2, 2, 0)
if show_trail:
robot.useTrail = True
robot.trail = []
robot.display['trail'] = 1
grid = Grid(15, 4)
for i in range(steps):
brain.flush()
inputs = get_sensors(robot, steps, i)
output = brain.sactivate(inputs)
robot.move(*output)
x, y, a = robot.getPose()
grid.update(x, y)
sim.step()
return grid.analyze_visits()
def eval_population(population):
print("Evaluating chromo", end=" ")
for i in range(len(population)):
print(i, end=" ")
chromo = population[i]
brain = nn.create_ffphenotype(chromo)
chromo.fitness = eval_individual(brain, robot, sim)
print()
Evolution¶
Note that evolving brains for robots will be a much slower process than evolving solutions to XOR. Here we need to create the network and allow it to control the robot for an extended period of time in the simulator in order to determine it's fitness. In order for you to see quick results, I have initially set the number of generations to 5, however, you should increase this for your experiments.
Remember to look at the files avg_fitness.svg and speciation.svg after evolution is complete. You'll need to use a linux command such as eog in a terminal window to view them.
def evolve(n):
config.load('configCoverage')
chromosome.node_gene_type = genome.NodeGene
# Tell NEAT that we want to use the above function to evaluate fitness
population.Population.evaluate = eval_population
# Create a population (the size is defined in the configuration file)
pop = population.Population()
# Run NEAT's genetic algorithm for at most 30 epochs
# It will stop if fitness surpasses the max_fitness_threshold in config file
pop.epoch(n, report=True, save_best=True, name="Coverage")
# Plots the evolution of the best/average fitness
visualize.plot_stats(pop.stats, name="Coverage_")
# Visualizes speciation
visualize.plot_species(pop.species_log, name="Coverage_")
robot = make_robot()
sim = Simulator(robot, make_world)
evolve(5)
def eval_best(chromo_file):
config.load('configCoverage')
chromosome.node_gene_type = genome.NodeGene
fp = open(chromo_file, "rb")
chromo = pickle.load(fp)
print(chromo)
fp.close()
visualize.draw_net(chromo, "_" + chromo_file)
brain = nn.create_ffphenotype(chromo)
fitness = eval_individual(brain, robot, sim, show_trail=True)
canvas = Canvas((400,400))
sim.physics.draw(canvas)
canvas.save("trail_" + chromo_file + ".svg")
print("fitness", fitness)
Analysis¶
Try evaluating the best chromosomes found at each generation of one of your evolutionary runs. Describe how the behavior improved from one generation to the next. Remember to look at the phenotype images that are also created when you evaluate the best chromosomes. These images show the topologies of the evolved networks. Describe whether the network topology changed from one generation to the next.
eval_best("Coverage_best_chromo_4")
Experiments¶
When using NEAT, many parameter settings must be specified and it isn't always clear how best to make these choices. Each of the choices made in the code above can affect the types of behavior that will be evolved. Below are just some of the parameter settings that you could explore.
What inputs should be provided? In the original code only three were given: the normalized minimum of front sonar sensors, the stall sensor, and a count down timer. Try other combinations of inputs.
How should fitness be measured? In the original code we used a grid size of 15 and the percent visited as the fitness. How would things change if we made the grid size bigger or smaller? Is there a better method of evaluating coverage rather than percent visited?
How should the NEAT parameters be set? Should the probability of adding nodes and connections be changed? Should more or less speciation be encouraged? Should we use bigger populations and run for more generations?
Run a series of 10 experiments using the original set up that I provided. Each evolution should be for at least 10 generations. Report on the best coverage achieved in each run, as well as the complexity of the best networks in terms of the number of nodes and connections in the network topology. Note that the evolution process is not guaranteed to always lead to ever increasing fitness levels. Sometimes an earlier generation can find a higher performing solution than a later generation.
Modify the parameters in one of the ways suggested above. Run a series of 10 more experiments. Compare these results to original results. Try to find a set of parameters that outperforms the ones I provided.
Results¶
Report on the results of your experiments here.
Use git to commit, add, and push¶
Be sure to save this notebook to the repository.