GPU Enhanced Path Finding for an Unmanned Aerial Vehicle

Situated robots like unmanned aerial vehicles (UAVs) typically need to arrange their plans as a sequence of actions between multiple goal locations. Identifying the sequence of goals to plan for can be naturally cast in the form of the traveling salesman problem (TSP). By making faster decision, more complex real-time operations may be achieved. A graphics processing unit (GPU) is used in this work to enhance the computational execution rate. A genetic algorithm working in concert with a clustering algorithm is used to quickly compute the desired routes. Several algorithm customizations are made to address the GPU´s limited memory space. The implemented GPU code works 4.8 times faster than serially implemented code and the algorithm can solve large problems with 4000 waypoints.