The Simulated Evolution of Robot Perception

Abstract

This dissertation tackles the problem of using genetic programming to create the vision subsystem of a reactive obstacle avoidance algorithm for a mobile robot. To focus the search on computationally efficient algorithms while dealing images from a non-toy problem, the representation restricts computation to be over a window which moves vertically over the image. The evolved programs estimated the distance to the nearest object in various directions, given only a camera image as input. Using a typical supervised learning framework, images of the environment were collected from the robot's camera and the correct distance in various directions determined by hand. Evolving programs were evaluated on this fixed training set and compared to the hand determined answers. Once the evolution was complete, obstacle avoidance programs were written to use the best evolved programs, and the combined system used to control a robot. The approach can be seen as automating the iterative design process. A researcher's main contribution is typically at a high level-techniques and frameworks-yet most time is spent on an example problem, trying different instantiations until one works. When faced with such a problem, one can usually think of a half dozen very different approaches, and even write them out in pseudo code. The technique proposed here can be seen as searching the space spanned by that pseudo code. In a series of experiments, programs were evolved in three different ways for two different environments to both create working systems and push the limits of the approach. Even in this nascent form, the evolved programs work about as well as existing, hand written systems. They used a number of architectures, including a recurrent mathematical formula and a series of if statements similar to a decision tree but with non-linear relations between as many as five image statistics. They successfully coded around peculiarities of the imaging process and exploited regularities of the environment. Finally, when given a representation so general as to cause the genetic algorithm to fail, and hand constructed rough answer was used as a "seed," which the genetic algorithm successively modified to cut its error rate by a factor of 5.8. This dissertation grew out of my conviction that critiques of Artificial Intelligence can be viewed constructively, as intellectual light-houses to guide us closer to the fundamental nature of thought, to the real problems at the heart of intelligence. To not address them, to work on techniques with fundamental flaws, would be fooling oneself no matter how impressive the demonstrations. There seems to be something fundamental about AI that we are all missing, and I believe these critiques bring us closer to it. This dissertation describes the experiments and their results, discusses ways to develop them further, then presents critiques of AI and discusses the potential of this approach to overcome those critiques.