基于Dijkstra算法的移动机器人全局避障策略研究

基于Dijkstra算法的移动机器人全局避障策略研究

摘要

在现代社会中，机器人得到了快速发展并在众多领域得到广泛应用。它对国家的工业发展，国防的建设以及大众生活产生了重大的影响，而且影响力越来越大。在环境恶劣的情况下就需要借助机器人的帮助，如灾后搜救，排雷防爆，隧道探索等。那么机器人路径规划就显得尤为重用。

路径规划是移动机器人研究领域的重要内容，也是一种比较典型的优化问题。路径规划目前没有最好的算法可以涵盖所有，路径规划算法应该对规划速度和最优路径有所侧重。目前的使用方法有人工势场法、遗传算法、A-star算法、Dijkstra算法等。

本课题是在静态全局实体环境已知，通过栅格法进行环境建模，重点研究机器人全局路径规划的Dijkstra算法，为机器人寻找一条从初始状态到目标状态的最优无碰撞路径。通过用Mathematica进行仿真实验，可以实现机器人搜索到最优避障路径到达目标点并避开障碍物。

本文着重介绍了移动机器人避障和路径规划中常用到的方法，对其中的栅格法，可视图法。人工势场法和遗传算法进行了详细的分析。本次将移动机器人的运动进行了简化，只分了8个方向的运动。能力有限，没办法对圆弧运动和微小的运动做出深入的分析，本文的成果是对传统算法dijkstra进行深入分析，以离散数学中的图论知识为背景，阐述该算法在实际情况下的运用。从数学的角度进行实际操作。在编程方面依靠计算机软件的通讯接口，将图论中的图通过编写邻接矩阵程序完成绘制。利用mma软件对算法和环境进行了模拟实验。实验结果和分析证明了算法的可行性，此外，充分认识了该算法的缺陷和可改进之处。

在论文结尾对全文进行了总结并对深刻的分析了dijkstra算法的优劣之处，以及适用范围。

关键字：Dijkstra算法；机器人；路径规划；Mathematica；

摘要 2

Abstract 3

一、绪论 4

1.1课题的背景及意义 4

1.2主要研究内容及关键问题 6

1.3论文结构 6

二、路径规划概述 7

2.1路径规划问题的分类及概述 8

2.2环境建模概述 8

2.2.1可视图法 9

2.2.2栅格法 9

三、Dijkstra算法的概述 11

3.1Dijkstra算法基本原理 12

3.2Dijkstra算法思想的数学模型 12

3.3实现流程 13

四、基于Dijkstra算法的全局规划 14

4.1环境建模 14

4.2算法应用 17

五、实验仿真及结果分析 19

5.1仿真实验 19

5.2结果分析 22

六、总结 23

参考文献 24

一、绪论

1.1课题的背景及意义

随着科技水平的提高，机器人有了极速成长并在大量领域得到广泛运用。它对国家的工业发展，国防的建设以及大众生活产生了重大的影响，影响力越来越大。在环境恶劣的情况下就需要运用机器人的能力，例如灾后搜救，排雷防爆，隧道探索等。那么机器人路径规划这个问题成了避障的关键。

路径规划是典型的优化问题，路径规划目前没有最好的算法可以涵盖所有，好的路径规划算法应该对规划速度和最优路径相兼容。目前的使用的算法有人工势场法、遗传算法、神经网络算法、Dijkstra算法等。以下是对人工势场法和遗传算法的论述与分析。

人工势场法是构建一种不存在的力场的方式研究用力的概念使物体产生加速度，从而使得物体自主运动。在实际环境中有探索机器人不是静止状态时，看成为它在人为制造的力场下的运动。引力来源于目标点，机器人和与目标点的连线就是力的方向指向目标点的中心从而产生加速度，使得机器人朝着目标点移动，从而达到终点位置。但是一般情况下，还会存在障碍群对机器人的移动产生阻碍，因此为了使得机器人避开障碍物，设定障碍物对机器人有斥力作用，力作用线为机器人和障碍物的连线方向指向机器人的中心从而产生远离障碍物的力生成加速度，达到避开障碍物避免机器人陷入静止状态导致机器人永远没有机会移动到目标点的位置。在实际环境中，障碍物和目标点共同所产生的合力对移动机器人的移动进行控制。根据万有引力定律，物体之间的距离越小，所产的的力越大。因此，在这力场中，机器人每时每刻所受到合力大小和方向都在改变，

