# Genetic programming with “karel the robot”?

Karel the robot is an education software comparable to turtle graphics to teach programming for beginners. It's a virtual stackbased interpreter to run a domain specific language for moving a robot in a maze. In it's vanilla version, the user authors the script manually. That means, he writes down a computer program like “1. moveforward 2. if reachedobstacle==true then stop 3. moveleft”. This program gets started in the virtual machine.

In contrast, Genetic programming has the aim to produce computercode without human intervention. So called permutations are tested if they are fulfill the constraints and after a while the sourcecode 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 computercode. 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?

• Yes. The question is, whether they produce any useful output. Your 'fitness function' could be a parser which checks whether your programs are syntactically well-formed, but the output would probably be fairly random. Unless you incorporate the desired output into the fitness function in some way. – Oliver Mason Dec 10 '18 at 17:59
• @OliverMason My idea was to model the fitness function with learning from demonstration. This is sometimes called inverse reinforcement learning or transfer learning because the aim is to replicate human actions. – Manuel Rodriguez Dec 10 '18 at 18:06

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.

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).