Grammatical Evolution (GE) is a computational technique based on formal grammars. A formal grammar specifies the correct construction of programming statements in a high level programming language such as Java. In GE, the high level programming language is represented in Backus-Naur Form (BNF) and uses the multiple options provided in BNF to exhaustively create the many different possibilities of programming statements.
BNF notation expresses the grammar of a language using four core components [Warford].These components can be expressed in the tuple {N, T, P, S}:
An autonomous robot uses on-board controllers to perceive, decide, and act on their environment [Russell]. There is a growing demand for autonomous robots to act intelligently in dynamic environments. This work describes the use of Grammatical Evolution (GE) to create an optimal robot-controlling programs to be executed by the robot controller of the Finch robot.
In our grammatical evolution system, each genotype is represented as a string of integers, generated through a combination of random and genetic algorithmic operations. The genotype is then transformed to a Java-like program (the ÒphenotypeÓ) by performing a grammatical derivation on the corresponding BNF grammar. In fact, the precise mapping from genotype to phenotype is the result of expanding the particular production rules represented in the grammar as specified by the set of integers in the genotype. The phenotype is evaluated using a fitness function and simulator that produces a valuation of the merit (its fitness score) of that generated program. Based on their fitness scores and other attributes, individuals will then be selected to be "parents" for a new generation of individuals. This cycle continues until a suitable solution to the task has been evolved. The main accomplishment of system GEF was the evolution of a suitable controller program for the Finch robot that enables the robot to navigate simple obstacle arrangements.
Five part construction process that will use grammatical evolution to create a computer program that controls a Finch robot.
