栅格图特征提取下的路径规划建模与应用-AGV吧

1 引言

移动机器人逐渐代替人进行工作，并具有高精度和高效率的优点[1]。机器人综合了机器视觉、机器人导航与定位、模式识别、多传感器融合和人机接口等多种研究领域[2]。AGV 作为一种新型的智能移动机器人，具有自动化程度高、灵活性强、抗干扰能力强、安全性好等优点。路径规划作为 AGV运动中的关键问题之一，成为目前的研究热点。根据已知的环境信息，路径规划问题可分为两类。一个是全局路径规划问题[3]，即在规划之前已经知道所有的环境信息。另一个是局部路径规划问题[4]，机器人必须自己收集环境信息。本文研究的是全局路径规划问题。

全局路径规划问题有两种常用方法。一种是穷举搜索方法，如：Dijkstra[5]、A*算法[6]和图论[7]。该类方法搜索的是整个空间，这意味着它一定可以找到最优解，但执行时间会随着问题的大小成指数增长。为解决上述问题，Akshay 在文献[1]中提出了机器人路径规划的时效 A*算法，它不确定每个节点的启发式函数值，只在碰撞阶段之前确定该值，从而缩短了 A*算法的执行时间；Rui Song[8]认为 A*算法仅限于生成分段线性路径，既不平滑也不连续，使得节点过多不利于智能体的运行，为此提出了一种改进的基于路径点的 A*算法，来平滑 A*算法规划出的路径，减少不必要的节点，使路径更加连续，其本质是在规划出路径后再对路径进行平滑处理，这样，然而在进行路径规划时，往往会增加算法的计算量，影响算法的实时性。

另一种解决全局路径规划的方法是利用启发式算法，它是解决优化问题的一种常用方法。由于路径应该是无碰撞的，并且应该满足一组优化准则，因此路径规划也被认为是优化问题。常用的启发式算法有禁忌搜索法[9]、蚁群算法[10]、遗传算法[11]、粒子群算法[12]等。但这些算法容易陷入局部最优，且计算量较大。为此，Mo[13]将生物地理学与粒子群算法相结合，增加了种群的多样性，避免了局部最优；Lee[14]改变了遗传算法初始种群的生成方式，缩短了寻找最优解所需的时间，加快了算法的收敛速度；Yakoubi M A[15]考虑到转弯次数对智能体的影响，利用遗传算法规划出了一条路径较短转弯次数较少的路径，并说明了这样的路径更有助于智能体的高效运行。

蚁群优化算法(ACO)是一种经典的仿生最优路径规划算法，具有易于与其他算法融合、易于分布式并行计算、全局优化性能好等优点[16]。已有的研究结果表明，蚁群算法在求解复杂优化问题，尤其是离散优化问题方面具有一定的优势。王晓燕[17]将人工势场法与蚁群算法结合，将人工势场法求得的初始路径与节点间的距离综合构成新的启发信息，并引入启发信息递减系数，避免了因启发信息误导而造成的局部最优问题；Lee[18]提出了一种基于异构蚂蚁的路径规划方法，通过改进蚂蚁的转移概率函数和信息素更新规则来直接找到一个节点较少的最佳路径，无需进行后续的平滑处理。

规划节点，即在路径规划过程中算法所需规划的节点，传统的路径规划方法存在着规划节点过多的问题，节点可以分为换向节点和非换向节点，AGV 在实际运行中，由于所规划的路径通常是分段线性路径，AGV 必须停在每个换向节点，根据下一段路径改变其方向，然后再重新启动[19]，因此换向节点的多少对提高 AGV 的运行效率、减少 AGV 的磨损起着重要作用,而当非换向节点过多时，由于在每一个节点处都要对其要到达的节点重新进行计算，算法的计算量会过大，减少路径规划时非换向节点的数目，可以缩小搜索范围，提高搜索效率。

然而，上述文献虽然考虑了节点过多对算法计算量和 AGV 运行效率的影响，但是其改进方法往往是对一般算法规划出路径后再对路径进行平滑处理，这样会使路径规划的过程相对繁琐，不利于其使用。为此，卜新苹[20]利用四叉树法对传统的均匀栅格图进行分割，重新确定栅格之间的连接关系，减少栅格数目，结果表明，减少栅格点能在不影响求解质量的同时，缩小搜索范围，从而提高了算法的收敛速度，减少了规划出的路径中节点的数量。Jihee Han[21]提出了提取临界障碍物和周围点集的方法，该方法根据障碍物对路径规划的重要程度，找到相对重要的障碍物，并在环境中找到包含这些障碍物的栅格点子集，减少了需要考虑的栅格点的数目，从而降低了三维路径规划的复杂性。在不同的障碍物环境下进行的仿真实验表明，该方法提高了三维路径规划的效率，也减少了规划出的换向节点的个数，提高了智能体的运行效率。

利用四叉树法非均匀分割栅格图时针对不同的环境会有不同的四分原则，而且重新确立连接关系时要频繁进行入栈出栈操作，可能会造成数据量过于庞大。而提取临界障碍物和周围点集的方法只适用于一条路径被频繁修改的情况，当要寻找完全不同的另一条路径时，之前非临界障碍物有可能会成为新的临界障碍物，进而影响求解过程。为了能够在减少规划节点的同时不失去算法的广泛适应性，将障碍物的顶点作为节点特征进行提取，并将其作为新的备选点来规划路径，然后采用蚁群算法在新的栅格环境下进行路径规划，以期减少蚁群算法搜索过程中的节点数目，提高算法的收敛速度。