Welcome to our Genetic Car!
The goal of this Software Design project is to create an intelligent car that will drive around a user-drawn track. We are using genetic algorithms to naturally evolve better and better cars through each generation.
The team is: Riley Chapman (@rileychapman), Josh Sapers (@jsapers), Paul Titchener (@ptitchener) and Sophie Li (@srli).
This site is will be used for deliverables. Some interesting links are:
Final Presentation
This section is first in case you simply want to know what we did with our project. Feel free to read through the write ups below at your own pace!
We put together a slideshow for our final presentation that goes in detail about our project and our progress. Take a look through it for a tl;dr of our project progress and final results.
We also recorded a video of our program in action, take a look!
Project Proposal
The primary focus of our project will be to create a genetic algorithm that causes the behaviors of a simulated car to evolve over time. The car will move around a track, but not be told either where it is around the track or how to move. Instead, it will know what direction driving forward will make it go in and how far away from a wall it is. Different iterations of the car will have different responses to these inputs. Over the course of many generations, these reactions will mutate and evolve until an optimal set of parameters has been determined. The project will be similar in some ways to the webapp BoxCar2D. We will not be overlapping with other courses or working with anyone from a different section. We do not anticipate needing an angel advisor.
At the minimum, we’d like our car to be able to teach itself how to drive around a hard coded track. Though this track will definitely be more complex than a circular ring, by using a hardcoded track we will limit additional complication. This will allow us to just test the genetic algorithm and then move on to designing the less fundamental parts of our project.
Our primary worry about this plan is how we will have the cars respond to their “sensor” variables and how we can mutate this behavior. We are reasonable confident that we can simulate the car, and create tracks, but are less confident about what the parameters are that will determine how the car responds to the sensor variables that we pass to it.
After we have finished our minimum deliverable we would like to introduce roadblocks and obstacles inside the track. These could include potholes and ramps, which the car would have to learn to manipulate to complete the course faster. An extension to this could be implementing physics in determining the health of each generation of our cart. For example, we could emulate the way ramps work in the real world. Depending on how the cart approaches the ramp, it could drastically improve or reduce it’s score.
A second stretch goal would be to implement user drawn tracks. We would invite the user to draw a track with his mouse and generate a track from the input. This introduces complexities with dealing with interpreting inputs from a wide variety of user who may not be drawing the track seriously.
Our last stretch goal would be turning our project into a web app. As none of us have experience with python web apps, we think additional and interesting challenge. This would require us to learn how to develop user interfaces and teach us how to debug a different type of system.
Our first step for this project will be to create a simulation of a car that is able to move and collide with walls that we hard code into place. Second, we will add a fitness function that determines how well a car has done. Third, we will edit the algorithm that drives the car so that it will respond to various inputs. Finally, to complete our initial goals, we will add the genetic algorithm that will select for the best inputs and incrementally improve the car over time.
Design Proposal
Currently, our design looks like this:
We’ll save the tracks as a list of rects, and use a rect as a car. Collision will be simply rect collisions. Sensors are in progress, and simply check for a rect collision on each pixel value between the car at the wall. The matrix controls the wheels of the car, allowing it to move forwards/backwards and left/right
We are still torn between whether we’d like to make this an educational or fun program. We’re definitely interested in pursuing genetic algorithms as a ML component to our project, but we’re not really sure how we’ll implement this. There are two possible frameworks we can pursue:
1. Educational program, focused on teaching users the differences between different AI algorithms
2. A fun program that lets the user watch the progression of a car as it learns to drive, this would be similar to boxcar2d
Benefits of an educational program would be that it would let us explore different algorithms ourselves, and we would learn a lot more in the progress on the front of machine learning. Additionally, this educational program would be much more useful to an average user than a fun-focused project. However, a downside would be that we would have to account for different kinds of ML, which would involve many bugs and introduce a lot of complexity in our code. Additionally, if we pursue many different kinds of machine learning, we may spread ourselves too thin and end up not doing any implementation well.
The benefits of a fun program would be that we would be able to focus more on the user and the presentation of our data. We were all really interested in using genetic algorithms, so a fun program will allow us to focus all our energy on making the genetic algorithm robust and the track drawing better as well. Though the program may not be as useful as an educational program, it would definitely allow us better refinement of a single idea. and make a good presentation.
We’ll probably end up going in the direction of a fun-focused program like boxcar2d. At our current energy and resources, we probably wouldn’t be able to pull off multiple implementations well enough to merit going down that path. We feel that by focusing all our energy on making a good genetic algorithm, we’ll end up with a solid product that we can be proud of.
We’ve divided development into sections, where each member of our team is focused in implementing something specific.
- Paul: Track-drawing, control of the car
- Josh and Riley: Matrix mutation and fitness, aka genetic algorithm
- Sophie: View, sensors
We’re using Model-View-Controller, and we’ve divided each section into its own folder. We have a main script that calls the init from the model, view, and controller. That way, each member can edit files in their own folder and we won’t have to worry about conflicts. Each member has their own git branch, and we’ll merge all our changes into a main branch. We have a weekly meeting, where members will discuss the changes to the code they have done, to make sure everyone is on the same page.
Design Refinement
Our current class diagram:
While we are still progressing forward with the goal of “fun” in mind, we’ve realized that the car requires much more stringent code than we expected. The previous model contained the drawn walls in lists and the sensors check for a rect collision at every pixel. However, it’s quite intensive to check each pixel value for each value in the list, and our sensors ran quite slowly. We’ve changes the walls into arrays, so sensor runtime is much lower now.
Additionally, we’ve added directional control to our car. The matrix now controls the left and right wheels of the car, so the car can now turn. This allows for more complex behavior. There is now a theta value associated to the car as well, which allows us to “attach” sensors to the front, left, and right sides of the car that move along with the car.
We’re beginning to see matrix evolution, but there are still some bugs that have to be ironed out. Particularly, the sensors often see right through the track, which greatly messes up the drive of the car. There is also a lot of wiggling as the car rapidly drives left to right, which slows down progress as well.
Reflection
At this point, we’ve completed development of all the algorithms and track elements. We’ve changed the way track drawing is done, so sensor errors with the wall appear much less. Additionally, we’ve changed control of our car from a linear relationship to a quadratic one, which allows for more complex behavior of the car in relation to the input of the sensor values. A more indepth summary of how exactly this occurs was shown in the powerpoint presentation above.
We’ve changed our program so that it now supports 15 cars instead of only 1. This change was made because of our design focus on the “fun” approach. By having an entire generation of cars shown at once, the user can “cheer” on his favorite car, and see the results from genetic evolution much quicker. By adding a graph, we can also visually show progress over time, in case the user doubts whether our model works or not. We’ve also changed the car from a rect to a sprite, which makes our representation of a “smart car” more believable.
Our original presentation:
Our final presentation:
We’ve kind of achieved our minimum deliverable of having a car learn to drive around a hard coded track. We never actually implemented the hard coded track, but dove right into user drawn tracks. The car can successfully drive around these tracks. Unfortunately, we never got around to our many reach goals. We never implemented a web app and we never implemented obstacles. However, we did fix the reach goal of implementing drawn tracks from the very beginning, and got a really cool UI for presenting our work too. Dividing the work was a really good idea, since it made more complex goals easier to achieve. Though there were difficulties with merging branches, with different code, it was still pretty smooth sailing.
It was a great idea to implement 15 cars at once. This really focused on the user-fun part of our project, and made our program really fun to watch. Adding the a “raceboard” for all of the cars was a great idea too, since it made it easier for a user to cheer for a certain car. We found that making each car distinguishable really helped get the user interested in the progress all the cars were making. Next time, we want to include more elements for user-interaction, and probably make a webapp. Perhaps we might want to use Tkinter for prettier menus as well.
Although our division of labor was good throughout the project, our use of version control greatly improved as the project progressed. Originally, with only a main branch, editing files was a tricky logistical task. Then we figured out git branching. From there, the division of adding new features and tracking down bugs went smoothly. Each team member was able to effectively work independently, and integration of everything went well.
One of our most persistent bugs had to do with the sensors in the simulation of the car. For the time that we were showing lines to represent the sensors it was very apparent that occasionally, the sensors would see through the walls of the track. This would cause the cars to turn instant 180’s and otherwise wrecked havoc on the control algorithm. This bug manifested itself somewhere in the part of the code where the sensors worked out where the walls where, and also in the part of the code that kept track of where the walls were. We had a curious situation in our simulation in that our program knew everything about the position of the track, but the part of it that had to control the car had to extrapolate the position of the track using its sensors. This design choice was made so that the control algorithm that evolved from our program could, in theory, be placed on an actual robot.