The ever-increasing applications of UAV’s have shown the great capabilities of these technologies. However, for many cases where one UAV is a powerful tool, an autonomous swarm all working cooperatively to the same goal presents amazing potential. Environment that are dangerous for humans, are either too small or too large for safe or reasonable exploration, and even those tasks that are simply boring or unpleasant are excellent areas for UAV swarm applications. In order to work cooperatively, the swarm must allocate tasks and have adequate path planning capability.
This paper presents a methodology for two-dimensional target allocation and path planning of a UAV swarm using a hybridization of control techniques. Genetic algorithms, fuzzy logic, and to an extent, dynamic programming are utilized in this research to develop a code known as “UNCLE SCROOGE” (UNburdening through CLustering Effectively and Self-CROssover GEnetic algorithm). While initially examining the Traveling Salesman Problem, where an agent must visit each waypoint in a set once and then return home in the most efficient path, the work’s end goal was a variant on this problem that more closely resembled the issues a UAV swarm would encounter.
As an extension to Dr. Obenmeyer’s “Polygon-Visiting Dubins Traveling Salesman Problem”, the Multi-Depot Polygon-Visiting Dubins Multiple Traveling Salesman Problem consists of a set number of visibility areas, or polygons that a number of UAV’s, based in different or similar depot must visit. While this case is constant altitude and constant velocity, minimum turning radii are considered through the use of Dubins curves. UNCLE SCROOGE was found to be adaptable to the PVDTSP, where it competed well against the methods proposed by Obenmeyer. Due to limited benchmarking ability, as these are newly formed problems, Obenmeyer’s work served as the only basis for comparison for the PVDTSP. UNCLE SCROOGE brought a 9.8% increase in accuracy, and a run-time reduction of more than a factor of ten for a 20 polygonal case with strict turning requirements. This increase in performance came with a 99% certainty of receiving the best found solution over the course of 100 runs. With only a 1% chance for error in this particular case, the hybridized method has been shown to be quite powerful.
While no comparison is currently possible for MDPVDMTSP solutions, UNCLE SCROOGE was found to develop promising results. On average, it takes the code 25.62 seconds to approximately solve a 200 polygon, 4 depot, 5 UAV’s per depot problem. This polygon count was increased even up to 2,500, with a solution taking 9.8 hours. It has been shown that UNCLE SCROOGE performs well in solving the MDPVDMTSP and has acceptable scalability.