基于遗传算法扫地机器人设计路径规划

2021-04-29周欣沅

中阿科技论坛(中英文) 2021年4期

王浩方露庄奎周欣沅

（江苏海事职业技术学院,江苏南京 211170）

近年来，国家相关部门不断加大对机器人产业的扶持力度。作为服务机器人领域中的新产品，扫地机器人可在无人看守的情况下轻松完成室内环境的吸尘等清洁工作。路径规划对机器人的工作至关重要，不仅能提高其清扫效率，还能将机器人的工作原理广泛应用于各个场景，具有一定研究价值。路径规划是智能扫地机器人导航的关键技术，实时、快捷及安全的运动方式能够事半功倍。因此，本文将对扫地机器人的路径规划进行深入探讨[1]。

全覆盖路径规划即在工作范围内，清扫机器人从初始点开始，找到一条可覆盖全部位置的连续路径，以使机器人的某种性能指标达到最优。全覆盖路径规划算法目前已有很多，主要有随机方法、单元分解法、规划式覆盖算法、模板模型法、神经网络算法、遗传算法等。其中遗传算法在路径规划中具有很强的全局寻优性、环境适应性及运算准确性。

1 路径规划算法

遗传算法（Genetic Algorithm）的基本思想是参照生物界自然遗传机制和自然选择的随机化搜索算法。通过模拟人工种群的进化过程，在选择、交叉及变异中进行迭代，直至其适应度达到近似最优状态[2]。另外，GA作为一种智能优化算法，相对一些普通的优化算法，可以较快获取最佳的结果，其关键步骤为：初始化种群、计算适应度、选择、交叉和变异。

1.1 环境模型的建立

在对扫地机器人的路径规划前，首先建立其工作区域的环境地图。栅格法是地图建模的常用方法，定义0代表自由区域，1代表障碍区域。栅格大小的设定会直接决定规划算法的性能。栅格越小，环境信息分辨率越高，但数据量及噪声会增大，并会降低规划速度及算法性能；反之，栅格较大，存储信息量越少，提高了算法速度，但降低了环境信息分辨率。

1.2 环境编码

将数学中的微元化处理思想应用于扫地机器人的路径规划中，机器人的运动轨迹T就被划分成由直线段拟合而成，转换成数学表达式即为：

由于扫地机器人在运动过程中是具有方向性的，那么在实际运算中应将基本距离单位适量化处理，假设起点为O，终点为P，则数学表达式为：

扫地机器人经过的每一个位点被运算后，就能获取到其所工作环境的路径，建立扫地机器人在工作空间中位置的集合，即：

将路径轨迹T利用坐标点数据进行储存，利用二维平面坐标确定当前路径轨迹中扫地机器人的具体位置，再依据遗传学原理将路径进行确定的方式称为染色体的编码。在实际的路径规划中，机器人的路径统计可以通过多次操作和运算来完成。

1.3 适应度函数的选择

个体适应度函数值的大小是遗传算法中区分个体优劣的重要指标，从生物学层面来讲，相当于“适者生存”的能力，而此能力正是由个体适应度的大小来决定的。所以，算法的收敛性及收敛速度取决于适应度函数的选取。常见的适应度函数如下：

（2）求解极大值问题时，令：

其中Cmin为的最小值估计。

求解极小值问题时，令：

其中Cmin为的最大值估计。

（3）求解极大值问题，适应度函数通过转换得到：

求解极小值问题，适应度函数通过转换得到：

1.4 算法步骤

扫地机器人的路径规划可以归纳为：按照某种优化指标，在起始点和目标点规划出一条与环境障碍无碰撞的路径，并且实现所需清扫区域的合理完全路径覆盖。遗传算法的运算过程如下：

（1）初始化：群体的初始化由随机方式产生；

（2）个体评价：通过个体适应度函数值来评价；

（3）选择运算：在个体适应度评估的基础上，对群体建立选择算子运算；

（4）交叉运算：在个体适应度评估的基础上，对群体建立交叉算子运算；

（5）变异运算：为防止出现未成熟收敛现象，对群体建立变异算子运算；

（6）迭代终止判定：满足终止条件时，产生的最大适应度个体即为最优解，计算结束，否则返回至第二步。

在整个进化过程中，个体在选择运算中是否被选中是由个体适应度的大小来决定的[3]。适应度大的个体被遗传的概率也就越大，反之亦然。通过比例选择来判定个体是否被遗传，而目标数值与个体适应度之间的转换规则需要提前设定好[4]。尤其是要提前设定好当目标数值是负数时的解决办法。执行遗传算法时，需要提前设定四个参数，即：群体大小、变异概率、交叉概率和终止代数。