基于启发式算法的路径寻优问题的研究

2020-08-30 20:28
499

近年来,国内外学者提出了多种算法用于解决移动机器人路径规划的问题,包括蚁群算法、粒子群算法、人工势场法、遗传算法等。蚁群算法的规划性能相对较好,其并行性能够提供很强的抗干扰能力,很大程度上提高了算法的鲁棒性。另外,它还具备很好的可扩展性,这也是它可以在路径寻优技术发挥重要作用的前提。

然而,蚁群算法在路径寻优的实际应用中仍然存在运算效率低、容易出现“早熟”现象、对路径的优化能力不高等缺陷,直接影响了它的可靠性与有效性。如何缩短运算时间、快速收敛和全局搜索以跳出局部最优解是其需要解决的问题。


02

设计内容

(1)对地形环境进行二维栅格环境建模。采用了栅格法对环境进行建模,将复杂的实际地形划分为大小相同的栅格,其中含障碍物的栅格用黑色表示,不含障碍物的栅格用白色表示,通过采用序号法对每一个栅格进行标识。

(2)为了验证基本蚁群算法的有效性,采用迪杰斯特拉算法来对相同环境的地图求取最短路径,通过基本蚁群算法的路径和迪杰斯特拉算法求取的最短路径来验证基本蚁群算法的性能。

(3)针对在大规模环境下,基本蚁群算法的搜寻效率低下,且容易收敛到局部最优路径的情况,在基本蚁群算法的基础上增添了一种惩罚策略,更大程度上增加了最优路径上的信息素,对较差路径上的信息素强度进行了削弱,扩大了最优路径和最差路径上信息素之间的差异,从而提高了蚁群路径的搜索效率。

(4)基于MATLAB软件开发环境设计了基于蚁群算法的路径规划仿真系统,并利用该仿真系统对所提算法进行了大量仿真。


03

设计亮点

(1)同时采用蚁群算法和迪杰斯特拉算法对随机栅格地图进行路径寻优问题的研究,兼顾路径距离和寻优的速度能够迅速有效的从指定起点寻找到一条安全无碰撞的路径到达指定终点。

(2)在传统的基本蚁群算法的基础上,采用一种惩罚策略对基本蚁群算法进行优化,在大规模地图和障碍占比增多的情况下,对比传统的蚁群算法在路径距离和寻优速度上都有一定的提升