Program induction: building a wall

Abstract

Evolutionary programming of many systems has been demonstrated in the literature. In This work we use these techniques to program a virtual robot to build a wall out of blocks that impede progress in one direction across a grid of squares. Specifically, two methods for automatic program induction are compared on this task. Virtual blocks are presented one at a time in a fixed location on the grid. The robot must move the currently presented block to enable presentation of the next block as well as using the blocks to build the wall. An evolutionary algorithm operating on strings of actions for the task is used for baseline performance measurement. Evolutionary algorithms operating on GP-Automata and ISAc lists are then applied to the wall building task. In addition to broadening the palette of virtual robotics task, this permits us to compare these two representations for program induction. We study two versions of the wall building problem. The first, in which there are impenetrable walls at the boundary of the virtual world, is much easier than the second method that takes place on a virtual table-top where blocks and the robot may fall off. In addition to the usual randomized initialization, a technique for initializing evolutionary runs with already evolved solutions is presented for the string baseline and both program induction representations.