Analysis of Path Planning Algorithms Based on Travelling Salesman Problem Embedded in UAVs

• Thiago Werlley Bandeira UFPB
• Walton P. Coutinho UFPB
• Alisson V. Brito UFPB
• Anand Subramanian UFPB

Resumo

Monitoring and recognition of large areas bring great challenge and Unmanned Aerial Vehicles (UAV) promise tobe a great help. The challenge is to optimize the task of UAVs, in order to reach the goals with maximum possible quality. The objective of this work is to analyze possible path algorithms and the feasibility of embedded them in a UAV. The question we aim at answering is: given a set of points to be visited and a battery level of the UAV, what is the best possible trajectory to visit all points with the highest resolution of the images? This work proposes the application of two algorithms for solving well known problems from literature, namely the Traveling Salesman Problem and the Close-Enough Traveling Salesman Problem, in the path planing of UAVs. Both approaches present satisfactory results, and a discussion is raised about whether it is possible to embed optimization software into a light and small computing platform.

Palavras-chave: Trajectory, Vehicles, Traveling salesman problems, Heuristic algorithms, Mathematical model, Optimization, Unmanned Aerial Vehicle, Path Planning, Embedded System