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

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

随着科技的发展，移动机器人在农业机械，智能交通还有智慧城市等领域都有不凡的表现，而机器人的路径规划是学术界研究的一个热点及难点问题。路径规划简单来说，就是设定起点与终点两个点， 通过智能算法在可行路径上规避障碍物，获得一个安全无碰撞，距离最短的路径。常用的评价指标有规划路径的长短信息，用时大小以及拐角频率等[1] [2] [3]。另外，还可以从面对的场景，环境信息的不同， 分为全局路径规划和局部路径规划[4]。全局路径规划主要使用的是静态地图，在先验信息已知的情况下规划路径， 常见的算法有传统算法包括Dijkstra 算法[5]、A*算法[6] [7]等， 智能算法包含粒子群优化算法， 蚁群算法，遗传算法等。而局部路径规划面对对象通常为动态环境，在环境完全未知或者部分已知的前提下，基于多传感器识别局部环境，形成实时路径规划，常用的算法有动态窗口法(DWA)，人工势场法(APF)，模糊逻辑法(FL)等。

文献[8]使用A*算法解决了AGV 无冲突路径规划问题。文献[9]将A*算法应用到了农业场景中，提高了采摘机器人的工作效率和控制精准度。张超等人[10]运用Dijkstra 算法思想，在输电线路选线方面发挥了作用。以上文献均涵盖了全局路径规划思想，涉及不同的领域，因此，对两种经典全局路径规划算法展开研究显得尤为重要。

2. 全局路径规划 全局路径规划是导航功能中重要的一环，导航包中常常出现，导航包调用全局路径规划器，并且是以插件的形式，插件接收全局地图，以及人为设定的起点和目标点等信息，经过算法处理，输出处理好的全局路径信息。

2.1. Dijkstra 算法 本文将通过复现Dijkstra 算法的实现过程，详细地一步一步说明，来体会理解算法的核心思想，即Dijkstra 算法将所有点的最短代价按照由近及远的顺序一一计算。在说明算法之前，需要进行情景假设， 首先确定起始点，行走过程中，一次只能前进一格，不能够越过格子，所以可以得到周围八个相邻的格子。如果走上下左右四个方向的话，计它路程为2。如果走左上、左下、右上、右下，那么就计它路程为3。这里定义两个数组，一个是用来存放待确定路径的点，取名为openlist = [ ]，另一个是用来存放已确定路径的点，取名为closedlist = [ ]。说明一下，在Python 里面是列表，如果在其他语言也可以设置为数组。根据命名规则，每个点通过下标信息都能记录其父节点，在提取路径时一目了然。不走已确定路径的点，即已放进closedlist 的点。为了方便讲解，约定起点为S 点，相邻的8 个点以A~H 来称呼表示