An idea grew in my head recently for a proof of concept project that would be an excellent example of evolutionary programming and that evolved concept would lead to an equally interesting robotics project. I think this idea would make for a great senior thesis for a comp. sci., or engineering major.
The basic concept is having a robot draw a picture. I know this has been done and it can be demonstrated in higher quality using a simple camera and printer (or a Polaroid for that matter) but I do not know of it being accomplished in this way. The steps of the basic plan are:
- Take a picture
- Evolve a set of marker or brush strokes that resemble that picture
- Have a robot execute these instructions to draw/paint the picture out
Now we will break down the steps in more detail.
Take a picture.
Simple enough, just use any camera and snap a photo saving it to a readable digital format. Already digitized photos are also useful but for the biggest fun factor there should be a camera, such as a webcam, that the system/robot can trigger and immediately take the image from to begin working.
Evolve a set of marker or brush strokes that resemble that picture.
This is where things get interesting. If you are not familiar with evolutionary programming read the section below or skip it if this is familiar to you.
Evolutionary Programming Explained
There are three steps to an evolutionary program. First you must represent a potential solution to a problem in a “genetic” manner. Then you must develop a “fitness test” that determines how well any potential solution solves the problem. Finally you generate random solutions and evolve them until suitably good solutions are found. Lets look at these in more detail.
Representing a potential solution to a problem in a “genetic” manner: Hopefully this would mean something simple but most importantly it means a format that is open to expressing an arbitrarily high number of possibilities. This expressed solution should be able to combine with any other solution and it should also be subject to mutations. Mutations take the form of random changes in data. This means that it should be possible to swap some values and corrupt small pieces of the data without causing a fatal overall program crash.
Develop a “fitness test” that determines how well any potential solution solves the problem: This is the point at which we must make sure that no possible version of the solution can cause a crash. No matter what is passed in if it is valid in the format of the solution then it should be given a rating. This rating is fuzzy which is to say it is not a pass or fail rating but a number representing how well the problem was solved. The norm for such value ratings tends to be a floating point number that’s value ranges from 0.0 (complete failure) to 1.0 (perfect success) but it is rare to apply evolutionary programming to a problem that perfect solutions can be predicted for so it is not uncommon to have an arbitrary scale. That means the rating could go up indefinitely. Your first rating may be 0.235 then 1.024 then 3.457 and still there could exist a solution that is rated 12,375,000. The important part is that the ratings be able to compare to each other. You should be able to test any size group of solutions and identify the best, worst, and the top 20 percent (or any other percent) of the group.
Generate random solutions and evolve them until suitably good solutions are found: If you model your data well then generating random potential solutions should be easy, fill all fields with a random value that is in its valid range. You should generate a large number of solutions. The exact number will depend on your computing resources and time constraints but the larger sample you have the better potential for results. The evolving process takes some thought but is not very complicated. Test all of the solutions to find the best ones. Lets assume we use the top 20%. Next create the second set of potential solutions from these most fit members. Combine parts of the data from two different solutions into a new one to make a child, make as many children as you need from the top performers to fill your second set. It is common to include copies of the parents as well since it is possible that their offspring may not be as good as the original. Finally introduce a small amount of random mutation. This may be swapping some values in a solutions data set or changing a value at random somewhere but it should only be done to a small portion of your data (lets say 1% or less). This process is then repeated until an adequately good solution is found or until the rate of change becomes too small over several generations.
Data model
In the case of a robot drawn image the data model for the potential solution can be rather simple. For example this string could represent one stroke:
1:-12.7:3:-10.5:6.2
This means use color number 1 to draw a line from (-12.7, 3) to (-10.5, 6.2) with the generic form of:
Color : X1 : Y1 : X2 : Y2
For more complex and potentially natural shapes you may want to model a curve instead of a line which is just as easy using a third control point in the form:
1:-12.7:3:-13:3.3:-10.5:6.2
Color : X1 : Y1 : Cx : Cy : X2 : Y2
If at this point you are getting confused don’t beat yourself up about it. This can be a lot of information to take in at one time and it may be good to revisit the next half of the paper after a break or even another day. Moving on lets think of how to represent more than one stroke. With the formatting assumptions we already have it is simpler than you might think. Just make the string longer.
1:-12.7:3:-13:3.3:-10.5:6.2:3:2.1:22:14:12.022:-16.8:6.2:7:4.55:8:19.2:8.3:12:-8.1
That string represents 3 curved strokes with color information for each and while it is definitely hard to read it is very well suited to our purposes. It would not be wrong to use an array of individual strokes as your data and doing that will make it easier for you to write your test and the evolving code but the advantage to one large string is its similarity to real genetic coding. Genes are in fact far simpler than this data but they represent a huge amount of information and that simplicity means that in an accident (mutation) something completely unexpected can happen (say a color value is swapped with a coordinate). This is very very good since the whole reason for evolving a solution to a problem is that you don’t know the solution and you want to explore as many possibilities as you can without the constraint of your own assumptions.
Fitness test
The test of how closely your robot drawing matches the image taken should be performed with existing code. Image matching has been well developed by many people for a great number of reasons and you will have to research what solution best meets your budget, processing power, and quality requirements. Before you can match images you need to draw a sample of the one created by your solution and for this I also recommend some type of pre-built graphics library that can render primitives and generate an image file. This choice will reflect the same considerations taken into account for your image matching software.
Before we consider the fitness test done lets consider one more piece of information. You don’t want the robot to take 4 days to draw the picture right? So another aspect of the fitness test could be the total number of strokes required to complete the drawing. This will have to be weighed against how closely the images match to reach a happy medium. You could, for example, subtract time taken from the score generated by the comparison.
Evolving the drawing
With the test and the data model well defined the process of evolving the drawing is very straightforward. Combining two drawings could mean a few things but lets stick to the simple case of half of the strokes coming from parent 1 and half of the strokes coming from parent 2. You could do a lot of different things here like averaging coordinates in close proximity but the more structure your algorithm imposes the less benefit you stand to reap from the evolution process.
Mutations can take two forms. One would be a random swap of two numbers or of two whole strokes. The other would be changing a single number to a random value.
Another thing to consider in our case is that a drawing can have different numbers of total strokes so unlike in nature we may want to try things like using all strokes from both parents, less than half of both, or a mutation that cuts out as much as half of the total strokes. Use these with some probability controls and you should get more interesting results.
Have a robot execute these instructions to draw/paint the picture out
The robotics portion has its own set of problems. While it would be easiest to deliver the vector information to a plotter and let it draw perfect lines a more impressive robot is one that uses an articulated arm to move brushes or markers over a paper or even canvas. Robotic arms are not uncommon, here is a simple one for around 350 to 500 dollars. I would probably elect to use a Lego mindstorms robotics kit to build one. The interesting part comes when you try to replicate the human ability to draw on a flat surface using a design that naturally moves in curved arcs.
Did you ever wonder what all that trigonometry was good for? Well this is it. I am not going to go into full detail here because of the needed time in research to solve the problem but the process is straightforward. First come the problems:
- How do I translate the coordinates from a 2 dimensional plane into a set of angle values for each of my motors (expect to use at least 3)
- How do I find the rate of change for each motor to produce a line on the 2d surface smoothly without the writing utensil lifting from the paper
- How can the robotic arm find and predictably grasp the drawing utensils
I am sure that there is a great deal of already made arm control software that accomplishes these tasks but the problems are interesting none the less.
That’s it for now. I may revise this later on after re-reading it but for now I’m too tired to add any more. If anything is unclear, poorly organized, or incorrect please just leave a comment and I will update to the best of my abilities otherwise I’d love to hear some feedback on the idea. Especially if someone already did it! 🙂