In the obstacle grid map, due to the limitations in search direction imposed by classical path algorithms and meta-heuristic algorithms, the shortest paths are not the true shortest paths (TSPs) but rather the shortest grid paths (SGPs). This paper introduces an SGP vertex extraction and filtering algorithm (SGPVEFA) that identifies key nodes within SGPs. After screening, these nodes yield TSPs under the same conditions. Through various experiments, the shortest path length searched by the SGPVEFA proposed in this paper can be used to search for the real shortest path, and it also has advantages in comparison with recent new algorithms. With the increase in map scale and obstacle rate, the advantages of this path algorithm are more significant.
To address the challenges of high computational complexity, inferior path performance, and the balance between path quality and efficiency in traditional 3D omnidirectional path planning algorithms for UAVs, this study proposes an innovative precision algorithm for solving 3D omnidirectional shortest paths. The algorithm innovatively introduces the concepts of circling path and overpass path, reducing three-dimensional omnidirectional path computation to two-dimensional processing. It designs a three-view obstacle detection algorithm to achieve efficient obstacle avoidance judgment, formulates separate path-solving strategies for discrete and continuous obstacles, respectively, and obtains optimal solutions through recursive adjustments and path optimization. Experimental results demonstrate that compared to A* and Theta* algorithms, our approach achieves shorter path lengths with superior stability; the proposed algorithm achieves a 21.86% reduction compared to RRT*, 10.48% compared to A*, and 0.89% compared to Lazy_Theta*. In addition, the proposed algorithm exhibits enhanced adaptability in high-obstacle environments (particularly irregular obstacles). These findings provide an effective solution for complex spatial path planning in UAV applications.
In the obstacle grid map, due to the limited search directions of classical path algorithms and meta-heuristic algorithms, the shortest paths they solve are not true shortest paths (TSP), but rather shortest grid paths (SGP). In this paper, a SGP vertex extraction and filtering algorithm is proposed to extract and filter the key nodes in the SGP path, so as to obtain the TSP path under the same conditions. Experimental validation shows that the shortest path lengths found by the proposed SGP vertex extraction and filtering algorithm are shorter than those obtained by heuristic path algorithms, and it also outperforms recent new algorithms in comparative experiments. As the map scale increases and the obstacle rate rises, the advantages of this path algorithm become more pronounced.