Path Planning of UAVs Under Dynamic Environment based on a Hierarchical Recursive Multiagent Genetic Algorithm

Path planning is a key technology to realize the automatic navigation of unmanned aerial vehicles (UAV), which has great significance both in theory and practical application. Evolutionary algorithms (EAs) are a type of nature-inspired computational methodologies for addressing complex real-world problems that cannot be solved well by mathematical or traditional modeling. However, the huge calculation of each iteration in the EAs greatly reduces the efficiency of the algorithm. In this paper, to accelerate the search speed of EAs and consider the dynamics of the environment, we propose a hierarchical recursive multi-agent genetic algorithm that can perform path planning in real time, termed as HR-MAGA. We used a strategy of layer-by-layer optimization on 3D maps with different resolution in the optimization process. The local search ability of the algorithm is improved by competition and self-learning process. In addition, the hierarchical recursive optimization process can greatly reduce the amount of computation and effectively deal with the dynamic characteristics of the environment. The experimental results show that HR-MAGA not only has strong global optimization ability, but more importantly, is able to generate collision free paths in real time after considering the physical limitations of the UAV and the dynamics of the environment.