随着而来加速度也随着改变，移动的轨迹通常来说没有过于接近障碍物，相对来说路线平滑。但是有几种情况下会导致机器人的合力为零点，出现死点，让机器人出现静止状态。从而路径陷入僵局，无线循环在原点。在一般情况下，障碍物和目标点之间的空间大距离长，该算法可以满足避开障碍物迅速的到达目标点，因为合力方向始终朝着目标点。在实际环境中，一般存在障碍与目标点相距不远，当这种情况发生时，机器人朝着目标点进发的时候，它也将向障碍物靠近，就会出现它永远无法到达目标点的情况。

为此需要对引力和斥力的大小进行定量分析。引入引力场函数和斥力场的概念，设定斥力将比引力大的多，从而尽可能的避免上述情况的发生，导致局部最优解出现，陷入无限循环的计算之中。该种算法优点是准确寻找目标点的位置，可以在移动的过程中处理数据无需等待算法的结束，运行效率高，计算和移动是可以同步进行的。空间的存储要求不高。其中最为关键的是参数的设定，对于引力场和斥力场都极为重要，一个微小的参数改变，都可能引起路径规划的失败。需要多次的模拟调试，才可以将参数设定为适用于当前环境的，路径不出现局部最优解。十分依赖于实际环境信息。

遗传算法是从自然选择的角度进行淘汰进化的算法，遗传算法的数据库被称为群体。每一个数据称为一个个体，该算法和传统算法相比最大的不同在于，不是从单个的数据值进行搜索求解，而是从整个数据形成的群体开始搜索的，是从大局的观念入手的算法，它仅仅只需对个体的函数值进行分析，就可得出当前群组的平均环境适应度，不需要其他的辅助信息。在搜索的过程中通常不会陷入局部最优解的问题，甚至面对复杂问题时也可使用，在理论上可以找到整体最优解。在遗传算法中，会把目标的函数值转化为适应度这个概念，只有整个群体的平均适应度达到这个适应度就可以停止数据内部的操作。

它采用适者生存的原理，现将每一个数据值转化为对应的适应值，用来评价每一个个体的优劣，对下一步的遗传操作进行分类，通常使用三种操作分别为选择，交叉和变异。

选择的意义为提高群体的平均适应值，它的范围是将当前群体的个体按所占比例生成到新的群体中，所形成的交配个体，即当前群体中生成下一代的群组且还是下一代的构成的部分的中间群体。选择算子的加入并没有形成新的个体，因此在当前群体中没有任何一个个体有改进。接下来是交叉算子，交叉可以生成新的个体，它会将交配群体中任意个体两两配对，产生新的个体，而更新当前群体，这时就会提高平均环境适应度。依靠这种方式接近既定适应度，也就是说它决定了这个群体的全局走向。在交叉算子的使用过程中，还会有交叉出错发生变异的现象。这也是新的群组的组成，但只会有小部分。

变异算子它是该算法的局部体现，及它对遗传算法的局部探索起关键作用。在这两种算子的配合下，就能完成对需探索空间的全领域或者是局部搜索的任务。

但是在解决复杂环境及有效的算法构造上对应的适应度函数和遗传算子等设计方面，存在极大的困难。通常遗传算法的最终收敛时间过长，算法运算速度慢，所占据的时空要求很大，所以对编码和算法的理解以及对算子的构造要求很高。遗传算法的本身是生物群体进化的概念，从整体着手，满足马尔科夫链。群体可以无限的进化下去。实际上存在空间的要求。对与空间的假设也是遗传算法首先要解决的。对于全局的路径搜索问题而言时间是最大的制约因素。

1.2主要研究内容及关键问题

本课题对已知的全局静态环境下，用栅格法建立环境模型，运用dijkstra算法对机器人全局路径规划，为机器人寻找一条给定起始点和目标点的无碰撞路径。并且使用mathematica软件进行仿真实验，对dijkstra算法的有效性和高效性做出评价，以及对规划出来的路径的可行性的判定。

1.3论文结构

本文的主要结构：

第一章：阐述本课题的背景及意义，比较目前了解的常用到的路径规划算法，并提出基于Dijkstra算法对机器人路径规划的问题。

第二章：描述机器人路径规划的问题，介绍环境建模的方法。

第三章：介绍Dijkstra算法，介绍其基本原理和工作流程，描述数学原理和数学模型。

第四章：基于Dijkstra算法的全局规划研究，将Dijkstra算法应用到机器人的避障路径中，采用栅格法对环境进行建模，并描述算法的实施步骤。

第五章：编写程序对其进行仿真实验，并分析实验结果。

第六章：全文综合得出结论。

参考文献

[1] 谭民, 王硕. 机器人技术研究进展. 自动化学报, 2013, 39(7): 963¡972