I. Introduction of UAV

Introduction with the development of modern technology, there are more and more types of aircraft, and their applications are becoming increasingly specialized and perfect, such as DJI PS-X625 UAV, which is used for plant protection, BAOji X8 UAV, which is used for street scene shooting and monitoring patrol, and White Shark MIX underwater UAV, which is used for underwater rescue. The performance of the aircraft is mainly determined by the internal flight control system and external path planning. In terms of path problem, only by the operator in the concrete implementation of the task in the hands of the remote control of unmanned aerial vehicles to perform the corresponding work, may be psychological and technology put forward high request of the operator, in order to avoid personal error, the risk of causing the damage of aircraft, a solution is carried out on the aircraft flight path planning. The measurement accuracy of aircraft, the reasonable planning of flight path, the stability and safety of aircraft at work and other changes require more and more high requirements for the integrated control system of aircraft. Uav route planning is a problem to design the optimal route to ensure that UAV can complete specific flight tasks and avoid various obstacles and threat areas in the process of completing the tasks.

1. Common path planning algorithms Figure 1 Common path planning algorithms This paper mainly studies the flight path planning of UAV in the cruise stage. Assuming that uav maintains constant altitude and speed in flight, flight path planning becomes a two-dimensional plane planning problem. In the path planning algorithm,AThe algorithm is simple and easy to implement. To improve ABased on the algorithm, A new and easy to understand improvement A is proposedAn algorithm for uav flight path planning. A traditionalIn this algorithm, the planning area is rasterized, and node expansion is limited to the intersection of grid lines, and there are usually two directions of motion at a certain Angle between the intersection of grid lines. Enlarge and refine the two sections of paths with angles infinitely, and then use the corresponding path planning points on the two sections respectively as tangent points to find the corresponding center of the circle that forms the tangent circle, then make an arc, and find the corresponding center Angle of the arc between the corresponding two tangent points, and calculate the length of the arc according to the following formulaWhere: R — radius of the tangent circle; Alpha — the central Angle corresponding to the arcs between the tangent points.

2. Ant colony algorithm introduction

1 Origin and development history of Ant Colony Algorithm (ACA) Marco Dorigo et al. found that ant colonies can quickly find targets by secreting biohormones called pheromones to communicate foraging information when searching for food. Therefore, in his doctoral dissertation in 1991, he first systematically proposed a new intelligent optimization algorithm “Ant System” (AS for short) based on Ant population. Later, the proposer and many researchers made various improvements to the algorithm and applied it to a wider range of fields. Figure coloring problem, secondary assignment problem, workpiece sequencing problem, vehicle routing problem, job shop scheduling problem, network routing problem, large-scale integrated circuit design and so on. In recent years, M.Dorigo et al. further developed Ant algorithm into a general Optimization technology “Ant Colony Optimization (ACO)”, and called all the algorithms conforming to ACO framework “ACO algorithm”.

Specifically, individual ants start looking for food without first telling them where it is. When an ant finds food, it releases a volatile pheromone (called a pheromone, it evaporates over time and its concentration indicates how far the path is) into the environment that other ants sense as a guide. Generally, when there are pheromones on multiple paths, the ant will preferentially choose the path with high pheromone concentration, so that the pheromone concentration of the path with high pheromone concentration will be higher, forming a positive feedback. Some ants do not repeat the same route as others. They take a different route. If the alternative path is shorter than the original one, gradually more ants are attracted to the shorter path. Finally, after some time of running, there may be a shortest path repeated by most ants. In the end, the path with the highest pheromone concentration is the optimal one selected by the ant. Compared with other algorithms, ant colony algorithm is a relatively young algorithm, characteristics, such as distributed computing center control and asynchronous indirect communication between individuals, and is easy to be combined with other optimization algorithms, through many healthyenterprise continuously explore, to today has developed a variety of improved ant colony algorithm, but the principle of ant colony algorithm is still the main.

