Program Induction: Building a Wall
with James I. Lathrop
Submitted to CEC 2004

Abstract PDF eprint

We study the problem of getting a virtual robot to build a wall out of blocks that impede progress in one direction across a grid of squares. The blocks are presented one at a time in a fixed location, with translation of the currently presented block required to enable presentation of the next block. We use a genetic algorithm operating on strings of actions as a baseline. We then use evolutionary algorithms to specialize GP-Automata and ISAc lists to the wall building task. In addition to broadening the assault on the virtual robotics task, this permits us to compare these two program inductions techniques. 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. The second version takes place on a virtual table-top where blocks and the robot may fall off.