基于改进模拟退火算法的搬运机器人路径规划

，，，，

(1.苏州科技大学 江苏省建筑智慧节能重点实验室，江苏 苏州 215009; 2.常州工学院 计算机信息工程学院，江苏 常州 213002)

0 引言

近年来，随着计算机技术的迅速发展，移动机器人的研究日新月异。在机器人的研究领域中，常常需要规划出一条行驶轨迹最优、运行代价最少的路线。机器人路径优化算法主要有贪心算法、模拟退火算法、遗传算法、禁忌搜索算法、神经网络及人工势场法等方法。针对模拟退火算法寻优效率低的问题，巩敦卫等人通过引入脱障算子和一致寻优算子，提出了一种状态产生方法[1]。然后该算法的计算复杂度较高。针对基本遗传算法存在收敛速度慢的不足，王雷等人提出了一种改进自适应遗传算法[2]。然而该算法的路径规划准确性不高，容易与障碍物发生碰撞。杜宗宗等人提出了一种遗传模拟退火算法[3]。但忽略了在实际环境中的验证。

针对上述算法中存在的在不同环境下，缺乏普遍适应性的问题。本文通过栅格法建立场地环境，针对机器人移动路径规划，提出了一种改进模拟退火算法，并且通过改变环境系数进行仿真实验，验证了该算法能够适用于不同的环境。

1 基于栅格法的环境建模

本文通过栅格法进行场地环境建模。栅格法将场地环境进行切割，分成一定数量同等大小的方块，每个方块都需要存放对应区域的信息。因此分割的份数越多，对实际场地描述也越精细，但相应的信息存储空间开销增大，并且路径规划难度提高。

障碍物和自由区域由计算机随机生成，但是需要根据机器人一般的工作环境，设定障碍物占据整个环境的比例以及障碍物分布的集中性。障碍物占据比例，在实际环境中是指投影到二维平面上障碍物总体面积占据环境总面积的比例，在栅格图上则是黑色格子数目占总格子数目的比例。障碍物分布的集中性，描述障碍物成块分布的程度。反映到栅格图上就是若干黑色格子聚集在一起情况的多少。

机器人最理想的路线是由起始点Start直接指向终点End。本文参照正态分布刻画上述两种环境因素，且设定在图形中间区域产生障碍物的概率比周边高。用数学语言描述：设定任一格子到环境中心位置的距离为Distance，该格子是障碍物的概率为P，公式(1)中，λ为常系数，λ越大障碍物占据的比例越高，方差项σ调整障碍物集中分布的趋势，σ越小，障碍物越集中在中心区域。

图1是减小σ得到的结果，从图中可以看出障碍物分布具有集中性。但是需要注意，如果λ和σ设置不合理，障碍物过多，会导致Start与End之间没有路径连接。

图1 降低方差的场地栅格图

2 改进模拟退火算法

2.1 基础算法

贪心算法通过每一次选择局部最优解，试图求出整个问题的最优解。这种策略能解决许多问题的整体最优解，但并不能求得所有问题的整体最优解。改进贪心算法在贪心算法的基础上添加禁忌表，记录机器人以往运动中由于“过于贪心”导致无法到达End的格子，具体算法如下。

如图2，假设机器人当前位置为O，A、B、C、D、E、F、G、H八个位置均可作为其下一步到达的位置。首先排除周围的障碍物、边界以及禁忌表(初始的禁忌表为空)中存在的格子。并且A、C、E、G四个斜方向格子需要约束，以A为例，如果机器人要从O到达A，B和H至少有一个不是障碍物。然后计算剩余格子与End的距离，机器人选择结果最小的格子作为下一步。机器人通过每一步修正后最贪心的选择和生成的禁忌表，逐步移动，到达终点。

图2 搬运机器人当前位置示意图

通过仿真，依次派送20个机器人从Start前往End，得到路径图3，其中粗线是最短路径。可以看出，禁忌表信息逐渐完善，机器人陷入“困境”的情况逐次减少。在一定环境条件下，机器人能够通过改进贪心算法到达End。但是可以看出即使进行多次移动，机器人的路径没有太大改变，仅仅是因为禁忌表的更新，有小范围变化。因此，可能无法通过多次实验，找到Start到End的最短路径，从而引入改进模拟退火算法。

图3 改进贪心算法路径

2.2 改进模拟退火算法实现

退火算法来源于材料的统计力学的研究。高温时的粒子包含大量的能量，具备随机运动与重组条件；而低温时，则反之。随着温度逐渐降低(退火)，当温度到达某个点时，粒子处于热平衡状态。随着系统彻底冷却，晶体也完全呈现低能状态。

具体实现如下：机器人在约束条件下计算出最佳选择，不妨设为E点。同时也找到次佳选择，设为F点，在一定概率下机器人放弃选择E点，而选择F点。定义退火系数AcceptLower，公式(2)中X，Y分别为End或O格子中心的横、纵坐标。DistanceO是栅格O中心到End中心的距离，DistanceE和DistanceF同理。公式(3)中常系数k用作调整退火系数，当随机数0～1小于AcceptLower时，机器人做次佳选择。