2 solving principle of ant colony algorithm Based on the above description of ant colony foraging behavior, the algorithm is mainly to simulate the foraging behavior of the following aspects: (1) the simulation diagram contains two kinds of pheromones in the scene, said a home, a place, said food and both pheromone volatilization in at a certain rate. (2) Each ant can perceive information only in a small part of the area around it. Ants searching for food, if within the scope of the perception, can directly in the past, if is beyond the scope of awareness, will be toward more than pheromones, ants can have a small probability pheromone many places don’t go, and instead, it is very important to the small probability event, represents a way of innovation, is very important to find a better solution. (3) Ants return to the nest using the same rules as when they find food. (4) When ants move, they will first follow the guidance of pheromone. If there is no guidance of pheromone, they will follow the direction of their moving inertia, but there is a certain probability of changing direction. Ants can also remember the path they have already walked, so as to avoid repeating the same place. (5) The ants leave the most pheromones when they find food, and then the farther away they are from the food, the less pheromone they leave. The rules for finding nest pheromones are the same as for food. Ant colony algorithm has the following characteristics: positive feedback algorithm, concurrency algorithm, strong robustness, probabilistic global search, does not rely on strict mathematical properties, long search time, easy to stop phenomenon. Ant transfer probability formula:In the formula, is the probability of ant K transferring from city I to city J; α and β were the relative importance of pheromones and heuristic factors, respectively. Is the pheromone quantity on edge (I, j); Is the heuristic factor; The next step for Ant K allows the selection of cities. The above formula is the pheromone update formula in the ant system, and is the pheromone quantity on the edge (I,j). ρ is the evaporation coefficient of pheromone, 0<ρ<1; Is the pheromone quantity left by the KTH ant on the edge (I,j) in this iteration; Q is a normal coefficient; Is the path length of the k ant during this tour. In ant system, pheromone update formula is:3. Solving steps of ant colony algorithm: (1) Initialization parameters At the beginning of calculation, it is necessary to initialize related parameters, such as ant colony size (ant number) m, pheromone importance factor α, heuristic function importance factor β, pheromone will emit money ρ, total pheromone release Q, maximum iteration times iter_max, initial value of iteration times iter=1. (2) construct solution space and randomly place each ant at different starting points. For each ant k (k=1,2,3… M), calculate the next city to be visited according to (2-1) until all ants have visited all cities. (3) update information su to calculate the path length of each ant Lk(k=1,2… , m), record the optimal solution (shortest path) in the current iteration number. At the same time, pheromone concentration on the connection path of each city was updated according to Equations (2-2) and (2-3). (4) Determine whether to terminate if iter<iter_max, set iter=iter+1 to clear the record table of ant paths and return to Step 2; Otherwise, the calculation is terminated and the optimal solution is output. (5) Determine whether to terminate if iter<iter_max, set iter=iter+1 to clear the record table of ant paths and return to Step 2; Otherwise, the calculation is terminated and the optimal solution is output. 3. Determine whether to terminate. If iter<iter_max, set iter=iter+1 to clear the record table of ant paths and return to Step 2. Otherwise, the calculation is terminated and the optimal solution is output.

Three, some source code

% -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- ant colony algorithm is the main function -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- CLC clear load data z Information % Starting coordinates starty=10;
starth=3; % endy=8;
endh=5;

n=10;
m=21; Best=[]; [path,information]=searchpath(n,m,information,z,starty,starth,endy,endh); % path find fitness=CacuFit(path); % fitness calculation [BESTFITNESS, Bestindex]=min(fitness); % bestpath=path(bestindex,:); Best=[Best;bestfitness]; % % Update pheromone ROU =0.2;
cfit=100/bestfitness;
k=2;
for i=2:m- 1
    information(k,bestpath(i*2- 1),bestpath(i*2)) = (1-rou)*information(k,bestpath(i*2- 1),bestpath(i*2))+rou*cfit;
end
    
    
for kk=1:1:100kk [path,information]=searchpath(n,m,information,z,starty,starth,endy,endh); % path find fitness=CacuFit(path); % crossover.simulation [newbestfitness newbestindex] = min (fitness); % optimum fitnessifnewbestfitness<bestfitness bestfitness=newbestfitness; bestpath=path(newbestindex,:); end Best=[Best;bestfitness]; % % Update pheromone ROU =0.2;
    cfit=100/bestfitness;
    k=2;
    for i=2:m- 1
        information(k,bestpath(i*2- 1),bestpath(i*2)) = (1-rou)*information(k,bestpath(i*2- 1),bestpath(i*2))+rou*cfit;
    end
    
    
end

for i=1:21
    a(i,1)=bestpath(i*2- 1);
    a(i,2)=bestpath(i*2);
end

k=1:21
figure(1)
x=1:21;
y=1:21;
[x1,y1]=meshgrid(x,y);

%surf(x1,y1,z,'linestyle'.'none')
mesh(x1,y1,z)
load data z information 
axis([1.21.1.21.0.2000])


