Genetic Programming
of Autonomous Agents

description

The purpose of this project is to use genetic programming to develop control programs for autonomous vehicles. The initial focus will be on creating a multi-agent, perimeter maintenance program that will maximize the secure perimeter around a base.

genetic programming

GP is an adaptive search method based on the theory of evolution.

What is GP searching?

GP searches a space of all possible programs that can result from user defined function and terminal sets. These sets are chosen to give the program the necessary tools to solve the problem. For example, if the goal is to evolve something simple like a 4-bit multiplexer, the function set might be {AND OR NOT XOR} to represent 1-output functions on bit-valued inputs, and the terminal set might be {S0 S1 A0 A1 A2 A3}, representing 2 signal-selection bits and 4 signal input bits.

How does the search begin?

GP begins by initializing a population of randomly generated program trees consisting of primitives from the function and terminal sets. For the multiplexer example, a generation 0 individual could be ((S0 OR NOT(A0)) AND S1), or in tree form (AND (OR S0 (NOT A0)) S1).

How is the search guided?

GP requires a way to measure each program's "fitness level" to determine how likely it is for that program to contribute to the next generation. Once each member of a generation has its fitness evaluated, evolutionary operators simulate reproduction and mutation to create a new generation that is more likely to contain "genetic" material from "fit" individuals in the previous generation. For most problems, fit solutions are located near other fit solutions in the search space, and these genetic operators produce programs adjacent to their parents. The search therefore begins focusing on the area around the most fit individuals. A fitness function for the multiplexer could be the number of correct outputs the program provides when tested using all possible combinations of inputs (i.e. fitness level of 0-64).

When is GP most useful?

GP is best for problems with no ideal mathematical solution and a clear way of determining the fitness of a solution. The function and terminal sets must be large enough to enable programs to perform the desired action, but small enough that a good solution can be found in a reasonable amount of time.