Joint search method for UAV multiobjective path planning in urban low altitude environment

A joint search method for multiobjective path planning for an unmanned aerial vehicle (UAV) traveling from a starting point (START) to an end point (GOAL) in an urban low altitude environment, the method comprising the steps of:

• (a) constructing a static safety index map (S-SIMap) based on a set of static obstacles (denoted by FORBIDDEN) that are marked on a geographic map containing the starting point and the end point, wherein a lattice of nodes, the nodes each being square, is defined over the geographic map, and the S-SIMap provides a static safety index for the UAV when located at each node in the lattice of nodes, wherein the UAV is deemed located at the node if a center of the UAV is within the node,
• wherein the static safety index map S-SIMap∈RM×N the static safety index S-SIMap[{right arrow over (s)}c] of the UAV centered at {right arrow over (s)}c=(xc,yc) is calculated by
• S-SIMap[{right arrow over (s)}c]=−10 log10(Pr(xc,yc)),
• where Pr(xc,yc)=1−Pr(xc,yc), and
• Pr(xc,yc), representing a risk probability of the UAV centered at (xc,yc), is calculated by the integral of the position probability density on an obstacle area;
• (b) constructing a static cost distribution map (COST) based on both the S-SIMap and a velocity of the UAV, and storing the COST in a memory module of a computer on board the UAV;
• copying the COST and setting a dynamic cost distribution map (D_COST) as equal to COST;
• (c) performing an offline search (OFSA) using the COST to obtain an offline flight path (path) for the UAV from the START to the GOAL according to path=OFSA(START, GOAL, COST);
• storing the path in the memory module of the computer on board the UAV, setting a current flight path to the path, and causing the UAV to fly according to the current flight plan and repeatedly perform the steps (d)-(g) until the UAV reaches the end point;
• (d) running an obstacle detection module of the UAV to detect whether an obstacle unmarked on the geographic map appears within a detection range of the UAV, and outputting a flag, is_detected_new_obstacles, to indicate whether an online search should be activated, wherein the detection range is a circle centered at a current location, current, of the center of the UAV with a radius equal to an airborne sensor detection distance;
• (e) if no unmarked obstacle is detected in step (d), the UAV continuing to fly according to the current flight plan;
• (f) if an unmarked obstacle is detected in step (d), the UAV performing an online search (ONSA) for a replanned flight plan, replan_path, and setting the current flight plan to the replanned flight plan, wherein the online search comprises the following substeps:
• (f1) constructing in real-time a dynamic safety index map wherein the D-SIMap provides a dynamic safety index for any nodes corresponding to the unmarked obstacle detected;
• (f2) formulating a multiobjective path planning problem of joint optimization of flight time and flight safety of the UAV traveling from the current location to the end point;
• (f3) updating the D_COST based on the D-SIMap;
• including some nodes in NEW_FORBIDDEN according to the D_COST;
• (f4) solving the multiobjective path planning problem to obtain the replanned flight path based on the D_COST, and setting the current flight path to the replanned flight path;
• (f5) terminating the online search if the UAV is at the end point or a straight line between the current location and the end point does not appear in the NEW_FORBIDDEN;
• otherwise, repeating from step (f1);
• (g) after step (f) is terminated, performing an offline search to obtain an offline flight path (path) for the UAV from current to the GOAL based on the stored COST according to path=OFSA(current, GOAL, COST), and setting the current flight plan to the generated path.