关键词: 跳点搜索算法, Ｂｅｚｉｅｒ曲线, 路径规划, 轨迹优化, 无人机平台

Abstract: Although the traditional JPS algorithm reduces the number of expansion nodes during path planning, it needs to find a jump point for each node it generates, which thus increases the number of expansion nodes in the obstacle area, resulting in the time cost of generating nodes and the path cost. And the cost of visiting nodes is higher. To address this problem, this paper proposes an S-JPS algorithm that improves the jump search rules. On the heuristic function: This algorithm introduces distance and direction information. The specific operation is: First multiply the distance between the starting point and the end point by the weight representing the distance information, then multiply the cosine value of the direction of the starting point and the end point by the weight representing the direction information, and finally linearly combine the above two steps. The cost of generating a large number of nodes is reduced. The JPS algorithm uses Manhattan distance or Euclidean distance to estimate the distance from the node to the target node to evaluate the priority of the node and determine the search direction. In contrast, the S-JPS algorithm more accurately describes the distance from the current point to the target. The estimated cost of the point, thereby reduces the time cost, path cost and number of visited nodes. Regarding the node update rules: In order to overcome the difficulty of back-end trajectory optimization, the inflection points have been trimmed to further improve the smoothness of the path. The specific operations are: For all extended nodes (a0, a1,…, aN), if the slopes of the straight lines an-1an and anan+1 formed by adjacent nodes are different, connect nodes an-1 and an+1. If the straight line an-1an+1 does not pass through the obstacle, discard the original an-1an and anan+1, and retain the line segment an-1an+1. The new path obtained by analogy is the path obtained under the node update rule.For the problem that the path planned in the back-end trajectory optimization is not smooth, a trajectory optimization method based on a mixture of Bezier curves and straight lines is proposed to smooth the generated trajectory to make its curvature more continuous and the generated trajectory smoother. This algorithm requires the curvature of the Bezier curve to be continuous with the straight line segment, so the curvature at the connection between the Bezier curve and the straight line segment is 0. Among them, the most important part of using Bezier curve to replace the original straight line segment is the selection of control points, and the selection method of control points is the formula (13) in the text. Through simulation experiment analysis and compared with the JPS algorithm, our results show S-JPS algorithm reduces a large number of visited nodes in the path planning under the same map, and improves the speed of path planning. Finally, the S-JPS algorithm is applied to an dependently built UAV for experiments. Under the same planning task with the same starting point, end point and actual physical environment, the S-JPS algorithm reduceds the path planning time by 98.6% compared to the JPS algorithm. The cost is down by 81.1% and the number of visited nodes by 99.7%, meeting the high demand for real-time path planning of UAVs.