[x0,y0]=meshgrid(1:0.1:21);
z0=interp2(x,y,z,x0,y0);

mesh(x0,y0,z0)
axis([1.21.1.21.0.2000])
xlabel('km')
ylabel('km') %path finding %n: number of paths m Number of planes Information: Pheromone Z altimeter %starty Starth Starting point %endy Endh End point %path Path finding function [path,information]=searchpath(n,m,information,z,starty,starth,endy,endh) ycMax=3; % horizontal maximum change hcMax=3; % vertical maximum variation decr=0.9; % decay probabilityfor ii=1:n
    path(ii,1:2)=[starty,starth]; oldpoint=[starty,starth]; % Current coordinate pointfor k=2:m- 1% Calculate the corresponding fitness values of all data points kk=1;
        for i=-ycMax:ycMax
            for j=-hcMax:hcMax
                point(kk,:)=[oldpoint(1)+i,oldpoint(2)+j];
                if (point(kk,1) <20)&&(point(kk,1) >0)&&(point(kk,2) <17)&&(point(kk,2) >0)
                    qfz(kk)=CacuQfz(point(kk,1),point(kk,2),oldpoint(1),oldpoint(2),endy,endh,k,z);
                    qz(kk)=qfz(kk)*information(k,point(kk,1),point(kk,2));
                    kk=kk+1;
                else
                    qz(kk)=0;
                    kk=kk+1; Sumq =qz./sum(qz); pick=rand;while pick==0
            pick=rand;
        end
        
        for i=1:49
            pick=pick-sumq(i);
            if pick<=0
                index=i;
                break; end end oldpoint=point(index,:); % Update pheromone information(k+1,oldpoint(1),oldpoint(2=))0.5*information(k+1,oldpoint(1),oldpoint(2)); % Path save path(ii,k*2- 1:k*2)=[oldpoint(1),oldpoint(2)];       
    end
    path(ii,41:42)=[endy,endh]; Function fitness=CacuFit(path) [n,m]=size(path);for i=1:n
    fitness(i)=0;
    for j=2:m/2
        fitness(i)=fitness(i)+sqrt(1+(path(i,j*2- 1)-path(i,(j- 1) *2- 1)) ^2+(path(i,j*2)-path(i,(j- 1) *2)) ^2) +abs(path(i,j*2)); %nowy,nowh: now %endy,endh: end %oldy,oldh: last %k: current layer %z: terrain height map function QFZ = CacuQfz (nowy nowh, oldy, oldh, endy, endh, k, z) % point is feasibleif z(nowy,k)<nowh*200
    S=1;
else
    S=0;
end
 ldh*0.2-nowh*0.2) ^2+(nowy-oldy)^2) +sqrt((21-k)^2+(endh*0.2-nowh*0.2) ^2+(nowy-oldy)^2));

 


qfz=S*M*D;



    


%}
kk=1:0.1:21;
xx=interp1(x,k,kk);
yy= interp1(y,a(:,1)',kk);
zz=interp1(x,a(:,2)',kk);

for i=1:length(xx)
 
    plot3(xx(1:i),yy(1:i),zz(1:i)*200.'--or')
    
    pause(0.1);
end

hold off;

figure(2)
plot(Best)
title('Trends in optimal individual fitness')
xlabel('Number of iterations')
ylabel('Fitness value')

Copy the code

4. Operation results

Matlab version and references

1 matlab version 2014A

[1] Yang Baoyang, YU Jizhou, Yang Shan. Intelligent Optimization Algorithm and Its MATLAB Example (2nd Edition) [M]. Publishing House of Electronics Industry, 2016. [2] ZHANG Yan, WU Shuigen. MATLAB Optimization Algorithm source code [M]. Tsinghua University Press, 2017. [3] WU Qian, LUO Jinbiao, GU Xiaoqun, ZENG Qing. [4] Deng Ye, Jiang Xiangju. Optimization Algorithm of UAV 3D Trajectory Planning Based on Improved PSO [J]. Journal of Ordnance Equipment Engineering, 201,42(08). [5] Yunhong Ma, Heng Zhang, Legrong Qi, Jianliang He. Trajectory Planning Algorithm of quadrotor UAV based on improved Artificial Potential Field Method [J]. Sensors and Microsystems, 201,40(07) [5] 3d uav path planning based on improved A* algorithm [J]. Electronics optics & control, 2019,26(10) [6] jiao Yang. Research on 3d path planning of uav based on improved ant colony algorithm [J]. Ship electronic engineering, 2019,39(03)