The difficulty of roving eyes

author = "Craig W. Reynolds",

title = "The difficulty of roving eyes",

booktitle = "Proceedings of the 1994 IEEE World Congress on Computational Intelligence",

year = "1994",

volume = "1",

pages = "262--267",

address = "Orlando, Florida, USA",

month = "27-29 " # jun,

publisher = "IEEE Press",

DOI = "

doi:10.1109/ICEC.1994.350005",

keywords = "genetic algorithms, genetic programming, controller evolution, corridor following task, dynamic aiming, evolved control programs, fitness distributions, lens effect, populations, problem difficulty, problem domain, proximity sensor directions, random search, robot-like vehicle, roving eyes, sensor representations, syntactic constraint, user's representation, vehicle control programs, computer vision, mobile robots, path planning,",

size = "6 pages",

abstract = "Genetic programming (GP) operates on a problem domain through the lens of the user's representation. The difficulty (GP hardness) of an application can depend as much on the representation as on the problem itself. Seemingly small changes of representation can cause significant changes in difficulty. An example of this effect was discovered while using GP to evolve a controller for a robot-like vehicle performing a corridor-following task. A small syntactic constraint applied to evolved control programs significantly reduced the difficulty of the problem. This allowed a solution to be found with a population of 2000 for a problem that had previously resisted solution with populations of 10,000. The syntactic constraint corresponded to removing the controller's ability to dynamically aim its proximity sensors. In the constrained case, sensor directions remain fixed during the lifetime of the controller and are aimed solely by evolution. In his investigation of the lens effect, Koza (1992) found that the relative difficulty of two representations can be determined by comparing the distribution of fitnesses found during a random search of the two program spaces. Indeed, by examining the initial, random generation of GP runs for the corridor-following problem, we see a foreshadowing of the subsequent difficulty of several sensor representations",

notes = "The difficulty for GP to produce a corridor following robot controller is found to depend dramatically on how the sensor primitive ``look-for-obstacle'' is used by GP. With no constraints very difficult. Readily solved if syntax rules are imposed which force its argument to be a constant.",