Session: 02-03-02: Optimization

Paper Number: 150329

150329 - Design of Multi-Drone Paths Based on Genetic Algorithms 

In a wide range of industries, the use of unmanned aerial vehicles (UAVs), commonly known asdrones, provides multiple opportunities and generates efficiencies. A growing number ofindustry professionals are using drones for the purposes of improving and optimizing industrialprocesses and enhancing operational efficiencies. Using drones, which have proved to beextremely powerful, versatile industrial tools, a wide variety of applications can beaccomplished. Furthermore, they are particularly effective in missions that require long-termsurveillance. Drones are particularly interesting due to their ability to coordinate, as well astheir ability to cover large areas or collaborate with one another to achieve specific goals, suchas mapping terrain. This paper presents an innovative algorithm for path planning that istailored for drone operations as an alternative to solving the Multi-Traveling SalesmanProblems. The proposed algorithm combines concepts from K-Means and Genetic Algorithms(GA) in order to optimize drone routes in an efficient manner. The algorithm is composed of twoprimary sub-algorithms: target classification and path planning. The K-Means algorithm isinitially employee in order to determine the optimal number of clusters and distribute targetsamong drones. The algorithm then calculates the shortest path for each drone using a multi-chromosome GA in order to minimize the distance travelled by each drone. Our study examinedvarious methods for implementing GA, as well as different combinations of GA operatormethods, in order to identify the most effective method. We tested selection operators such asRank Selection, Tournament Selection, and Steady State Selection, as well as mutationoperators such as Swap Mutation, Inversion Mutation, and Scramble Mutation. Over the courseof the research, Order Crossover was consistently used as the crossover operator. During theresearch process, we tested the behavior of various combinations of operators of the geneticalgorithm on a database of 100 targets (the initial point for the drones included), following theprocedures previously outlined, provided that the number of drones was known in advance. Anexperimental evaluation was conducted for predetermined numbers of drones (K=4, K=5, andK=6), with the combination of Rank Selection operators together with Order Crossover andInversion Mutation yielding the best results. Additionally, the algorithm was tested in scenariosin which the number of drones was not predetermined, allowing it to determine the optimalnumber of drones needed to cover all targets. In selecting GA operators, previous researchfindings demonstrated consistently favourable results. The proposed algorithm offers aneffective solution for advanced drone path planning, both in predetermined deploymentscenarios as well as dynamic deployment scenarios. By combining K-Means and GA techniques,this algorithm enhances the efficiency and performance of drone operations across a widerange of applications by optimizing route plannings.

Presenting Author: Miri Weiss Cohen Braude College of Engineering

Presenting Author Biography: Miri Weiss Cohen is in the Head of Department of Software Engineering at the Braude College of Engineering. Her research interests lie in the area Machine Learning (AI) methodologies in use of optimization for engineering problems. In recent years, she is focusing on two major topics: first, prediction and optimization of green energy (solar and wind) models using bigdata time series. Second, using CT and MRI scans for classification and segmentation of cancer, reconstructing 3D volumes Deep learning. She has collaborated actively with researchers in several other disciplines relating to Machine Learning in service of rehabilitation and design of human computer interfaces

Authors:

Moran Levi Braude college of Engineering
Ron Rozenfeld Braude College of Engineering
Miri Weiss Cohen Braude College of Engineering