Multiobjective Pathfinding Using Hardware Accelerated Genetic Algorithms

Multiobjective pathfinding is an extremely computationally expensive problem, yet it is important for many applications. Classical algorithms fail as the complexity of the environment increases, and we must look to other methods for finding high-quality paths. This is especially true when we move beyond assigning a cost to each point on a map, and consider environmental properties that have a magnitude and a direction, such as wind. In this thesis, I present a scalable custom hardware designed by Geir Åge Noven for evaluating the fitness of paths through real-world environments. The hardware is based on a grid of processing elements, and each path traverses this grid as its fitness is being calculated. The concept of topologically folding the environment is discussed. This operation allows each processing tile to represent multiple areas of the map, which allows for even load distribution among the processing tiles. The proposed hardware is compared to other evaluation hardwares, including the GPU, and some simulations are performed on genetic algorithm performance on multiobjective pathfinding. I find that the proposed hardware has several properties that makes it suitable for evaluating path fitness, such as even load distribution among the processing tiles. I also find that genetic algorithms can continually improve paths in a real-world terrain for a large number of generations. Finally, the computational qualities of the proposed hardware and GPU architectures are compared