Assessment of genetic algorithm based assignment strategies for unmanned systems using the multiple traveling salesman problem with moving targets

Abstract

The continuous and rapid advancements in autonomous unmanned systems technologies presents increasingly sophisticated threats to military operations. These threats necessitate the prioritization of improved strategies for military resources and air base defense. In many scenarios, it is necessary to combat hostile unmanned systems before they reach the defensible perimeters of existing fixed-base defense systems. One solution to this problem is weaponizing friendly unmanned systems to hunt and kill hostile unmanned systems. However, the assignment and path planning of these “Hunter-Killer” systems to incoming hostile unmanned systems, in a multiple friendly versus multiple enemy scenario, presents a major challenge and can be represented by the Multiple Traveling Salesmen Problem with Moving Targets (MTSPMT). The MTSPMT is a combinatorial optimization problem and an extension of the classical Traveling Salesman Problem whereby the number of salesmen is increased and targets (cities) move with respect to time. The objective of the MTSPMT, for the application of military defense using a squadron of Hunter-Killer unmanned systems, is to determine a path that minimizes the cost required for multiple Hunter-Killer unmanned systems to successfully intercept all incoming threats. In this study, an assessment of genetic algorithm based assignment strategies for unmanned systems using the MTSPMT is performed. A number of scenarios were constructed using up to 50 hostile unmanned systems and the generated solutions were compared based on their resulting time to converge, solution fitness, and number of generations required. Findings indicate that under certain conditions genetic based algorithms provide better results on average and converge more rapidly than brute force searching and existing assignment and path planning solutions.