## 3 Path-Planning Design and Dynamic-Obstacle Avoidance Strategy
### Dynamic-Obstacle-Avoidance Strategy Based on Artificial-Potential-Field Method
#### 3.3.2 Escape Method for Local Optimal Solutions of Artificial-Potential-Field Method  
In the process of drones for path planning, the gravitational force generated by the target point for the drone and the repulsive force generated by the obstacle are equal in size and opposite in direction, that is, the force balance phenomenon at the nontarget point where the drone is. When the search is trapped in a local optimum, it will result in the drone being unable to continue the path planning and eventually fail to reach the target point. In this paper, we classify the cases in which an artificial potential field will produce a local optimum into three types. 1. When the obstacle is directly in front of the target point and the drone is in the same course, and the current drone is subject to gravitational force and repulsive force of the same magnitude and opposite direction, as shown in Figure 12a. 2. When the obstacle is on both sides of the drone and the combined direction of the repulsive force is opposite to the direction of the gravitational force and has the same magnitude, as shown in Figure 12b. 3. When the obstacle is behind the target point and the repulsive force is much larger than the gravitational force, as shown in Figure 12c. When the drone is in a local optimum, the situation is divided into two types based on whether there is direct visibility between the drone and the target point. First, as shown in Figure 12a, the obstacle is between the drone and the target point, and it can be found through the 3D LOS visibility detection that the drone cannot reach directly through the obstacle, and it must be affected by unequal external forces, thus breaking the force balance of the drone. Therefore, in this paper, in the case that the drone is caught in the local optimal solution and there is no direct visibility between the drone and the target point, the virtual-target gravitational field is added around the local optimal point to induce the drone to escape, as shown in Figure 13.  
Figure 12: Artificial-potential-field method falls into the local-optimum case. (**a**) The obstacle is directly in front of the target point and on the same course as the drone. (**b**) Obstacles are on both sides of the drone. (**c**) The obstacle is behind the target point and on the same course as the drone. When the drone is trapped in a local optimal solution but has direct visibility, the 3D Bresenham's Line algorithm can be used to test whether a straight line course between the drone and the target is directly reachable. If a direct route is available between the drone and the target point then the current drone is directly connected to the target point location, as shown in Figure 14.  
Among them, the 3D [PERSON]'s line algorithm plays a key role in driving the local optimal solution and trajectory regression of the drone escape. [PERSON]'s line algorithm  
Figure 14: Escaping Local Optimal Solutions Using the 3D Bresenham’s Line Algorithm. (**a**) Traditional artificial-potential-field method. (**b**) Improved artificial-potential-field method. (**c**) Traditional artificial-potential-field method. (**d**) Improved artificial-potential-field method. Figure 13: Escape local optimal solution using virtual-target gravitational field. (**a**) Traditional artificial-potential-field method. (**b**) Improved artificial-potential-field method. was previously used in bitmap images to determine the raster of pixels through which the line determined between two points passes. [PERSON]'s line algorithm is very effective in 2D grid maps to test for the presence of obstacles between two points, but it is not applicable in 3D stereoscopic space. In this paper, [PERSON]'s line algorithm is further extended in three-dimensional space, and step sampling is used to detect whether two points are directly accessible to each other. The implementation steps are given in pseudocode in this article, as follows (Algorithm 3).