An Improved Jump Point Search Algorithm for Home Service Robot Path Planning

摘要

When the jump point search algorithm is applied to robot path planning, there are problems such as many redundant path points, large cumulative turning angle and the robot incapable of adjusting its posture at the path point. This paper proposes an improved jump point search algorithm, which checks the connectivity between the previous point and the last point of each original point. It also uses vector cross product to identify the direction of the next path point relative to the current path point. The vector dot product is adopted to calculate the rotation angle of the current path point. Three evaluation indicators, such as the number of path points, the total path length and the cumulative turning angle, are formulated to judge the merits and demerits of the optimized algorithm. The experimental results show that on the map of scene 1, improved jump point search algorithm reduces the path points from 9 to 7, with total path length decreased by about 12%, and cumulative turning angle decreased by about 27%. The improved jump point search algorithm is designed to obtain a shorter final path, a smaller cumulative turning angle, and to able robot to adjust posture at the path point.