# The Improved A* Algorithm for Quadrotor UAVs under Forest Obstacle Avoidance Path Planning
## 2 Materials and Methods
### Comparison Experiments Based on 3D Point Cloud Map of Plantation Forest  
The present study conducted a comparative experiment between the improved A* algorithm and the traditional A* algorithm in various obstacle environments to validate the superiority of the former. However, this experiment alone is insufficient since the actual environment encountered by UAVs during flight within a forest may differ from the map created in a random setting. To address this limitation, this study utilized a real 3D point cloud map of a plantation forest to compare the path planning effectiveness of different algorithms, including the traditional A* algorithm, the improved A* algorithm proposed in the literature [38], the RRT algorithm, and the APF algorithm. Figure 4 illustrates the environment map information and processing flow of the plantation forest map.  
Figure 3: Obstacle environment maps with different numbers of grids: (**a**) grid size 20 \(\times\) 20, start point coordinates (1, 20), end point coordinates (20, 1); (**b**) grid size 30 \(\times\) 30, start point coordinates (1, 30), end point coordinates (30, 1); (**c**) grid size 40 \(\times\) 40, start point coordinates (1, 40), end point coordinates (40, 1); and (**d**) grid size 50 \(\times\) 50, start point coordinates (1, 50), end point coordinates (50, 1).  
As shown in Figure 4a, the point cloud data was obtained from a handheld 3D scanning device of the plantation forest located in Bajia Park, Haidian District, Beijing, The test area was selected using CloudCompare software, and the PassThrough filtering method and RadiusOutlierRemoval were applied to remove the background noise and outliers, respectively [51]. Since the point cloud data was relatively sparse, voxelization was performed to transform the point clouds into an Octomap, which is a three-dimensional map creation tool based on octree, and the plantation forest's 3D reconstruction was completed in ROS [53], as shown in Figure 4b. Subsequently, the two-dimensional grid  
Figure 4: Acquisition and processing process of actual plantation forest map: (**a**) three-dimensional point cloud map of the plantation forest; (**b**) Octomap of the plantation forest; (**c**) grid map of the two-dimensional projection surface of the plantation forest; and (**d**) two-dimensional projection map of the plantation forest after re-rasterization.  
map was obtained by projecting the plane of the plantation forest where the UAV flight height was located, as shown in Figure 4c. This map was discretized into a large number of pixel grids composed of black and white grids, with black representing obstacles and white representing passable areas. The pixel size of the map is 974 \(\times\) 785. In computer science, a binary matrix is usually used to represent this grid map, with the position of each matrix element representing the grid position, the element value of 1 indicating that the position is occupied by obstacles, and 0 representing the unoccupied area. Due to the large number of grids in the obtained two-dimensional map, directly importing it into MATLAB 2022a for use would consume a considerable amount of storage, and path search would require significant computational time. Therefore, on the premise of preserving the location, shape, and size of obstacles in the original map, simple image processing was performed to obtain a real map with fewer grids. As illustrated in Figure 4d, the black outline of the tree trunk intercepted in this plane is considered an obstacle. The two-dimensional map of the plantation forest after re-rasterization was composed of 246 \(\times\) 200 grids, based on the image pixel ratio of the two-dimensional grid map. By setting different start and end coordinates, the performance comparison results of the five algorithms in different complex scenes were obtained.