-
摘要:
为更好地解决移动机器人路径规划问题, 改进蝙蝠算法的寻优性能, 拓展其应用领域, 提出了一种具有反向学习和正切随机探索机制的蝙蝠算法. 在全局搜索阶段的位置更新中引入动态扰动系数, 提高算法全局搜索能力; 在局部搜索阶段, 融入正切随机探索机制, 增强算法局部寻优的策略性, 避免算法陷入局部极值. 同时, 加入反向学习选择策略, 进一步平衡蝙蝠种群多样性和算法局部开采能力, 提高算法的收敛精度. 然后, 把改进算法与三次样条插值方法相结合去求解机器人全局路径规划问题, 定义了基于路径结点的编码方式, 构造了绕避障碍求解最短路径的方法和适应度函数. 最后, 在简单和复杂障碍环境下分别对单机器人和多机器人系统进行了路径规划对比实验. 实验结果表明, 改进后算法无论在最优解还是平均解方面都要优于其他几种对比算法, 对于求解机器人全局路径规划问题具有较好的可行性和有效性.
Abstract:In order to better solve the problem of mobile robot path planning, improve the optimization performance of bat algorithm and expand its application field, a bat algorithm with reverse learning and tangent random exploration mechanism is proposed. The dynamic perturbation coefficient is introduced into the position update in the global search stage to improve the global search ability of the algorithm. In the local search phase, the tangent random exploration mechanism is incorporated to enhance the strategy of local optimization and avoid the algorithm falling into local extremum. At the same time, the reverse learning selection strategy is added to further balance the diversity of bat population and local mining ability of the algorithm, and improve the convergence accuracy of the algorithm. Then, the improved algorithm and cubic spline interpolation method are combined to solve the robot global path planning problem, the coding method based on path node is defined, the method and the fitness function for solving the shortest path without collision with obstacles are constructed. Finally, the path planning experiments of single robot and multi-robot system are carried out in simple and complex obstacle environment. The experimental results show that the improved algorithm is superior to other comparison algorithms in terms of the optimal solution and the average solution, which is feasible and effective for solving the robot global path planning problem.
-
近年来随着智能化技术的迅速发展和产业智慧升级的不断推进, 智能移动机器人在越来越多的领域里得到了广泛应用, 如货物搬运、智慧生产、智能生活、异常环境探测、水下作业、太空探索等等[1-2]. 其中, 移动机器人路径规划是机器人研究领域的一项关键技术. 如, 在执行抢险救灾、货物搬运等任务时, 采用较好的机器人路径规划技术可以提高机器人作业效率、减少机器人磨损, 同时也可以节约人力资源, 减小资金投入[3]. 国内外学者已经就移动机器人路径规划问题做了大量的工作并取得了不少成果. 如可视图法[4]、自由空间法[5]、人工势场法[6]、A*算法[7]、深度学习方法[8]、强化学习方法[9]等. 但可视图法的路径是多个直线相连接, 路径不够平滑, 不易找出最优路径. 自由空间法的复杂度与空间中障碍的数量成正相关关系, 故而此方法不适用于复杂障碍空间. 人工势场法存在容易陷入局部最优解和终点不可达的缺点, 而A*算法存在着内存开销大、计算时间长等不足. 深度学习方法存在工作空间不完全可观察且较不稳定的缺点. 强化学习方法在面对复杂环境时, 其状态空间的尺寸会变得非常庞大, 无法在较小资源中实现实时的路径规划. 所以随着环境系统复杂性及任务难度的增加, 传统的路径规划方法难以取得理想的效果. 最近几年, 通过大量的研究和实验发现, 仿生智能优化算法在求解机器人路径规划方面具有独特的优势, 并且多种智能优化算法已经成功应用于路径规划的搜索策略中, 如蚁群算法[10]、人工鱼群算法[11]、遗传算法[12-13]、粒子群算法[14-15]等. 遗传算法容易产生很多含有障碍的无效路径, 影响了算法的效率. 基本的蚁群算法存在搜索时间长, 易于停滞等缺点. 因此, 研究速度更快、环境适应性更强、路径规划更优的算法成为研究者们不断追求的目标.
2010年, 剑桥大学学者Yang[16]提出了一种新型的启发式智能优化算法—蝙蝠算法. 蝙蝠算法是模拟蝙蝠发出和接收超声波来捕食而提出的. 目前, 蝙蝠算法已经在交互测试[17]、反应堆堆芯布置[18]、连续优化问题[19]、车辆路径规划问题[20]、线性天线阵列失效校正[21]等方面得到了实际应用.
目前在机器人路径规划中一般采用圆弧[5, 8]、直线[4, 6-7, 9-15]来分段构造和表示机器人的移动路径, 这样的表示方式使得机器人在移动过程中转折点较多, 欠缺连续平滑性, 出现急停、急转情况时, 机器人移动缺乏可靠性且易造成相关部件损坏. 而三次样条插值方法则是通过一系列基于三次多项式的插值区间, 拟合出一条光滑曲线. 用这种方法产生的机器人路径曲线更为平滑, 可以保证机器人在急停急转时具有更好的动力学特性, 有着直线与圆弧拟合路径无法比拟的优越性. 基于圆弧和直线的这些特点, 本文采用三次样条插值曲线构造和表示机器人移动路径.
为了探索出更好地解决机器人路径规划问题的方法, 改善基本蝙蝠算法易陷入局部极值、寻优精度不高、算法后期收敛速度较慢等缺点, 提高蝙蝠算法的寻优精度和收敛速度, 拓展其应用领域, 本文尝试将蝙蝠算法的优化思想和三次样条插值方法相结合, 从而求解机器人路径规划问题. 首先, 对基本蝙蝠算法进行了改进, 在算法的全局搜索阶段, 引入动态扰动系数, 扩大蝙蝠种群的多样性. 在算法的局部搜索阶段, 对其随机探索方式进行改进, 提高算法收敛精度. 然后, 采用反向学习选择策略, 进一步平衡算法的全局勘探和局部挖掘能力. 最后, 把改进后算法与三次样条插值方法相结合, 定义了以路径结点为基础的编码方式, 构造了以求解移动机器人绕避障碍和最短路径为目标的方法和适应度函数, 求解机器人路径规划问题. 通过在简单和复杂障碍环境、单机器人和多机器人环境下进行的路径规划实验, 测试对比结果表明, 改进算法对于求解机器人全局路径规划问题具有很好的可靠性和有效性.
1. 基本蝙蝠算法
在基本蝙蝠算法中, 每只蝙蝠都被看作是"无质量、无大小"的粒子, 都代表着解空间中的一个可行解. 对于不同的适应度函数, 每只蝙蝠都有相应的函数值. 并通过比较函数值确定当前最优个体. 然后据此更新种群中各蝙蝠的频率、速度、脉冲发射率、响度, 不断迭代进化, 靠近和产生当前最优解, 最终找到全局最优解. 算法中每只蝙蝠的频率、速度以及位置更新式为
$$ \begin{align} & f_{i} = f_{\min } + ( f_{\max } - f_{\min } ) \beta \end{align} $$ (1) $$ \begin{align} & v_{i}^{t} = v_{i}^{t-1}+\left(x_{i}^{t-1}-x_{*}\right) f_{i} \end{align} $$ (2) $$ \begin{align} & x_{i}^{t} = x_{i}^{t-1}+v_{i}^{t} \end{align} $$ (3) 其中, $ f_{i} $表示第$ {i} $只蝙蝠发出的声波频率, $ f_{\max } $和$ f_{\min } $表示频率的最大值和最小值. $ \beta $是在[0, 1] 之间均匀分布的随机数. $ v_{i}^{t} $和$ x_{i}^{t} $分别表示第$ {t} $代第$ {i} $只蝙蝠的速度和位置. $ x_{*} $表示当前最优位置.
一旦蝙蝠发现猎物, 即接近全局最优解时, 便在当前最优个体附近使用局部搜索策略. 此时由生成的均匀分布随机数$ {P} $作为判断阈值, 如果$ P>r_{i} $ (第$ {i} $只蝙蝠的脉冲发射率), 则使用局部搜索策略, 反之, 则进行全局搜索. 局部搜索的位置更新式为
$$ \begin{equation} x_{\rm new} = x_{\rm old}+\mathcal{E} A^{t} \end{equation} $$ (4) 其中, $ \mathcal{E} $为$ [-1, 1] $上的均匀分布随机数. $ A^{t} $是第$ {t} $代所有蝙蝠响度的平均值. $ x_{\rm old} $为当前最优个体. $ x_{\rm new} $是局部搜索后产生的新个体. 蝙蝠在靠近猎物的过程中, 随着迭代次数的增加, 响度$ A^{t} $逐渐降低. 同时, 脉冲发射速率$ r_{i} $不断增加. 其更新式为
$$ \begin{align} & A_{i}^{t+1} = \alpha A_{i}^{t} \end{align} $$ (5) $$ \begin{align} r_{i}^{t+1} = r_{i}^{0}[1-\exp (-\gamma t)] \end{align} $$ (6) 其中, $ \alpha $和$ \gamma $是常数. 对任意的$ 0<\alpha<1 $, $ \gamma>0 $, 当迭代次数$ {t} $趋于正无穷时, 响度$ A_{i}^{t} $趋于0, 脉冲发射率$ r_{i}^{t} $趋于$ r_{i}^{0} $, $ r_{i}^{0} $是初始脉冲发射率.
2. 具有反向学习和正切随机探索的蝙蝠算法PTRBA
与其他群智能算法一样, 蝙蝠算法在优化过程中, 种群的多样性和算法的深度挖掘能力之间始终存在着矛盾. 对标准蝙蝠算法的改进, 其目的都是希望在加强算法局部搜索能力的同时, 保持种群的多样性, 防止算法在快速收敛的同时出现早熟收敛, 本文改进也是基于这一思想, 即利用正切随机探索机制在加强算法局部开采能力的同时, 依靠动态扰动系数和反向学习选择机制提高蝙蝠种群的多样性, 扩大蝙蝠的搜索范围.下面详细介绍具体改进策略.
2.1 动态扰动系数
基本蝙蝠算法在全局搜索阶段利用式(3)进行位置更新, 其中$ v_{i}^{t} $的求解过程利用$ x_{i}^{t-1}-x_{*} $, $ x_{i}^{t-1} $ $ - $ $ x_{*} $是上一代蝙蝠位置到当前最优位置的距离, 蝙蝠在每次进行全局搜索时, 都要受到这个距离的直接牵引和约束, 这样的方式容易使蝙蝠种群进行全局搜索时跳不出局部最优, 算法极易陷入局部极值. 针对这个问题, 提出了一种动态扰动系数方法, 在式(3)中对上一代蝙蝠位置进行扰动, 改变其位置, 扩大蝙蝠种群捕食的灵活性, 使得蝙蝠的全局搜索能力得到提高. 动态扰动系数$ \sigma $的计算如式(7)所示, 式(3)的改进如式(8)所示.
$$ \begin{align} &\sigma = 1+\cos \left(\frac{-\pi t}{2\times T_{\max }} -\frac{\pi}{2}\right)-\kappa \times \rm {betarnd( )} \end{align} $$ (7) $$ \begin{align} & x_{i}^{t} = \sigma \times x_{i}^{t-1}+v_{i}^{t} \end{align} $$ (8) 其中, $ {t} $是当前迭代次数, $ T_{\max } $是最大迭代次数. $ \sigma $随着迭代次数的增加而自适应减小, 在算法前期对上一代的蝙蝠位置扰动力度较大, 以此减轻$ x_{i}^{t-1}- $ $ x_{*} $对蝙蝠向更广阔范围探索的约束, 扩大蝙蝠种群的搜索范围, 在算法后期对上一代的蝙蝠位置扰动力度较小, 有利于提高算法的深度挖掘能力. $ \kappa $为扰动偏离因子, $ \kappa \in[0.1, 0.9] $经多次实验反复测试当时寻优效果最佳, 本文取值为0.5. $ {{\rm betarnd}}(\, ) $为服从贝塔分布的随机数, 其作用是对递减的$ \sigma $值进行扰动, 进一步增强蝙蝠捕食的灵活性, 增强算法全局搜索的开拓能力.
2.2 正切随机探索机制
蝙蝠种群利用式(4)进行局部搜索, 是以当前最优蝙蝠作为参考, 向外进行随机搜索, 式(4)中的$ \varepsilon $ $ \in $ $ [-1, 1] $, 是一个均匀随机数, 这样的均匀探索方式使算法在局部搜索阶段易陷入盲目状态, 不能较好地体现局部搜索的挖掘能力. 针对这个问题受柯西分布函数[22]的启发, 利用式(9)对算法在局部搜索阶段的随机方式进行改进
$$ \begin{equation} x_{\rm new} = x_{\rm old}+A^{t} \times \tan \left(\pi \times\left(r-\frac{1}{2}\right)\right) \end{equation} $$ (9) 其中, $ {r} $是$ [0, 1] $上的均匀分布随机数, $ \tan (\pi (r-\frac{1}{2})) $的值有两个分布特征: 1) 主要分布在0左右; 2)会有极少一部分数值较大的数. 特性1使蝙蝠种群在当前最优值附近搜索, 增强算法局部开采能力, 特性2使算法更容易跳出局部极值, 从而使蝙蝠算法的局部寻优机制更具策略性, 而不只是盲目地随机探索.
2.3 反向学习选择策略
Tizhoosh在文献[23]中给出反向学习的定义如下.
定义1. 若$ {x} $是定义在实数集$ {\bf R} $上的一个区间$ [a, b] $的一个实数, 即$ x \in[a, b] $, 则$ {x} $的反向解$ x_{1} $定义为
$$ \begin{equation} x_{1} = a+b-x \end{equation} $$ (10) 定义2. 若$ P(x_{1}, x_{2}, \cdots, x_{n}) $是$ {n} $维空间上的一个点, $ x_{1}, x_{2}, \cdots, x_{n} $为实数, 且$ x_{i} \in[a_{i}, b_{i}] $, 则其反向解定义为
$$ \begin{equation} x_{i}^{*} = a_{i}+b_{i}-x_{i}, \ \ \, i = 1, 2, 3, \cdots, n \end{equation} $$ (11) 结合上述两个定义, 把反向学习策略运用到蝙蝠算法的进化机制中, 把$ P(x_{1}, x_{2}, \cdots, x_{n}) $看作是蝙蝠位置, 依据定义2得到其反向解, 比较原蝙蝠位置和其反向解的适应度函数值, 若反向解的适应度函数值优于原蝙蝠位置的适应度函数值, 则用反向解代替原蝙蝠位置. 反向学习选择策略的引入, 增强了蝙蝠种群的多样性, 进一步解决了基本蝙蝠算法易陷入局部最优的不足, 更好地平衡了算法的全局搜索和深度挖掘能力.
3. PTRBA基于三次样条插值实现机器人路径规划
三次样条插值是一种分段式插值方法, 通过一系列基于三次多项式的插值点区间, 形成一条光滑曲线. 用三次样条插值方法拟合出的机器人移动路径曲线更加平滑, 这样可以保证机器人在急停或急转时有较好的动力学特性, 具有用直线与圆弧拟合移动机器人路径无法比拟的优点. 本文将三次样条插值方法融入改进蝙蝠算法PTRBA (A bat algorithm with dynamic perturbation, tangent stochastic exploration and reverse learning selection mechanism)中, 用于求解机器人全局路径规划问题.
3.1 三次样条插值
设在区间$ [a, b] $上取$ n+1个 $结点$ a = x_{0}<x_{1}<\cdots < x_{n} = b $, 给定这些结点的函数值$ f(x_{i}) = f_{i} $, $ i $ $ = $ $ 0, 1, 2, \cdots, n $, 若$ s(x) $满足条件:
1) $ s(x) \in C^{2}[a, b] $;
2) $ s(x_{i}) = f_{i} $, $ i = 0, 1, 2, \cdots, n $;
3) 在每个小区间$ [x_{i}, x_{i+1}] $上, $ s(x) $是三次多项式.则称$ s(x) $为三次样条插值函数.
三次样条插值函数是分段三次多项式, 在每个小区间$ [x_{i}, x_{i+1}] $上可以写成: $ s(x) = a_{i} x^{3}+b_{i} x^{2}+ $ $ c_{i} x+ d_{i} $, $ i = 0, 1, 2, \cdots, n-1 $. 其中, $ a_{i} $, $ b_{i} $, $ c_{i} $, $ d_{i} $为待定系数, 所以, $ s(x) $共有$ 4n $个待定系数. 为了确定$ s(x) $, 必须有对应的$ 4n $个条件. 由$ s(x_{i}) = f_{i} $, $ i $ $ = $ $ 0, 1, 2, \cdots, n $可知$ n+1 $个插值条件, 由$ s(x) \in $ $ C^{2}[a, b] $可知, $ s(x) $在区间$ [a, b] $上二阶连续可导, 可导必连续, 所以, $ s(x) $的导数在区间$ [a, b] $上必然连续, 那么在$ n-1 $个插值点处也必然连续, 即$ s_{-}^{\prime \prime}(x_{i}) $ $ = $ $ s_{+}^{\prime \prime} (x_{i}) $, $ i = 1, 2, \cdots, n-1 $, 共$ n-1 $个条件. 既然$ s(x) $二阶可导, 则$ s(x) $必然一阶可导且$ s(x) $连续, 可导必连续, 可知:
$$ \begin{align*} &s_{-}^{\prime}\left(x_{i}\right) = s_{+}^{\prime} \left(x_{i}\right), \; \; i = 1, 2, \cdots, n-1 \\&s_{-}\left(x_{i}\right) = s_{+}\left(x_{i}\right), \; \; i = 1, 2, \cdots, n-1 \end{align*} $$ 可得$ 2(n-1) $个条件. 到此为止, 共有$ 4n-2 $个条件. 再补充两个边界条件就可以确定$ s(x) $, 常用的边界条件有以下3种:
1) 给出两个端点处的一阶导数值;
2) 给出两个端点处的二阶导数值;
3) $ s(x) $是以$ b-a $为周期的函数.
3.2 编码
由上可知, 三次样条插值是一种分段式插值方法, 段与段之间的交接处, 称为路径结点. 段与段之间的样条是不同的, 而整个样条曲线则是一阶连续的, 且在路径结点处二阶连续, 因此, 分段样条之间的方向也可能不同, 路径结点就代表了整个路径的最大转向次数. 即使在非常复杂的环境下, 一般经历3 $ \sim $ 5次转向就能绕开所有障碍物. 依此, 本文以一条路径上的所有结点作为一个蝙蝠个体的编码. 也就是说, 一个蝙蝠个体代表了对应路径上的所有路径结点, 即一条路径上所有$ m $个路径结点的横坐标集合构成了蝙蝠个体的$ m $维横坐标, 相应地, 一条路径上所有$ m $个路径结点的纵坐标集合构成了蝙蝠个体的$ m $维纵坐标.
假设已知$ m $个路径结点的坐标$ (x_{m 1}, y_{m 1}) $, $ (x_{m 2}, y_{m 2}), \cdots , (x_{m m}, y_{m m}) $以及起点和终点的坐标$ (x_{s}, y_{s}), (x_{t}, y_{t}) $. 在区间$ (x_{s}, x_{m 1}, x_{m 2}, \cdots $, $ x_{m m} $, $ x_{t}) $和$ (y_{s}, y_{m 1}, y_{m 2}, \cdots, y_{m m}, y_{t} ) $上, 通过三次样条插值得到$ n $个插值点的横坐标$ (x_{1}, x_{2}, \cdots, x_{n}) $和纵坐标$ (y_{1}, y_{2}, \cdots, y_{n}) $. 此时, 得到了$ n $个插值点. 由路径结点和插值点以及起点和终点组成的连线就是我们要求得机器人的路径.
3.3 构建适应度函数
机器人路径规划要满足两个条件: 1) 不能与障碍物发生碰撞; 2) 路径长度要尽可能短. 本文就以满足上述条件的无碰撞的路径长度最短作为适应度函数的评价标准.
本文构造的适应度函数为
$$ \begin{equation} z = L (1+\varpi \times \eta) \end{equation} $$ (12) 其中, $ \varpi $是一个足够大的数, 用以排除通过障碍物区域的路径, 这里取值为100. $ L $是机器人从起点到终点的路径长度, 其计算式为
$$ \begin{equation} L = \sum\limits_{i = 1}^{n} \sqrt{\left(x_{i+1}-x_{i}\right)^{2}+\left(y_{i+1}-y_{i}\right)^{2}} \end{equation} $$ (13) 其中, $ \left(x_{i}, y_{i}\right) $为第$ i $个插值点的坐标.
$ \eta $是一个标志变量, 其初始值设置为0. $ \eta $的求值过程为
for $ k = 1: nobs $
$$ \begin{align} &\quad\; \; \; \; \; d_{k} = \sqrt{\left(x x-x o b s_{k}\right)^{2}+\left(y y-y o b s_{k}\right)^{2}} \end{align} $$ (14) $$ \begin{align} &\quad\; \; \; \; \; \theta_{k} = \max\left(1-\frac{d_{k} }{{robs}}, 0\right) \end{align} $$ (15) $$ \begin{align} &\quad\; \; \; \; \; \eta = \eta+\operatorname{mean}\left(\theta_{k}\right) \end{align} $$ (16) end
为了计算方便, 可将障碍物设置为圆形表示, $ nobs $是障碍的总个数, $ xx $为一条路径上所有插值点横坐标的集合, $ yy $是所有插值点纵坐标的集合. $ (x o b s_{k} $, $ y o b s_{k}) $为第$ k $个障碍的圆心坐标, $ r o b s_{k} $为第$ k $个障碍的半径. 式(14)是为了求出一条路径上所有插值点到第$ k $个障碍圆心的距离, 这个距离称为$ d_{k} $. 式(15)是为了判断路径是否经过第$ k $个障碍, 若路径经过第$ k $个障碍, 则集合$ \theta_{k} $中必存在有大于0的数. 若路径没有通过任何一个障碍, 则集合$ \theta_{k} $中的数都是0. 式(16)中$ {\rm mean}{(\theta_{k})} $是集合$ \theta_{k} $中所有数的平均数, $ \eta $是一个累加值, 即$ nobs $个$ \operatorname{mean}(\theta_{k}) $的值相加之和, 若所求得路径没有通过障碍物区域, 则$ \eta = 0 $. 反之, $ \eta $是一个大于0的数.
3.4 算法流程
步骤1. 根据具体环境确定路径结点的个数$ m $, 确定插值点的个数$ n $, 确定机器人的起点$ \left(x_{s}, y_{s}\right) $和终点$ \left(x_{t}, y_{t}\right) $, 确定算法的最大迭代次数$ T_{\max } $, 蝙蝠的种群规模$ npop $, 速度$ v_{i} $, 声波响度$ A_{i} $, 脉冲发射速率$ r_{i} $, 声波频率的最大值$ f_{\max} $和最小值$ f_{\min} $.
步骤2. 初始化蝙蝠位置, 每只蝙蝠位置坐标形如$ [(x_{m 1}, x_{m 2}, \cdots, x_{n m n}), (y_{m 1}, y_{m 2}, \cdots, y_{n m n})] $, $ (x_{m 1} $, $ y_{m 1}), (x_{m 2}, y_{m 2}), \cdots, (x_{m m n}, y_{n m n}) $分别为$ m $个路径结点的坐标. 并利用式(11), 求出其反向解.
步骤3. 利用三次样条插值方法和$ (x_{s}, x_{m 1} $, $ x_{m 2}, \cdots, x_{m m}, x_{t}) $, 求出$ n $个插值点的横坐标$ (x_{1} $, $ x_{2}, \cdots, x_{n}) $. 同理, 可求出$ n $个插值点的纵坐标$ (y_{1} $, $ y_{2}, \cdots, y_{n}) $. 此时, 得出$ n $个插值点的坐标$ (x_{1}, y_{1}) $, $ (x_{2} $, $ y_{2}), \cdots, (x_{n}, y_{n}) $.
步骤4. 利用式(13)计算出路径长度, 即$ n $个插值点之间的距离.
步骤5. 利用式(14)$ \sim $(16)判断此路径是否经过障碍区, 并得出标志变量$ \eta $的值.
步骤6. 利用式(12), 计算适应度函数的值. 同理, 求出其反向解的适应度值.
步骤7. 比较蝙蝠位置和其反向解的适应度值. 若后者小于前者, 则用反向解代替原蝙蝠位置.
步骤8. 利用式(1), (2), (8), (9)分别对蝙蝠位置进行更新, 即得出更新后具有$ m $个路径结点坐标的路径.
步骤9. 重复执行步骤3$ \sim $8, 直到算法达到最大迭代次数.
步骤10. 得到并输出最短路径.
4. 仿真实验与分析
为了验证本文算法在求解机器人路径规划问题上的有效性与可行性, 在保证客观、公正的前提下, 将改进算法PTRBA与标准粒子群算法(Particle swarm optimization, PSO)、基本蝙蝠算法(Bat algorithm)以及文献[24]中提出的改进蝙蝠算法—融合均匀变异与高斯变异的蝙蝠优化算法(Uniform-Gaussian mutation bat algorithm, UGBA)进行实验对比分析, 从而全面检验PTRBA算法的寻优性能.
4.1 实验环境及参数设置
为了保证算法比较的客观和公平, PSO, BA, UGBA, PTRBA算法均采用相同软、硬件平台, 运行环境为Windows7、编程环境为MATLAB R2014a. 仿真实验中, 4种算法的种群规模、最大迭代次数保持一致, 即$ npop = 150 $; $ T_{\max } = 100 $. BA, UGBA, PTRBA算法中的声波响度、脉冲发射速率主要控制着算法的局部搜索能力, 基于公正性, 本文对以上两个参数的设置与基本蝙蝠算法保持一致, 即$ A_{0} = 0.25 $; $ r_{0} = 0.5 $. PSO算法中的学习因子$ c_{1} $, $ c_{2} $分别决定粒子个体经验和群体经验对粒子运行轨迹的影响, 在PSO算法中, 个体经验和群体经验有着同等重要的影响力, 一般设置为$ c_{1} = $ $ c_{2} $ $ = 1.5 $, 本文采用同样的取值.
4.2 单机器人系统的路径规划及算法寻优性能分析
对于单机器人系统, 分别在简单障碍环境和复杂障碍环境下, 进行路径规划对比实验. 在简单环境下, 设置障碍个数为6, 路径结点个数为3. 在复杂环境下, 设置障碍个数为11, 路径结点数设置为4. 两种环境下的插值点个数都设置为100. 其具体实验结果分别如图 1、图 2、表 1和图 3、图 4、表 2所示.
表 1 简单环境下4种算法所求路径长度比较Table 1 Comparison of path lengths obtained by four algorithms in a simple environment算法 最优解 最差解 平均解 PSO 9.0853 9.8596 9.4564 BA 10.9109 13.4622 11.8820 UGBA 9.0346 11.8220 10.0908 PTRBA 8.9638 9.0151 8.9821 表 2 复杂环境下4种算法所求路径长度比较Table 2 Comparison of path length obtained by four algorithms in a complex environment算法 最优解 最差解 平均解 PSO 9.4117 11.0475 10.1180 BA 10.5201 15.3563 12.3124 UGBA 9.4695 13.9027 11.1290 PTRBA 8.8452 9.8183 9.1892 从图 1和图 3中可以直观地看出本文改进算法PTRBA所规划出的机器人路径最短, 尤其是在复杂环境下, 本文算法的求解效果更加明显. 这是因为在全局搜索阶段, 引入动态扰动系数, 增强了蝙蝠飞行的灵活性, 提高算法寻优能力. 如图 2和图 4所示, 算法在前期收敛速度并不是很快, 但在第10代左右时, 算法可以跳出局部极值, 快速向最优解靠近.这是因为在局部搜索阶段, 融入正切随机探索机制, 增强算法的局部开采能力和搜索策略性, 使算法更容易跳出局部极值, 从而提高了算法的寻优精度.如表 1和表 2所示, 是每个算法独立运行30次所得出的路径情况, 可以看出本文算法PTRBA求解出的路径长度无论是最优解、最差解还是平均值都是4种算法中最短的且求解结果非常稳定, 这是因为反向学习策略进一步平衡了算法全局勘探和局部挖掘能力, 是算法所求路径与其他算法相比更加稳定. 总体上, 三种改进机制相互配合, 提高算法收敛速度和寻优能力.
4.3 多机器人系统的路径规划及算法寻优性能分析
与单机器人系统相比, 多机器人路径规划问题更为复杂, 它要求各个机器人之间不能发生碰撞. 为满足此要求, 本文使用了一种基于人工障碍的多机器人路径规划方法[25-26], 该方法可防止各条机器人路径之间出现交叉现象, 从而避免了各个机器人之间可能发生的碰撞. 其具体过程如下:
步骤1. 利用PTRBA和三次样条插值方法, 规划出第1个机器人的路径, 然后, 以此路径上的$ m $个路径结点为圆心, 人工虚拟出$ m $个障碍.
步骤2. 此时, 除了原来环境中障碍外, 又人工虚拟出了$ m $个障碍, 形成了一个新的障碍环境. 在此新环境下, 规划出第2个机器人的路径. 由于第1个机器人的路径上已经人工设置了$ m $个障碍, 所以, 第2个机器人的路径不会与第1个机器人的路径相交. 以此类推, 规划出所有机器人的路径.
本文仿真实验要求为3个机器人规划出无碰撞路径, 每条路径上的路径结点个数设置为3. 分别在简单环境和复杂环境下, 进行对比仿真实验. 在简单环境下, 设置障碍个数为4, 在复杂环境下, 设置障碍个数为9. 两种环境下的插值点个数都设置为100. 其具体实验结果如下:
由图 5$ \sim $8和图 9$ \sim $12可以直观地看出, 本文改进算法PTRBA所规划出的移动机器人路径很少出现不必要的曲折, 这是因为全局搜索阶段的动态扰动系数和局部搜索阶段的正切随机探索机制, 使蝙蝠种群快速向最优解靠近, 算法整体寻优能力得到提高.
表 3和表 4是每个算法独立运行30次得出的路径结果, 可以看出本文改进算法所规划出的每个机器人的路径平均解与所有机器人路径总长度的最优解、最差解及平均解, 都要优于其他三种算法, 这是因为反向学习选择策略的引入, 使算法的全局探索和局部挖掘能力得到平衡, 算法运行过程非常稳定, 进一步验证了本文改进算法和三次样条插值方法相结合求解移动机器人路径问题的可行性和可靠性.
表 3 简单环境下4种算法所求路径比较Table 3 Comparison of path lengths obtained by four algorithms in a simple environment算法 机器人1平均解 机器人2平均解 机器人3平均解 总路径最优解 总路径最差解 总路径平均解 PSO 10.1045 10.4892 11.3857 31.2132 32.6915 31.9794 BA 11.3361 12.4762 12.7646 34.6364 39.3087 36.5770 UGBA 10.9146 11.2058 11.8302 32.6335 35.1046 33.9507 PTRBA 8.9105 9.7747 10.8018 28.4527 29.8305 29.4870 表 4 复杂环境下4种算法所求路径比较Table 4 Comparison of path lengths obtained by four algorithms in a complex environment算法 机器人1平均解 机器人2平均解 机器人3平均解 总路径最优解 总路径最差解 总路径平均解 PSO 10.1527 10.7141 11.3416 30.8667 33.3565 32.2085 BA 11.6525 11.6937 13.2311 35.3250 37.7116 36.5773 UGBA 9.7856 11.8275 12.0380 32.7774 35.0416 33.6512 PTRBA 9.2125 9.6017 10.5695 29.2493 29.7060 29.3837 5. 结论
本文将蝙蝠算法与三次样条插值方法相结合求解机器人路径规划问题. 首先对蝙蝠算法进行改进, 在全局搜索阶段, 引入动态扰动系数, 增强了蝙蝠飞行的灵活性, 提高算法全局寻优能力. 在局部搜索阶段, 融入正切随机探索机制, 增强算法的局部开采能力和搜索策略性, 使算法更容易跳出局部极值. 反向学习选择策略进一步平衡了算法全局勘探和局部挖掘能力, 使算法所求路径与其他算法相比更加稳定. 然后, 以三次样条插值中的路径结点作为蝙蝠个体的编码, 从而把蝙蝠算法和三次样条插值方法与机器人路径规划结合起来, 并据此构建了无碰撞最短路径的方法和目标函数. 最后, 分别在简单环境和复杂环境下对单机器人和多机器人系统进行了路径规划对比实验, 实验结果表明, 基于PTRBA算法和三次样条插值得的机器人路径规划方法的求解性能优于其他对比算法, 验证了改进后算法在规划移动机器人路径方面的有效性和优越性. 下一步将继续改进蝙蝠算法的优化性能, 探索更有效的路径拟合方法, 研究新的启发式智能算法并应用于移动机器人路径规划问题.
-
表 1 简单环境下4种算法所求路径长度比较
Table 1 Comparison of path lengths obtained by four algorithms in a simple environment
算法 最优解 最差解 平均解 PSO 9.0853 9.8596 9.4564 BA 10.9109 13.4622 11.8820 UGBA 9.0346 11.8220 10.0908 PTRBA 8.9638 9.0151 8.9821 表 2 复杂环境下4种算法所求路径长度比较
Table 2 Comparison of path length obtained by four algorithms in a complex environment
算法 最优解 最差解 平均解 PSO 9.4117 11.0475 10.1180 BA 10.5201 15.3563 12.3124 UGBA 9.4695 13.9027 11.1290 PTRBA 8.8452 9.8183 9.1892 表 3 简单环境下4种算法所求路径比较
Table 3 Comparison of path lengths obtained by four algorithms in a simple environment
算法 机器人1平均解 机器人2平均解 机器人3平均解 总路径最优解 总路径最差解 总路径平均解 PSO 10.1045 10.4892 11.3857 31.2132 32.6915 31.9794 BA 11.3361 12.4762 12.7646 34.6364 39.3087 36.5770 UGBA 10.9146 11.2058 11.8302 32.6335 35.1046 33.9507 PTRBA 8.9105 9.7747 10.8018 28.4527 29.8305 29.4870 表 4 复杂环境下4种算法所求路径比较
Table 4 Comparison of path lengths obtained by four algorithms in a complex environment
算法 机器人1平均解 机器人2平均解 机器人3平均解 总路径最优解 总路径最差解 总路径平均解 PSO 10.1527 10.7141 11.3416 30.8667 33.3565 32.2085 BA 11.6525 11.6937 13.2311 35.3250 37.7116 36.5773 UGBA 9.7856 11.8275 12.0380 32.7774 35.0416 33.6512 PTRBA 9.2125 9.6017 10.5695 29.2493 29.7060 29.3837 -
[1] 张立建, 胡瑞钦, 易旺民. 基于六维力传感器的工业机器人末端负载受力感知研究. 自动化学报, 2017, 43(3): 439-447 doi: 10.16383/j.aas.2017.c150753Zhang Li-Jian, Hu Rui-Qin, Yi Wang-Min. Research on force sensing for the end-load of industrial robot based on a 6-axis force/torque sensor. Acta Automatica Sinica, 2017, 43(3): 439-447 doi: 10.16383/j.aas.2017.c150753 [2] 杜义浩, 邱石, 谢平, 郭子晖, 吴晓光, 李小俚. 下肢康复机器人的自适应人机交互控制策略. 自动化学报, 2018, 44(4): 743-750 doi: 10.16383/j.aas.2017.c160128Du Yi-Hao, Qiu Shi, Xie Ping, Guo Zi-Hui, Wu Xiao-Guang, Li Xiao-Li. RAdaptive interaction control for lower limb rehabilitation robots. Acta Automatica Sinica, 2018, 44(4): 743-750 doi: 10.16383/j.aas.2017.c160128 [3] 白天翔, 王帅, 沈震, 曹东璞, 郑南宁, 王飞跃. 平行机器人与平行无人系统: 框架、结构、过程、平台及其应用. 自动化学报, 2017, 43(2): 161-175 doi: 10.16383/j.aas.2017.y000002Bai Tian-Xiang, Wang Shuai, Shen Zhen, Cao Dong-Pu, Zheng Nan-Ning, Wang Fei-Yue. Parallel robotics and parallel unmanned systems: Framework, structure, process, platform and applications. Acta Automatica Sinica, 2017, 43(2): 161-175 doi: 10.16383/j.aas.2017.y000002 [4] Toan T Q, Sorokin A A. Trang V T H. Using modification of visibility-graph in solving the problem of finding shortest path for robot. In: Proceedings of the 2017 IEEE International Siberian Conference on Control and Communications. Astana, Kazakhstan: IEEE, 2017. 1-6 [5] Conn R A, Kam M. Robot motion planning on dimensional star worlds among moving obstacles. IEEE Transactions on Robotics and Automation, 1998, 14(2): 320-325 doi: 10.1109/70.681250 [6] 徐飞. 基于改进人工势场法的机器人避障及路径规划研究. 计算机科学, 2016, 42(12): 293-296 doi: 10.11896/j.issn.1002-137X.2016.12.054Xu Fei. Research on robot obstacle avoidance and path planning based on improved artificial potential field method. Computer Science, 2016, 42(12): 293-296 doi: 10.11896/j.issn.1002-137X.2016.12.054 [7] 张继文, 刘莉, 陈恳. 面向全方位双足步行跟随的路径规划. 自动化学报, 2016, 42(2): 189-201 doi: 10.16383/j.aas.2016.c150432Zhang Ji-Wen, Liu Li, Chen Ken. Omni-directional bipedal walking path planning. Acta Automatica Sinica, 2016, 42(2): 189-201 doi: 10.16383/j.aas.2016.c150432 [8] Pfeiffer M, Schaeuble M, Nieto J, Siegwart R, Cadena C. From perception to decision: A data-driven approach to end-to-end motion planning for autonomous ground robots. In: Proceedings of the 2016 IEEE International Conference on Robotics and Automation. Stockholm, Sweden: IEEE, 2016, 485-501 [9] 张福海, 李宁, 袁儒鹏, 付宜利. 基于强化学习的机器人路径规划算法. 华中科技大学学报(自然科学版), 22018, 46(12): 65-70 https://www.cnki.com.cn/Article/CJFDTOTAL-HZLG201812012.htmZhang Fu-Hai, Li Ning, Yuan Ru-Peng, Fu Yi-Li. Robot path planning algorithm based on reinforcement learning. Journal of Huazhong University of Science and Technology (National Science Edition), 2018, 46(12): 65-70 https://www.cnki.com.cn/Article/CJFDTOTAL-HZLG201812012.htm [10] 王晓燕, 杨乐, 张宇, 孟帅. 基于改进势场蚁群算法的机器人路径规划. 控制与决策, 2018, 33(10): 1775-1781 https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201810006.htmWang Xiao-Yan, Yang Le, Zhang Yu, Meng Shuai. Robot path planning based on improved potential field ant colony algorithm. Control and Decision-Making, 2018, 33(10): 1775-1781 https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201810006.htm [11] 黄宜庆, 彭凯, 袁梦茹. 基于多策略混合人工鱼群算法的移动机器人路径规划. 信息与控制, 2017, 46(3): 283-288 https://www.cnki.com.cn/Article/CJFDTOTAL-XXYK201703005.htmHuang Yi-Qing, Peng Kai, Yuan Meng-Ru. Path planning of mobile robot based on multi-strategy hybrid artificial fish swarm algorithm. Information and Control, 2017, 46(3): 283-288 https://www.cnki.com.cn/Article/CJFDTOTAL-XXYK201703005.htm [12] Sariff N B, Buniyamin N. Comparative study of genetic algorithm and ant colony optimization algorithm performances for robot path planning in global static environments of different complexities. In: Proceedings of the 2016 IEEE International Symposium on Computational Intelligence in Robotics and Automation. Singapore, Singapore: IEEE, 2016. 132-137 [13] Lamini C, Benhlima S, Elbekri A. Genetic algorithm based approach for autonomous mobile robot path planning. Procedia Computer Science, 2018, 127(2): 180-189 https://www.sciencedirect.com/science/article/pii/S187705091830125X [14] Das P K, Behera H S, Panigrahi B K. A hybridization of an improved particle swarm optimization and gravitational search algorithm for multi-robot path planning. Swarm and Evolutionary Computation, 2016, 28(1): 14-28 http://www.sciencedirect.com/science/article/pii/S2210650215001005 [15] Das P K, Behera H S, Panigrahi B K. Intelligent-based multi-robot path planning inspired by improved classical Q-learning and improved particle swarm optimization with perturbed velocity. Engineering Science and Technology, an International Journal, 2016, 19(3): 651-669 http://www.sciencedirect.com/science/article/pii/S2215098615001548 [16] Yang X S. A new metaheuristic bat-Inspired algorithm. Computer Knowledge and Technology, 2010, 284(1): 65-74 http://www.scienceopen.com/document/vid/851e27f2-134f-4d9b-b08e-38bfb7af65ce [17] Alsariera Y A, Majid M A, Zamli K Z. Adopting the bat-inspired algorithm for interaction testing. In: Proceedings of the 8th Edition of Annual Software Testing Conference (SOFTEC Asia 2015). Kuala Lumpur, Malaysia, 2015. 1-4 [18] Kashi S, Minuchehr A, Poursalehi N, Zolfaghari A. Bat algorithm for the fuel arrangement optimization of reactor core. Annals of Nuclear Energy, 2017, 64(2): 144-151 http://www.sciencedirect.com/science/article/pii/S0306454913005148 [19] Chakri A, Khelif R, Benouaret M, Yang X S. New directional bat algorithm for continuous optimization problems. Expert Systems with Applications, 2017, 69(1): 159-175 http://www.sciencedirect.com/science/article/pii/S0957417416305905 [20] 戚远航, 蔡延光, 蔡颢, 黄何列. 带时间窗的车辆路径问题的离散蝙蝠算法. 电子学报, 2018, 46(3): 672-679 doi: 10.3969/j.issn.0372-2112.2018.03.024Qi Yuan-Hang, Cai Yan-Guang, Cai Hao, Huang He-Lie. Discrete bat algorithm for vehicle routing problem with time window. Acta Electronica Sinica, 2018, 46(3): 672-679 doi: 10.3969/j.issn.0372-2112.2018.03.024 [21] Grewal N S, Rattan M, Patterh M S. A linear antenna array failure correction using improved bat algorithm. International Journal of RF and Microwave Computer-aided Engineering, 2017, 27(7): e21119 doi: 10.1002/mmce.21119 [22] Kao C, Tang H C. Symmetry property of multiplicative congruential random number generator in chi-square test. International Journal of Computer Mathematics, 2007, 55(1-2): 113-118 doi: 10.1080/00207169508804367 [23] Tizhoosh H. Opposition-based learning: A new scheme for machine intelligence. In: Proceedings of the 2015 International Conference on Intelligent Agent, Web Technologies and Internet Commerce. Vienna, Austria: IEEE, 2005. 695- 701 [24] 李煜, 裴宇航, 刘景森. 融合均匀变异与高斯变异的蝙蝠优化算法. 控制与决策, 2017, 32(10): 1775-1781 https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201710006.htmLi Yu, Pei Yu-Hang, Liu Jing-Sen. A bat optimal algorithm combined uniform mutation with Gaussian mutation. Control and Decision Making, 2017, 32(10): 1775-1781 https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201710006.htm [25] 强宁, 高洁, 康凤举. 基于PSO和三次样条插值的多机器人全局路径规划. 系统仿真学报, 2017, 29(7): 1397-1404 https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ201707002.htmQiang Ning, Gao Jie, Kang Feng-Ju. Global path planning for multi-robot based on PSO and cubic spline interpolation. Journal of System Simulation, 2017, 29(7): 1397-1404 https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ201707002.htm [26] 叶炜垚, 王春香, 杨明. 基于虚拟障碍物的移动机器人路径规划方法. 机器人, 2011, 33(3): 273-278 https://www.cnki.com.cn/Article/CJFDTOTAL-JQRR201103005.htmYe Wei-Yao, Wang Chun-Xiang, Yang Ming. Path planning method for mobile robot based on virtual obstacle. Robot, 2011, 33(3): 273-278 https://www.cnki.com.cn/Article/CJFDTOTAL-JQRR201103005.htm 期刊类型引用(20)
1. 李高扬,黎向锋,赵康,金玉超,易志东,左敦稳. 全粒子推动野马优化算法的无人机三维路径规划. 系统仿真学报. 2024(03): 595-607 . 百度学术
2. 兰鸿辉,卢海林,乔璐,王倩. 基于力流和有限元法的路径规划. 力学与实践. 2024(05): 956-962 . 百度学术
3. 陈丽芳,杨火根,陈智超,杨杰. B样条技术与遗传算法融合的全局路径规划. 浙江大学学报(工学版). 2024(12): 2520-2530 . 百度学术
4. LIU Dunlong,FENG Duanguo,SANG Xuejia,ZHANG Shaojie,YANG Hongjuan. Simulation of unmanned survey path planning in debris flow gully based on GRE-Bat algorithm. Journal of Mountain Science. 2024(12): 4062-4082 . 必应学术
5. 贾鹤鸣,李永超,游进华,李政邦,饶洪华,文昌盛. 改进沙猫群优化算法的机器人路径规划. 福建工程学院学报. 2023(01): 72-77 . 百度学术
6. 杜传胜,高焕兵,侯宇翔,汪子建. 基于改进双向A~*算法的消防机器人路径规划. 计算机与现代化. 2023(04): 15-19+25 . 百度学术
7. 周鹏,董朝轶,陈晓艳,赵肖懿,王启来. 基于Tent混沌和透镜成像学习策略的平衡优化器算法. 控制与决策. 2023(06): 1569-1576 . 百度学术
8. 张贝,闵华松,张新明. 改进海洋捕食者算法和插值平滑的机器人路径规划. 计算机应用研究. 2023(07): 2082-2089 . 百度学术
9. 于力涵,洪儒,吴宇伦,谢迎娟. 基于IKGC-PSO算法的无人机三维路径规划系统. 计算机测量与控制. 2023(08): 259-266 . 百度学术
10. 赵太飞,容开新,王一琼,李晖. 改进蝙蝠算法的紫外光引导无人机路径规划. 激光技术. 2023(05): 678-685 . 百度学术
11. 黄成,王涛,许家忠. 一种航天器交会与接近路径规划算法. 宇航学报. 2023(08): 1225-1237 . 百度学术
12. 贾鹤鸣,游进华,李永超,李政邦. 改进人工大猩猩优化算法的机器人路径规划. 新乡学院学报. 2023(12): 16-21 . 百度学术
13. 黄霖,符强,童楠. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题. 计算机应用. 2023(12): 3840-3847 . 百度学术
14. 杨光永,戈一航,晏婷,于元滐,徐天奇. 基于调和A*算法在移动机器人中的研究. 现代电子技术. 2022(04): 171-176 . 百度学术
15. 谢勇宏,孔月萍. 基于改进粒子群算法的三维路径规划. 计算机测量与控制. 2022(03): 179-182+191 . 百度学术
16. 刘景森,袁蒙蒙,李煜. 基于改进的樽海鞘群算法求解机器人路径规划问题. 计算机研究与发展. 2022(06): 1297-1314 . 百度学术
17. 郭瑱. 改进ABC算法的图书馆服务机器人路径规划. 信息技术. 2022(12): 19-23 . 百度学术
18. 刘景森,马义想,李煜. 改进鲸鱼算法求解工程设计优化问题. 计算机集成制造系统. 2021(07): 1884-1897 . 百度学术
19. 许德刚,赵萍. 蝙蝠算法研究及应用综述. 计算机工程与应用. 2019(15): 1-12+31 . 百度学术
20. 刘磊,杨鹏,刘作军,宋寅卯. 采用蝙蝠算法进化相关向量机的假肢步态识别. 振动.测试与诊断. 2022(04): 771-776+829 . 百度学术
其他类型引用(41)
-