Hybrid Path Planning Algorithm for UAV Trajectory Optimization in Cave Environments

Abstract: This study aims to address the complexity of unmanned aerial vehicle (UAV) path planning in cave environments. The unique characteristics of cave environments, including the presence of flying obstacles, complex U-shaped passages, limited GPS positioning, and complex spatial topology, pose challenges for path planning. In this study, a hybrid path planning algorithm combining the traditional artificial potential field (APF) method and the raccoon optimization algorithm is proposed. Firstly, the APF method is improved to solve the issues of unreachable targets and local minima, ensuring effective UAV navigation towards the target location. Secondly, the raccoon optimization algorithm is introduced to automatically optimize the parameters of the APF method, adapting to the specific requirements of cave environments and enhancing the efficiency and performance of path planning. Experimental results in actual cave environments demonstrate the potential of the proposed hybrid algorithm in cave exploration and environment modeling tasks. However, further research and testing in more real-world scenarios are needed to verify the feasibility and reliability of the algorithm. This study provides an important solution for UAV applications in cave environments, with broad potential value.

Keywords: cave environment, artificial potential field algorithm, raccoon algorithm, trajectory planning

Introduction Underground mines and unknown cave environments are abundant. Mines have numerous empty areas, mining sites, and high-risk passages [1], while caves feature arrangements of flying obstacles and complex U-shaped passages. Both environments face issues such as limited GPS positioning and complex spatial topology. Previous solutions for effectively surveying and exploring underground mines and unknown cave environments involved manually carrying appropriate detection instruments into the interiors. However, such solutions have risks and limitations, such as safety risks, limited access capabilities (human physical limitations), and restrictions on prolonged operations [2]. Rotary-wing UAVs, with their small size, strong hovering performance, and mobility, are ideal devices for underground environment exploration [3-4]. Given the demand for exploration in complex environments like caves, UAV path planning is particularly important. Many researchers have conducted extensive research based on different task requirements, utilizing algorithms such as A* algorithm [5], genetic algorithm (GA) [6], particle swarm optimization algorithm [7], ant colony optimization (ACO) algorithm [8], Rapidly-exploring Random Tree (RRT) algorithm [9], reinforcement learning method [10], and artificial potential field (APF) method [11] to solve various practical problems. For trajectory planning within caves, the focus should be on the UAV's local planning capabilities and obstacle avoidance performance. Compared to other algorithms, the APF method stands out due to its advantages of low computational complexity, real-time performance, ease of control, and excellent obstacle avoidance effect, making it an attractive choice among many algorithms [12]. However, traditional APF methods have limitations, including local minima, unreachable targets, and irrational path planning in multi-target scenarios [13]. To address these issues, researchers have made effective improvements by exploring enhancements to repulsion potential or attraction functions, fusion with other algorithms, and integration with machine learning algorithms, all of which have achieved significant results. In terms of repulsion potential or attraction function enhancements, Reference [14] introduced modifiers into the APF function to improve the efficiency of avoiding fixed obstacles and enable optimal path planning to the target location. Reference [15] proposed a distributed collision avoidance control method based on Improved APF (IAPF) and Voronoi constraints, enabling UAVs to successfully avoid collisions while navigating smoothly. Reference [16] presented a rotating vector-based IAPF that can plan collision-free and efficient obstacle-avoiding trajectories for UAVs. Although the potential field functions designed in the above references achieve obstacle avoidance effects, the relevant parameters in the potential field functions are manually set, requiring multiple iterations to determine more reasonable parameters, which increases the difficulty of debugging. In terms of fusion with other algorithms, Reference [17] combined the ant colony algorithm (AG) with APF to supplement formation path planning, addressing the slow convergence speed of the ant colony algorithm and the local minima problem in APF. Reference [18] combined RRT with APF to solve the local minima problem of APF. Although the above references solve the local minima problem, they do not satisfy the optimality principle of path planning. In terms of machine learning algorithms, Reference [19] associated the black hole potential field with reinforcement learning algorithms to reduce the occurrence of local minima in multi-target scenarios. The results showed that the trained intelligent agent could quickly adapt to scenarios with new obstacles. However, the adaptability of the algorithm needs improvement, as the size of the black hole domain must be defined according to different environments. Reference [20] proposed an auxiliary approach using APF for DQN action selection, introducing a network structure that can output both q values and action distribution, replacing the traditional DQN network structure that only outputs q values. They also proposed the SA-ε-greedy design, allowing the agent to have a certain deviation from APF guidance, accelerating convergence speed and overcoming the drawback of unreachable target points caused by APF. However, B-APFDQN requires gridization of the target space, complicating the path planning problem. Furthermore, when the task space is complex, the strategies obtained by the APF algorithm are more reasonable, which may mislead the agent. It's worth noting that caves have the challenge of obstacles distributed in both the top and bottom directions and complex U-shaped passages. This type of problem requires addressing two issues in the path planning process: 1) how to establish a closed 3D spatial environment constraint model to plan the optimal path (the shortest path under the condition of meeting the flight conditions) in an environment with a single target point; 2) in the above environment, how to achieve local correction capability for static obstacles without interfering with the enclosed environment. This study explores the problem of UAV trajectory planning in caves, and makes the following contributions: 1) an improved APF algorithm based on rotating attractive potential is proposed to effectively solve the issue of local minima in the traditional APF algorithm; 2) the raccoon optimization algorithm is introduced to automatically optimize the parameters of the APF method, adapting to the specific requirements of cave environments and enhancing the efficiency and performance of path planning. The overall structure of this paper is as follows: Section 1 provides a brief review of the relevant background and previous research achievements; Section 2 describes the research environment, constraint conditions, and objective function; Section 3 introduces the trajectory optimization methods, including the improved APF algorithm based on rotating attractive potential and the COA algorithm; Section 4 verifies the feasibility of the proposed improved APF algorithm based on rotating attractive potential and the use of COA to optimize APF parameters in UAV trajectory planning through simulations; Section 5 conducts simulation calculations on cave environments using the proposed hybrid algorithm.

