The Genetic Lander program was developed as an experiment to view the practicality of using an artificial intelligence technique known as Genetic Programming to develop a hypothetical lunar lander controller. By itself, this lunar lander simulator is to simple to be of any use since the physics have been so pruned, but the fact that it is a simple environment makes it a great test platform for learning algorithms. This applet serves more as a research tool than as a utility for developing a device to be used in the real world.
The applet tries to evolve a controller that will land the lunar lander on the blue landing platform. The applet starts automatically as soon as it is loaded. Genetic Lander consists of two main parts. In the background, Genetic Lander is constantly evolving new populations from an initial set of random programs. The display portion of the applet shows the best performing expression from the current generation in action.
The lunar lander is represented by a red square. This hypothetical lander is capable of thrusting from any direction underneath itself. A black line coming from the center of the craft represents the thrust.
The simulation can end in one of four ways before automatically
restarting with the most current expression. These outcomes are dictated
by the fact that the craft can't safely land if its vertical velocity exceeds
2.0 units/second or its horizontal velocity exceeds 0.8 units/second:
| Crash | the craft hit the ground exceeding the maximum vertical or horizontal velocity |
| Safe Landing | the craft hit the ground at safe speeds, but it missed the mark |
| Successful Landing | the craft landed on the landing pad at safe speeds |
| Out of Fuel | the craft ran out of fuel before touching the ground |
What is Genetic Programming?
Genetic Programming is a way to get the computer to simulate learning by evolving a solution to the given problem, in this case a lunar lander. Genetic programming was inspired by natural selection. The main idea behind it is that the computer starts with an initial population of randomly generated mini programs, 100 in this case, and by recombining and saving the good programs and removing the bad ones, the overall population of mini programs will gradually improve. Theoretically, good programs are composed of good building blocks and these building blocks can be rearranged into better programs. The mini programs, or expressions, are written in a language very similar to the programming language LISP. A math function such as:
3x + 2ywould be written as:
( add ( mul 3 x ) ( mul 2 y ))in LISP. The main advantage is that programs written this way can be easily stored and visualized as a tree. The advantage of having a set of program trees is that it easier for the swapping of portions of the program. To combine two programs from a population is as simple as grabbing a sub-tree of one and inserting into a spot in another program tree. In this way, the expressions will always remain syntactically correct. Whether they will always perform well is another matter.
Deciding which expressions to keep, recombine, or removed is the responsibility of the fitness function. The fitness function scores each expression on the basis of performance. The fitness function in Genetic Lander runs in the background giving each expression in the population 5 chances to land correctly. Some factors that determine score are:
Each expression has available to is a few basic math operations,
a conditional, and some environmental variables. The number of available
elements that expressions could be composed of was kept small to reduce
the solution space and also to prevent a single operator that does too
much. Add, subtract, multiply, divide, cosine, sine, inverse cosine, and
inverse sine are include, as well as a branching conditional "if less than
zero branch one way else branch the other way." The following environmental
variables are available to expressions:
| xVelocity | the current horizontal velocity of the craft - positive is to the right |
| yVelocity | the current vertical velocity of the craft - positive is down |
| directDistance | the distance from the center of the craft to the center of the landing pad |
| directAngle | the angle, in radians, from the craft to the landing pad - straight down is zero |
The output of the expression determines at which angle the lunar lander will shoot out the thrust. Anything returned that is less than negative 5 or greater than positive 5 means no action will be performed by the lander. The lander will simply accelerate downwards in responce to gravity. Anything between -5 and 5 will be mapped into a thrust between 90 degrees to the left and 90 degrees to the right.
Using Genetic Lander
The applet is composed of two parts: the "working area" on the left and the statistics on the right. The working area is composed of two pages: the Lander Display page and the Controller Update page. The tabs at the bottom of this area is used to switch between the two.
Lander Display Page
The main purpose of the Lander Display is to show the current best expression in action. The current best expression is updated only when the lander lands or crashes not while the craft is still in the air. Clicking anywhere on the Lander Display page will start the lander at that location with full fuel.
Controller Update Page
The Controller Update page is where the user can interact with the evolution
process. The expression in the text area shows the controller for the current
lander being run. The user can modify this expression, or a whole new expression
can be entered. WARNING: there is no real error checking. An invalid expression
will just not be used.
| Test Entered Expression | sets the expression entered in the text box to the current expression on display |
| Add to Population | adds the expression entered into the actual evolving population and also displays it |
| Get Current Best | sets the best from the evolution process to the current expression on display |
| Auto Update | if this flag is checked, then when the lander lands or crashes the current expression will be updated with a newer expression |
Lander Statistics
The lander statistics shows the performance of the expression
currently being shown on the Lander Display page. The coordinate (0,0)
is the upper left corner of the screen.
| Position | the current position of the lander |
| Velocity | the current velocity of the lander |
| Direct Angle | the angle between the lander and the landing pad |
| Direct Distance | the distance between the lander and the landing pad |
| Fuel | the remaining fuel |
| Time | the time elapsed since the current expression started running |
| Now Showing | tells from what generation the current lander controller came from |
Evolution Statistics
The evolution statistics shows the performance of the
population being evolved in the background.
| Generation | the current generation number |
| Max Fitness | the average fitness of the best performing expression |
| Average Fitness | the average fitness of all the trials of all the expressions in this generation |
Miscellaneous
| New Population | restarts the population of randomly created expressions - may take a couple seconds to process |
| Speed | sets the Lander Display page speed - 0 is the fastest. by using large numbers, more processor time is given to the expressions being evolved in the background |
Example Expressions:
Since the process of evolving a controller is subject
to randomness, there are times when nothing will evolve that correctly
lands on the landing pad. The evolution of the population may have become
stagnant because of a few semi-good performers saturated the whole population.
In this case it is best just to start with a new population. Here are some
controllers that do reasonable well:
(sub (div (iflz (sin (cos (yVelocity))) (mul (div (directAngle)
(mul (cos (yVelocity)) (add -2.305528473404248 -6.22291397636536))) 7.0404892298177195)
(directDistance)) (yVelocity)) (xVelocity))
(sub (div (iflz (sin (cos (yVelocity))) (mul (div (directAngle)
(mul (sub (asin 9.982073944360085) (yVelocity)) (add -2.305528473404248
(sub (div (iflz (sin (iflz (sin (cos (mul (sub (iflz (sin (yVelocity))
(directAngle) 7.0404892298177195) (yVelocity)) (add -2.305528473404248
(iflz (directAngle) (iflz -6.587768719548546 -8.440287062002804 (directAngle))
(directDistance)))))) (mul (div (directAngle) (mul (sub -8.440287062002804
(yVelocity)) (add (yVelocity) (iflz -6.587768719548546 (iflz -6.587768719548546
-8.440287062002804 (directAngle)) (add -2.305528473404248 (sub (div -6.587768719548546
(acos -8.075929770342773)) (xVelocity))))))) 7.0404892298177195) (directDistance)))
(directAngle) (directDistance)) (acos -8.075929770342773)) (xVelocity)))))
7.0404892298177195) (directDistance)) (acos -6.615442979253265)) (xVelocity))
(iflz (iflz (sub (cos (directAngle)) (sin (yVelocity)))
(sub (sub -2.4684089325679404 (asin -4.1692158746125525)) (sin (add -7.69110794441678
6.751196509037012))) (sub (mul (mul 4.877219410183999 6.468809843282834)
(sin -9.498963974382432)) (cos (acos 8.187091167795458)))) (sub (directAngle)
(iflz (add (sin (iflz (cos 2.8207755195175075) (xVelocity) 6.680786356368312))
(sub -3.792151134673853 (cos (directAngle)))) (xVelocity) (asin (div 8.187091167795458
(asin (directAngle)))))) (sub (div -8.075151056600305 (asin (directAngle)))
(xVelocity)))
(iflz (iflz (sub (cos (sin -5.1497036256975655)) (sin
(yVelocity))) (sub (sub -2.4684089325679404 (asin -4.1692158746125525))
(sin (add -7.69110794441678 6.751196509037012))) (sub (mul (mul 4.877219410183999
6.468809843282834) (sin -9.498963974382432)) (cos (acos 8.187091167795458))))
(sub (directAngle) (iflz (add (sin -1.018408489051728) (sub -3.792151134673853
(cos (directAngle)))) (xVelocity) (asin 8.682452651236034))) (sub (div
-8.075151056600305 (asin (directAngle))) (xVelocity)))
(div (div (acos 8.509996845824482) (directAngle)) (add (mul (div (div (mul (sub (sub -8.934308268248476 8.279085031748117) -6.997432626974267) 9.77190654881824) -6.997432626974267) 9.77190654881824) (asin (cos 0.9432053390287809))) (yVelocity)))