Maze Navigation via Genetic Optimization

Abstract

One of the most interesting applications of genetic algorithms falls into the area of decision support. Decision support problems involve a series of decisions, each of which is influenced by all decisions made prior to that point. This class of problems occurs often in enterprise management, particularly in the area of scheduling or resource allocation. In order to demonstrate the formulation of this class of problems, a series of maze problems will be presented. The complexity of the mazes is intensified as each new maze is introduced. Two solving scenarios are introduced and comparison results are provided. The first scenario incorporated the traditional genetic algorithm procedure for the intended purpose of acquiring a solution based upon a purely evolutionary approach. The second scenario utilized the genetic algorithm in conjunction with embedded domain specific knowledge in the form of decision rules. The implementation of domain specific knowledge is intended to enhance solution convergence time and improve the overall quality of offspring produced which significantly increases the probability of acquiring a more accurate and consistent solution. Results are provided below for all mazes considered. These results include the traditional genetic algorithm final result and the genetic algorithm optimization approach with embedded rules result. Both results were incorporated for comparison purposes. Overall, the incorporation of domain specific knowledge outperformed the traditional genetic algorithm in both performance and computation time. Specifically, the traditional genetic algorithm failed to adequately find an acceptable solution for each example presented and prematurely converged on average within 54% of their specified generations. Additionally, the most complex maze generated an optimal path directional sequence ( i.e . N, S, E, W) via a traditional genetic algorithm which possessed only 50% of the required allowable path sequences for maze completion. The incorporation of embedded rules enabled the genetic algorithm to locate the optimum path for all examples considered within 5% of the traditional genetic algorithm computation time.