Maze Solving Optimization through Genetic Programming

Overview

Over billions of years, species have evolved, making them better suited for tasks that aid their survival. The purpose of this experiment is to determine whether or not the principles of evolution can be effectively used to make computer algorithms more efficient at solving problems, specifically mazes. This experiment was conducted using a computer program written in Java. For each generation, a set of randomly generated mazes was produced and solved by each algorithm in the generation. Using ideas derived from biological evolution, such as mutation and “survival of the fittest,” subsequent generations of algorithms were produced. An important part of evolution is determining the fitness of an organism. The fitness score for each algorithm was determined by the average number of moves it took to solve each maze. In order to maximize the effectiveness of the evolutionary process, variables including generation size, genome size, and mutation rate were manipulated during testing. To determine the effectiveness of the evolution, the improvement in average fitness score over fifty generations was compared between trials incorporating evolutionary algorithms and trials without evolutionary algorithms using a one sided t test. The results supported the hypothesis that evolution led to more efficient maze solving programs. With a growing number of autonomous robots today, the creation of navigation algorithms for unknown terrain has relevant real-world applications. Forests, cities, and fields are all classes of terrain with distinct instances, but similarities throughout the class. By simulating these types of real-world mazes and allowing algorithms to evolve new adaptations for them, we can better prepare autonomous vehicles to navigate whatever they may face.

Competition history

• ISEF 2017 Robotics and Intelligent Machines · Entry ROBO045

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.