(2)

(3)

而退火算法收敛速度不够快，因此以退火算法作为基础，并融入遗传算法的思想。遗传算法将优良个体的基因保留，进行两两配对，变异，产生新生代，按此方法逐代进化。机器人利用退火算法产生多组路径，从中选取优良的路径。而这几种路径如果采取“两两配对”，“变异”显然是难以完成的。因为环境中存在障碍物，如果将路径进行随机改动，会存在穿过障碍物的情况，因此需要具体情况具体分析。

基于栅格法建立的环境，对每一个格子建立参数Kij，初值均相等。首先采用退火算法产生若干条路径，在这些路径中挑选出最短的几条。将这几条路径经过的格子参数Kij分别加上不同的常数，这个常数按照排序设定，路径越短对应的常数越大。同时，后续组机器人每一次前往End，同第一组一样更改Kij。不同的是每进行一组，Kij需要略微衰减，以防收敛速度过快，但要求Kij始终大于初值。公式(4)中，KE和KF分别是E和F格子对应的Kij参数。K′是常系数，如果KE>KF，就是在原退火系数的基础上乘以了一个大于1的数，机器人做次佳选择的概率提高。

(4)

2.3 路径长度计算

以图3为例。公式(5)中，Lall是路径总长度，i表示路径上第i个格子，L(i,i+1)是第i个格子与第i+1个格子间的距离。公式(6)给出了计算方法。注意水平垂直方向是二维栅格图上的，并非实际的水平与垂直。

(5)

(6)

3 搬运机器人硬件系统设计

本文选用STM32单片机作为搬运机器人的微处理器。并且添加感知模块、电机驱动模块、无线通信模块、电源模块。电源模块负责给单片机和各个模块供应能量，选用5 V低压电源，如图4所示。感知模块需要颜色传感器和GPS模块，颜色传感器用于检测机器人移动过程中所处环境，分辨障碍物；GPS模块用于机器人定位，在机器人从Start移动到End过程中起到导航的作用；通信模块用于单片机与上位机信息交流，派出的机器人将自己的移动轨迹、总路程、禁忌表等信息上传到上位机，上位机将处理信息后，下位机又进行下载和更新。

图4 搬运机器人实物图

本文设计的搬运机器人在夹持器上进行了改进，如图4所示。最初设计的搬运机器人采用剪刀式夹子夹持货物。改进后更换为一个SG90舵机调整角度的钩子。当机器人检测到货物，调整车身使其与货物良好接触，调整钩子角度使货物与车身固定在一起，改进后的机器人在运输货物时更稳定。

4 实验与分析

4.1 仿真实验

图5是通过贪心算法得到的最优路径(粗线)，长度为45.284 3；图6是改进模拟退火算法中机器人前往End过程产生的多组路径，最优路径(粗线)长度为44.698 5；对比改进贪心算法，改进模拟退火算法不会收敛于局部路径，结果较好。

图5 改进贪心算法

图6 改进模拟退火算法

如果降低公式(1)中方差项σ，即提高障碍物集中程度，得到的新环境下的两种方法仿真图：图7为改进贪心算法结果，最短路径为46.455 8；图8为改进模拟退火算法结果，最短路径为43.112 7，二者差距较大。

图7 改进贪心算法

图8 改进模拟退火算法

根据不同的方差项，各进行100次仿真实验，得改进贪心算法和改进退火算法的最短路径的平均值，如图表1所示。由表1可知，障碍物集中程度越高，即方差项σ越小，改进贪心算法越可能陷入某个固定解，而改进模拟退火算法可以找到较优的最短路径。

表1 不同方差项两种算法的最短路径均值

4.2 硬件平台实验

将本文提出的改进模拟退火算法应用于实际搬运机器人路径规划实验。通过多组实验表明，搬运机器人能够准确地绕过障碍物，并最终在多种路径中找到最优路径。如图9为搬运机器人行驶的最优路径。图9(a)表示机器人从起点出发。图9(b)、图9(c)分别表示机器人在行驶途中。图9(d)表示机器人到达终点。本实验验证了本文提出改进模拟退火算法的可行性，并且能够找到机器人路径的最优解或近似最优解。

图9 实际实验示意图

5 结论

由于传统路径规划算法普遍存在缺乏对环境适应性的问题，本文以改进贪心算法为基础，通过添加遗传算法的思想，最终提出了一种改进模拟退火算法，并分别在模拟环境和实际环境中对算法进行了验证。即使环境中的障碍物分布离散或者集中，本文提出的算法都可以通过一定量的工作找到最优解。此外，将本文提出的算法应用到了自主设计的搬运机器人，取得了2017年中国工程机器人大赛暨国际公开赛一等奖。