Planning method and system for shortest path

Abstract

The invention discloses a planning method and system for a shortest path. The method comprises the following steps of establishing an initial grid map according to the environmental information, and respectively marking the grid points of the grid map as a starting point, candidate points and obstacle points; traversing the candidate points to calculate the minimum step length from the candidate points to the starting point so as to form a minimum step length matrix graph; and selecting one of the candidate points as an ending point, and performing the recursive traversal through a reverse depth-first algorithm to obtain a shortest path plan from the ending point to the starting point. The method and the system of the scheme are based on a grid map global expansion algorithm, not only solve the problem that the final path is the shortest path, but also greatly reduce the time complexity and the space complexity of the operation.

Description

technical field [0001] The present application relates to a path planning technology, in particular to a planning method and system for the shortest path. Background technique [0002] The main function of global path planning is to find an optimal or near-optimal path from the starting point to the end point on the known static map. The path is generally continuous, smooth, without obstacles, and suitable for direct execution of the global path. Path planning algorithm is the basis of the whole navigation system, and its results provide path information for subsequent local trajectory planning. [0003] Path planning technology is a research hotspot in many fields at present, and has broad application prospects and scientific research value. It has important applications in robot pathfinding, traffic route navigation, artificial intelligence, game design and other fields. Among them, in the path planning scenario based on the grid map, A* and the optimization algorithm of...

AI Technical Summary

Problems solved by technology

[0004] Therefore, this type of algorithm has two deficiencies. On the one hand, due to the addition of heuristic search on the basis of breadth-first search, the feasible path finally selected may not be the shortest path, and the selection of feasible paths is largely Affected by the induction function, the effect of the algorithm cannot be guaranteed

On the other hand, although compared with the breadth-first search algorithm, the calculation amount of this type of algorithm has been reduced, but the calculation amount of this type of algorithm increases exponentially with the complexity of the map. For complex large-scale maps, it will still be disaster of dimensionality

Images