Multi-obstacle Path Planning of UAV Based on Improved Ant Colony System Algorithm

Recently unmanned aerial vehicles (UAVs) have been widely adopted by military and civilian applications due to their strong autonomies and adaptabilities. Especially in some tasks, a complex path planning problem is that a UAV traverses and searches multiple targets in an environment with obstacles, which is a traveling salesman problem with NP-hard computational complexity. The traditional algorithms which do not consider environment with obstacles are not feasible in the actual flying environment. In this paper, we study the path planning problem of a UAV searching for multiple targets in the environment with irregular obstacles. First, we use an improved geometric algorithm to find an accessible path between any two targets. Then, we design an ant colony system(ACS)-based optimization strategy to adjust the accessible order of a UAV such that the task completion time obtained by our approach would be reduced as much as possible. Finally, experiments with randomly generated target points in an environment with obstacles are conducted to show the effectiveness of the algorithm.

I. Introduction

With the rapid development of UAV technology and Internet of things technology, UAVs are widely used in military and civil fields [1]. Compared with the manned aerial vehicles, the UAVs have a great advantage in the complex and dangerous environment. However, due to the limitations of UAVs' own energy consumption, flight performance, load capacity and other factors [2], it is necessary to plan a safe and low-cost flight path for the UAV.