移动机器人全局路径规划仿真研究

Simulation Study of Global Path Planning for Mobile Robots

摘要: 本文将针对全局路径规划进行研究，选取两个最常用到的Dijkstra算法和A*算法进行讲解。首先进行情景假设，规定算法演示的规则，用数字大小表示距离的远近，引入字母A~H，逆时针方向代表目标点的八个方向。然后依据算法的实现原理，判断下一步中心点的选择，Dijkstra算法以到起始点的代价最小为准，而A*算法以起始点到终点的估算路程最短为判断准则。最后，遍历到终点，通过提取父节点信息，得到最短路径信息。仿真实验结果表明，能有效验证算法的实现过程，对比出两种算法的异同点。

Abstract: This paper will study global path planning, and select the two most commonly used Dijkstra algorithm and A* algorithm to explain. Firstly, scenario hypothesis is carried out and rules of algorithm demonstration are stipulated. Numerical size is used to represent the distance, letters A~H are introduced, and counterclockwise direction represents the eight directions of the target point. Then, according to the realization principle of the algorithm, the choice of the next center point is judged. Dijkstra algorithm takes the minimum cost to the starting point as the criterion, while A* algorithm takes the shortest estimated distance from the starting point to the end point as the criterion. Finally, the shortest path information is obtained by extracting the parent node information through traversing to the end point. The simulation results show that the algorithm can be validated effectively and the similarities and differences of the two algorithms are compared.