Is it possible to generate "Karel the robot" programs with genetic programming?

Question

Karel the robot is an education software comparable to turtle graphics to teach programming for beginners. It's a virtual stack-based interpreter to run a domain-specific language for moving a robot in a maze. In its vanilla version, the user authors the script manually. That means, he writes down a computer program like

1. move forward
2. if reached obstacle == true then stop
3. move left.

This program is then executed in the virtual machine.

In contrast, genetic programming has the aim to produce computer code without human intervention. So-called permutations are tested if they are fulfilling the constraints and, after a while, the source code is generated. In most publications, the concept is explained on a machine level. That means assembly instructions are generated with the aim to replace normal computer code.

In "Karel the robot" a high-level language for controlling a robot is presented, which has a stack, but has a higher abstraction. The advantage is, that the state space is smaller.

My question is: is it possible to generate "Karel the robot" programs with genetic programming?

Answer 1

A genetic algorithm is used to find an optimal solution to a problem. The parameters of the problem are encoded in the population, where each individual contains a solution to the problem in itself. Each individual is evaluated using a fitness function, and then the highest scoring individuals are used to create a new set of individuals by mixing up their parameters, and this new set replaces the worst scoring individuals from the previous generation. Over time, the average fitness of the population will (hopefully) increase, and a good solution be found. Essentially, the search space is explored in parallel through the many individuals in the population, which means that local maxima can probably be avoided.

The question now is: What is the problem you want to optimise?

The Karel language is fairly simple, and has few tokens. A program should be easily encodable in the right format, though genetic algorithms usually require individuals to have the same size (though shorter programs could be padded with no-ops). Recombining the best programs could mean swapping tokens. Maybe syntactic constraints could be factored into this to avoid crass syntactic errors. That should not be an insurmountable problem.

However, that still leaves the question of the fitness function. A basic criterion would be syntactic: if the program doesn't parse, it's not 'fit'. This could potentially wipe out a lot of offspring, and doesn't really help you much: it would produce more or less random programs which are syntactically well-formed.

What you really want is to evaluate the outcome of the programs. Like, which program can best navigate a maze. So you need to execute them and see what they produce. Then you run straight away into the halting problem: your little program might contain an endless loop and will never terminate. So you need to add a kind of time-out, or a limit on the steps the program can execute. This should be easy to do in a virtual machine.

So, to answer your question: Yes, it is possible to turn creating Karel programs into a problem that a genetic algorithm can be applied to. However, you need to be clear about what problem you want to solve. I don't quite understand what you mean by "learning from demonstration" or how you can achieve the aim of replicating human actions, but if you can somehow encode that in a fitness function, GAs are a tool you can use.

Answer 2

To generate high level programming language code in the context of genetic programming the Grammatical Evolution technique could be a good start. It allows to generate syntactically correct samples according to a grammar, so there will be no (syntactic) garbage in a population.

In the original implementation it has (very simple and) quite destructive mutation and crossover operators. This could be changed by making the operators more sophisticated, so they respect the actual tree-like structure of the samples and the grammar constraints, but effectively it will result in implementing the classical tree-based Genetic Programming system (which isn't bad).

The evaluation of such samples should be done by executing them in an appropriate environment (the actual VM and the desired map or whatever).

Answer 3

Is it possible to generate "Karel the robot" programs with genetic programming?

Yes, it is possible.

Robocode is a programming game where players program a tank-like robot to battle other robots in an arena. This has some similarities to "Karel The Robot" (i.e. the player programs a robot that has to perform a task in an arena). There is a paper describing the use of genetic programming in creating Robocode programs: GP-Robocode: Using Genetic Programming to Evolve Robocode Players by Yehonatan Shichel, Eran Ziserman, and Moshe Sipper.

In Genetic Programming: On the Programming of Computers by Means of Natural Selection by John R. Koza, Appendix B, there is an example solution to a "discrete non-hamstrung squad car game". Description of the game:

The discrete non-hamstrung squad car is a game of perfect information involving two players moving on a checkerboard grid of indefinite size. The pursuing player is a squad car with a speed advantage over the pedestrian evader. The object is to discover a strategy for the pursuer that results in capture of the evader in optimal (i.e., minimal) time.

The Common Lisp source code of a genetic programming solution is also available from the author's website: http://www.genetic-programming.org/gplittlelisp.html. The genetic programming representation used to solve this problem could conceivably be adapted to "Karel The Robot" problems.