2 Cave Environment Trajectory Planning Problem 2.1 Cave Environment Modeling This study focuses on the optimization of UAV trajectories in known cave environments. In path planning, the first step usually involves discretizing the research space (or search space) to facilitate the application of path planning algorithms. Continuous spaces in the real world are often challenging to handle directly, and discretization transforms the problem into easier-to-process discrete points or states, which can represent the positions of objects, the postures of robots, or specific states of other problems depending on the application domain [25]. The research space in this study is a cave environment with obstacles distributed in both the top and bottom directions and complex U-shaped passages, as shown in Figure 1. The cave environment modeling process is as follows: 1) use 3D MAX software to build a 3D model of the cave; 2) convert the generated 3D cave model into point cloud data and save its faces and vertices; 3) represent the cave environment in MATLAB software. It's worth noting that during the 3D modeling process, the undulating characteristics of the cave terrain must be considered, resulting in a cave environment measuring 450m × 350m × 58m. To facilitate subsequent descriptions and simulations, a ground coordinate system is established with the lowest point of the cave entrance as the origin. Based on the ground coordinate system, a body-fixed coordinate system is established for the UAV, with the U-axis pointing forward, the V-axis pointing to the right, and the W-axis pointing upward, as shown in Figure 2. The coordinates of obstacles and UAV waypoints are described in the geodetic coordinate system.

(a) 3D modeling of the cave environment (b) Point cloud of the cave (c) 3D representation of the cave environment Figure 1 Cave environment modeling (a) Top view of the body-fixed coordinate system for a quadrotor (b) 3D body-fixed coordinate system for a quadrotor Figure 2 Body-fixed coordinate system for a quadrotor

2.2 Problem Description Based on the analysis of the cave environment mentioned above, the trajectory optimization problem for UAVs in cave environments can be summarized as planning the shortest path from the cave entrance to the exit, assuming that the UAV flies at a constant speed. In the proposed method, the generated trajectory is composed of line segments and encoded into a matrix, represented by Equation (1), where each row represents the coordinates of the ith waypoint, and the objective function is represented by Equation (2):

(1)

(2)

The initial constraint conditions are:

(3)

(4)

where represents the distance between two waypoints, represents the maximum track length, represents the flight altitude of the UAV in the ground coordinate system, represents the intersection point of the perpendicular line to the cave floor with the parallel Z-axis passing through the waypoint, and represents the intersection point of the perpendicular line to the cave ceiling with the parallel Z-axis passing through the waypoint.

3 Cave Environment Trajectory Planning Methods 3.1 Traditional Artificial Potential Field Algorithm and Its Limitations 3.1.1 Traditional Artificial Potential Field Algorithm For the optimization problem mentioned above, the use of artificial potential field (APF) method is an effective solution [X]. The basic concept of the traditional APF method is to use virtual potential fields to describe the position information between the UAV and the target location, as well as between the UAV and obstacles [12]. It includes two types of potential fields: 1) attractive potential field, and 2) repulsive potential field. According to the target connection in the virtual potential field, the target point attracts the UAV, while obstacles repel the UAV within their influence range. Before reaching the target point, the UAV maneuvers under the influence of the attractive and repulsive forces. The superimposed potential field of the traditional APF algorithm is represented by Equation (6):

(6)

where represents the superimposed potential field, represents the attractive potential field exerted by the target position on the UAV, represents the repulsive potential field exerted by obstacles on the UAV, and represents the number of obstacles. The attractive potential field function and repulsive potential field function are represented by Equations (7) and (8).

(7) (8)

The attractive function and repulsive function are represented by Equations (9) and (10), and the resultant force is shown in Equation (11).

(9) (10) (11)

where represents the attractive gain coefficient, represents the repulsive gain coefficient, represents the distance between two points, and represents the range of the repulsive force. The attractive force is the negative gradient of the potential field , and the repulsive force is the negative gradient of the potential field . represents the total force exerted on the UAV. It should be noted that when the UAV, target point, and obstacles are aligned in a straight line, there will always be a point where the attractive force and the repulsive force are equal in magnitude but opposite in direction, resulting in a zero total force on the UAV. In this case, the UAV gets stuck in a local minimum [13], causing the UAV to stop moving or endlessly cycle between obstacles, unable to reach the destination. Therefore, the subsequent section proposes an improved method based on a three-dimensional rotation matrix to solve the problem of local minima in APF.