基于多约束场景的BFO-ACO漫游路径规划

作者：林晓玲王志强郭岩岩朱泽轩来源：《深圳大学学报(理工版)》日期：2022-10-11人气：344

在虚拟漫游中，路径规划是直接影响用户场景探索和沉浸感的关键问题．路径规划目的是在指定起点到终点之间寻找一条最优路径．与其他的路径规划环境不同，漫游环境中不仅要求规划路径最短，还要考虑路径经过景点可见区域的数量、路径的平滑性和路径与障碍物的安全距离等约束条件，这都给漫游路线规划设计带来一定的困难．现有的路径规划算法大多仅关注性能的改进，而常常忽略了多约束条件的影响，不适用于具有多约束条件的漫游环境．因此，针对漫游环境的多约束条件进行路径的评价和规划的研究十分必要．

当前常用的路径规划算法主要有蚁群优化（ant colony optimization，ACO）算法^[1-3]、遗传算法^[4-5]、粒子群算法^[6-7]和A^*算法^[8-9]等．其中，ACO算法^[10]因具有良好的分布式计算能力、强鲁棒性和全局收敛等优点被广泛用于路径规划，但也存在收敛速度慢、易陷入局部最优和死锁的问题，因此也衍生出许多改进算法．JIAO等^[11]通过改进信息素增量使其能够实现自适应更新，提高了算法的运行效率，减小陷入局部最优的可能性．辛建霖等^[12]采用基于ACO算法的多算法融合方式，在搜索初期使用Dijkstra算法初始化路径以提高搜索效率，再用Logistic混沌映射初始化信息素来提高算法的收敛速度，最后采用多选择策略和模拟退火机制提高全局搜索能力．MIAO等^[13]在启发式信息中考虑待选网格距离和目标网格之间的距离，使启发式信息能够自适应调节，并在传递概率中引入障碍排除因子和角度引导因子，从而增加了路径搜索的多样性，提高路径规避能力和搜索效率．CHEN等^[14]在启发式信息中加入A^*算法的估值函数思想，让蚂蚁在连接起始点的直线上找到移动点，从而提高寻找最优路径的准确性．陈志等^[15]通过信息素值非均匀初始化，减少初期搜索的盲目性，用伪随机方式选择路径，强化最优解的引导，同时利用动态惩罚的方法解决死锁问题，提高搜索速度和解的质量．张恒等^[16]针对死锁问题设计了自由寻路-剪枝策略，通过随机选择非障碍物栅格跳出死锁，并将死锁栅格加入禁忌表，以便生成优质路径．孙功武等^[17]采用特殊的回退策略解除死锁，并将死锁栅格储存在全局禁忌表，对整个蚂蚁群体后续的寻路进行约束，从而降低后续迭代中陷入死锁的概率．然而，随着场景约束条件增多和场景规模变大，约束条件之间难以达到平衡，路径的计算成本指数性增长，蚁群算法死锁次数更多，收敛速度慢和局部最优问题更加突出．

本研究根据漫游中对景点有效区域、障碍物距离、路径平滑度和路径长度等多个约束条件，构造评价路线的适应度函数模型，在蚁群算法中引入细菌觅食算法的复制和驱散机制，提出混合细菌觅食优化思想的改进蚁群优化（bacterial foraging optimi⁃zation and ant colony optimization，BFO-ACO）算法．个体蚂蚁根据状态转移规则生成概率来选择移动的邻接点，并根据适应度函数模型实时评价路径的优劣性．在适应度达到一定条件后，对种群中路径适应度最高的蚂蚁进行复制以提高搜索速度，同时淘汰适应度最小的蚂蚁，减少劣质路径对正反馈机制的影响；优化禁忌表更新方式，对陷入死锁状态的蚂蚁进行解锁，提高有效蚁群数量并保持种群多样性；在搜索过程中对搜索蚂蚁进行一定概率的驱散，避免陷入局部最优．

1 多约束环境路径规划

1. 1 地图模型构建

地图模型的构建是路径规划的重要前提，需要将漫游环境抽象为便于计算的模型．本研究采用栅格模型表示地图环境．虚拟漫游环境及其栅格化地图如图1．

图1 （a）虚拟漫游环境及其（b）俯视图与（c）栅格地图Fig. 1 (a) Virtual roaming environment and it's (b) top view and (c) grid map.

栅格地图环境用二进制表示．其中，黑色方格（记为1）表示不能通过区域，如建筑物和障碍物等；白色方格（记为0）是可自由通过区域．为方便查找，栅格内的所有方格采用由左至右，由上至下的顺序进行编码．

1. 2 多约束条件及路径适应度函数模型

一般环境的路径规划常以路径的长度评价路径优劣，路径越短则路径质量越高．漫游环境下的路径要求更高，需权衡多个约束条件后再对路径进行评价．为准确评价路径质量，提出路径适应度函数模型，根据适应度值判定路径的优劣程度．考虑漫游路径的长度、经过景物有效可见区域的数量、路径平滑性和障碍物距离的要求，建立适应度函数模型为

其中，w₁，w₂，w₃，w₄∈[ 0，1]，分别表示4个约束条件的平衡系数；f_i为第i个约束条件的适应度分量．路径长度是评价路径优劣中的关键指标，路径越短，其综合性能越好．路径长度适应度分量为其中， s为路径的步数； i为路径位置指标；（x_i ， y_i）和（x_i-1 ， y_i-1）分别为路径两个连续节点的坐标．路径中景物的可见性决定了体验者的沉浸感．在起点到终点的漫游过程中，漫游中看见的景点越多，体验者的视觉体验感越好．通常来讲，从景点的正面经过更能吸引体验者的注意力，使其不容易感觉到视觉疲劳．因此，景点的正面区域是景点的有效可见区域．将路径经过景点可见区域的平均个数作为路径评价标准之一，经过区域数量越多，路径的适应度值越高．景点可见区域的适应度分量为

其中，N为地图中关键景点的个数；S_n=1表示路径在n景点的可见区域内经过；S_n=0表示不经过．

在漫游过程中，若路径出现急转或多次转弯，会给体验者带来明显的眩晕感，因此路径的转弯幅度应尽可能减小．路径的平滑适应度分量为

其中，∆θ_i为第i步转弯的角度．

沿着路径进行漫游时，若过于贴近某一侧的障碍物，会造成视觉空间不协调．因此，路径的每一个位置与障碍物的最小距离都应该尽可能大，且平均障碍距离越大，视觉协调性越高．路径的障碍物距离适应度分量为

其中，d _av为全局平均最小障碍物距离；d_i为路径在i位置的最小障碍物距离．

2 BFO-ACO算法

2. 1 BFO-ACO算法原理

为解决ACO算法在路径规划中收敛速度慢和易陷入局部最优问题，本研究提出混合细菌觅食优化思想的改进蚁群优化算法．细菌觅食优化（bacte⁃rial foraging optimization，BFO）算法是PASSINO^[18]基于大肠杆菌在人体肠道内的觅食行为提出的新型智能仿生算法，具有快速搜索的特点和较高的优化能力，其关键步骤是趋向、复制和驱散操作．BFO-ACO算法的基本思想是在每次迭代搜索的过程中，计算当前路径的适应度值，当达到设定的阈值时，复制适应度值高的路径，提高最佳路径的搜索速度；多次迭代后，蚁群搜索会集中在几条路径中，此时对路径中某些位置的蚂蚁进行随机驱散，增加路径跳出局部最优的概率．另外，为解决传统蚁群算法的死锁问题，对禁忌表进行优化改进，使蚂蚁根据个体选择概率随机选择邻接点解除死锁，保证算法前期路径的多样性．

BFO-ACO算法基于传统蚁群算法的状态转移规则进行路径搜索，并按照路径的适应度值更新信息素．状态转移规则由每个位置的信息素浓度和距离启发因子决定．因此，从当前位置移动到方向j的概率为

其中，allowed为可移动的方向集合；α和β为正整数，是信息素和启发因子的权重；τ_j为移动到方向j的信息素强度；η_j为移动到方向j的启发式因子，取当前位置到终点距离的倒数．信息素浓度越大，启发式因子越小，则选择该方向的概率就越大．

当所有蚂蚁都到达终点时，即完成1次迭代．此时整个信息素表以固定系数ρ挥发掉一部分，当次迭代产生的路径信息素增加．信息素更新规则如式（7）至式（9）．

其中，t为迭代次数；ρ为挥发系数；Δτ为每次迭代中的信息素增量；Δτ _ij为每次迭代中从i点到j点路径的信息素增量；Δτ _ij ( m )为路径m释放的信息素量；M为蚂蚁的种群数量；F (m)为第m条路径的适应度，且0<F (m)<1；常数Q为信息素总量，路径的适应度越大，留下的信息素就越多． i，j∈path (m)表示路径m经过i点和j点．

2. 2 优化禁忌表解锁策略

ACO算法为避免形成环路和重复路径，在移动策略中使用了禁忌表，但禁忌表策略常使蚂蚁在搜索路径时陷入死锁状态，导致蚂蚁不能到达终点，此路径被标注为无效路径，不更新信息素，这降低了路径的多样性．特别是在规模较大的地图环境下，死锁会导致无效蚂蚁过多，在多次迭代之后才会出现少数有效路径，信息素迅速积累，后续迭代的蚂蚁群体大量集中在此有效路径中，极易导致局部最优解，甚至出现迭代终止之后仍无法搜索到有效路径的情况．为解决此问题，本研究提出优化禁忌表策略进行解锁．禁忌表记录蚂蚁经过的次数，移动时优先选择蚂蚁经过次数为0的邻接点．当所有邻接点禁忌值非0时，表示陷入死锁，此时按照禁忌表次数的倒数生成概率，随机选择邻接点跳出死锁．

图2（a）是蚂蚁在7号栅格发生死锁的示例．此时7号栅格的邻接点禁忌表都记为1，表示在此次迭代中蚂蚁已经过1次．按照禁忌表中记录次数的倒数产生概率进行解锁，则此时7号栅格的所有邻接点的选择概率都相等．假设选择3号栅格解锁并更新路径，如图2（b），此时3号栅格在禁忌表中记为2．继续移动时，优先选择在禁忌表中记录为0的邻接点随机进行移动，即4号和9号栅格，避免了蚂蚁因选择2、7和8号栅格而再次陷入死锁．在图2（c）中，蚂蚁在9号栅格再次陷入死锁时，按禁忌表记数的倒数生成移动选择概率，蚂蚁选择3号栅格跳出的概率比其他邻接点要小，减少了后续搜索中又陷入死锁的概率．因此，在优化禁忌表解锁的策略下，蚂蚁在单次迭代过程中陷入死锁的概率越来越小，从而在保证迭代前期就能找到有效路径，提高了路径的多样性．

图2 死锁解锁步骤（a）第1次死锁；（b）第1次按概率解锁；（c）第2次死锁；（d）第2次按概率解锁Fig. 2 Deadlock unlocking steps. (a) The first time deadlock, (b) the first time unlock by probability, (c) the second time deadlock, (d) the second time unlock by probability.

2. 3 引入复制机制

为提升算法初期的搜索速度，使整体算法快速收敛，本研究引入BFO算法的复制机制．复制操作在寻路过程中的应用如图3所示，黑色圆圈为起点，红色圆圈为终点，①至④是4只蚂蚁的实时搜索路径．在蚁群进行路径搜索的过程中，对每只蚂蚁的当前路径使用式（1）的适应度函数模型进行评价，路径的适应度值越高，该路径是优质路径的概率越高，对优质路径进行复制，增加优质路径的搜索概率．如图3（a），当前时刻路径①适应度值最大，对该路段进行复制，提高路径①的搜索概率．同时为了保持种群数量一致性，淘汰适应度最差的路径③，复制的路径对淘汰的路径进行替换，如图3（b）所示．随后，蚁群如图3（c）所示继续进行搜索．

2. 4 引入驱散机制

当迭代次数较大时，信息素基本集中在一条路径中，若这条路径不是最优路径，蚂蚁却以较大的概率沿着这条路径进行搜索，就难以跳出局部最优解．为使算法具有跳出局部最优的能力，在搜索中加入驱散机制．当邻接点的移动选择概率超过一定的阈值时，对蚂蚁采取随机概率驱散，选择其他邻接点进行移动，从而令每只蚂蚁都有可能跳出局部最优找到更优路径．假设在多次迭代后蚂蚁的最佳路径如图4（a），蚂蚁当前位于A点，其邻接表转移概率如图4（b），此时蚂蚁向B点移动的概率极大，超过了0. 94，陷入局部最优．对蚂蚁进行随机驱散到C点，使驱散后的路径更短，适应度值更大，得到最优解．

图3 BFO-ACO算法的复制过程（a）复制前；（b）复制路径①，淘汰路径③；（c）下一步搜索Fig. 3 Example of the replication process of the BFO-ACO algorithm. (a) Before replication, (b) replication path①and elimination path③, (c) next search.

图4 BFO-ACO算法的驱散过程示例（a）局部最优路径；（b）在A处进行驱散Fig. 4 Example of the dispersion process of BFO-ACO algorithm. (a) The local optimal path, (b) dispersed at A.

2. 5 BFO-ACO算法流程

BFO-ACO算法根据信息素浓度生成状态转移概率，然后通过解锁、驱散和复制等操作扩大路径多样性，加快搜索过程，最后根据路径适应度大小进行信息素更新，进入下一次迭代，重复此过程直至达到最大迭代次数K，最后输出最佳路径．图5是BFO-ACO算法流程图．

图5 BFO-ACO算法流程图Fig. 5 Flow chart of BFO-ACO algorithm

3 仿真及实验

3. 1 实验参数设置

为验证本研究构造的适应度函数模型及BFO-ACO算法在多约束环境中的有效性，使用3种不同规模的静态栅格环境分别为20×20栅格的简单环境、30×30栅格的陷阱环境，以及40×40栅格的多分支复杂环境，各进行50次实验测试，并将实验结果与传统ACO算法、BFO算法和双向ACO^[19]进行比较，所有算法均采用相同的实验参数和适应度函数模型．

实验参数设置：最大迭代次数K=200，群体

规模M=20，信息素挥发系数ρ=0.3，信息素增加强度系数Q=1，驱散阈值P_ed=0.9，状态转移系数α=1、β=1，每个个体解除死锁的次数上限为100次，超过此限值视为无效路径，适应度函数模型的平衡系数w₁=0.63、w₂=0.04、w₃=0.10、w₄=0 . 2 3．漫游路径的质量使用式（1）的适应度函数模型进行评价．

3. 2 实验仿真

3. 2. 1 路径规划结果分析

不同算法在3种不同规模环境下的路径规划结果如图6．其中，蓝色方格表示路径起点，红色方格表示路径终点，黑色方格表示不可行的障碍物，灰色方格为景点可见区域并分块标号，白色和灰色方格都可以自由通行．由图6（a）可见，20×20栅格的简单环境规模较小，有效景点区域比较集中，路径分支较为简单，4种算法规划的路径都比较集中，路径长度、弯折程度和障碍距离相近，BFO和双向ACO算法都经过4个景点区域，BFO-ACO算法经过5个景点，而ACO算法只能经过3个景点区域．由图6（b）可见，30×30栅格的地图环境不仅扩大了规模，还设计了凹陷和绕远陷阱，令寻路环境更复杂．其中，ACO算法的回折现象比较突出， BFO和双向ACO算法则出现不同程度的绕远和凹陷，本研究算法得到的路径相比其他算法，路径更短，弯折更少，且经过的有效景点区域最多．40× 40栅格的地图环境进一步扩大了规模，并设计障碍物均匀分散，从而使寻路过程中分支较多．由于ACO和双向ACO算法在整个迭代过程中极易因陷入死锁而无法得到有效路径，在此环境下对所有算法均采取与BFO-ACO算法相同的优化解锁策略来进行解锁．从图6（c）可见，BFO-ACO和BFO算法都经过3个景点区域且路径的弯折较少，但BFO算法所得路径较长；ACO算法所得路径绕远、弯折多且不经过景点，路径质量较差；双向ACO算法所得路径则出现较多的弯折．

3. 2. 2 迭代收敛曲线分析

图7比较了ACO、双向ACO、BFO和BFO-ACO算法在3种环境下的路径适应度迭代曲线．由图7 （a）可见，在小规模环境中，4种算法都能达到收敛．其中，BFO算法在驱散作用下不断寻找适应度更高的路径，收敛较慢；ACO算法前期无效路径较多，适应度小，在迭代约110次后收敛；双向ACO算法收敛速度较快，迭代约39次就能收敛，这是因为双向搜索加快了蚁群的寻路效率，能够快速积累信息素达到收敛，但所得路径适应度不高，陷入了局部最优情况．BFO-ACO算法在解锁策略下保证了迭代前期能够找到有效路径，从而保证了搜索的多样性，避免了出现局部最优的情况，在复制机制的驱动下快速搜索到较优路径，并及时进行驱散，得到适应度最优的路径，收敛速度快．

图6 （a）20×20栅格的简单环境、（b）30×30栅格的陷阱环境、（c）40×40栅格的多分支复杂规模环境下不同算法的路径规划结果Fig. 6 Path planning results of different algorithms in scale environments of (a) a simple environment for a 20×20 grid, (b) a trap environment for a 30×30 grid, (c) a multi-branch complex environment for a 40×40 grid.

图7 （a）20×20栅格的简单环境、（b）30×30栅格的陷阱环境、（c）40×40栅格的多分支复杂规模环境下不同算法的适应度与迭代次数关系Fig. 7 Iterative curves of adaptability of different algorithms in scale environments of (a) a simple environment for a 20×20 grid, (b) a trap environment for a 30×30 grid, (c) a multi-branch complex environment for a 40×40 grid.

在如图7（b）所示的30×30栅格的规模环境中， ACO算法由于地图规模较大和凹陷陷阱问题，令多数蚂蚁个体陷入死锁无法到达终点，因此在迭代了约25次后才找到第1条有效路径．之后，信息素在这条路径上迅速积累，局部最优情况较为突出． BFO算法的驱散机制可以得到适应度更高的路径，但由于没有信息素的引导作用，驱散的随机性较高，因此仍陷入局部最优．双向ACO算法避免了陷入死锁的无效路径过多的问题，但由于多约束条件的影响，信息素无法集中，适应度难以收敛． BFO-ACO算法在搜索过程中融入复制机制，加强了信息素在较优路径上的积累，可令路径适应度迅速收敛．在迭代到60～70次后，路径选择较为集中，此时启动驱散机制，可进一步提高路径质量，最终在迭代约110次时达到收敛．

在如图7（c）所示40×40栅格的大规模环境中， ACO和双向ACO算法在多分支条件下不断找到适应度相近的不同路径，因此信息素无法在一处积累，这令适应度无法收敛．但是，双向策略可获得比ACO算法质量更好的路径．ACO算法在迭代后期仍会出现单次迭代中无有效路径的情况．BFO算法在大规模环境下驱散作用效果不大，这是由于驱散的随机性导致的．BFO-ACO算法在完成驱散得到较优路径之后，信息素积累帮助迭代收敛，可保持较好的路径质量和搜索速度．

3. 2. 3 性能分析

表1对比了ACO、双向ACO、BFO和BFO-ACO算法在3种环境下的性能．由表1可见，在20×20栅格的环境中，ACO算法路径较长，平均转角大，平均障碍距离偏小；BFO算法的平均障碍距离大，景点数较多，路径长度和平均转角较小，但收敛慢；双向ACO算法运行时间短、收敛快，但路径的各项性能不高．运行时间上4种算法则差别不明显．可见，以上3种算法都无法平衡多个约束条件得到一条最佳的路径，而BFO-ACO算法在路径长度、景点数量、平均转角和平均障碍距离上都能保持较好效果，同时具有较快的运算速度．

在30×30栅格的中等规模环境中，BFO-ACO算法的各项性能依旧保持较好，在迭代至113次时达到收敛．ACO算法虽然收敛速度快，但这是由于该算法的有效蚂蚁数量过少，有效路径出现后搜索变得集中，易陷入局部最优，因而其路径整体质量差，路径适应度值小；BFO和双向ACO算法在搜索过程中易陷入凹陷陷阱，且运行时间长，适应度不收敛，最终得到的路径各项数值都不佳．

表1 不同算法在3种环境的路径规划仿真结果Table 1 Simulation results of path planning for different algorithms in three environments

在40×40栅格环境下，BFO-ACO算法在大规模环境下仍旧可保持较快的运算速度，多项约束性能较为平衡，在路长、景点数和平均转角上的表现都明显比其他算法效果更佳，而平均障碍距离虽略小于BFO和双向ACO算法，但整体路径适应度远大于其他算法，即使在多约束条件的限制下，适应度仍可收敛，而其他算法直至迭代终止仍无法收敛．

结语

提出一种基于多约束漫游环境的BFO-ACO路径规划算法，针对多约束条件构造用于评价路径质量的适应度函数模型，提出优化禁忌表的解锁方案，并将BFO算法中的复制和驱散思想融入路径搜索过程．解锁保证了路径搜索的多样性，以禁忌表中的蚂蚁经过次数生成概率解锁可以逐渐减小死锁发生的概率，提高搜索效率．路径搜索中引入复制机制，提高了算法前期的搜索速度，使算法全局更快收敛．引入驱散机制，使算法能够跳出局部最优，且驱散过程融入到搜索过程，不会增加额外的搜索时间．适应度函数模型在路径搜索过程中对路径的质量进行实时评价，是判断复制的重要评价标准，也是决定信息素更新的关键规则．通过与ACO、双向ACO、BFO算法在不同环境下仿真实验的结果进行比较，验证了BFO-ACO算法的可行性与有效性．

由于BFO-ACO算法是基于栅格地图对路径进行规划，应用到漫游环境中还需要进一步进行曲线平滑处理．因此，未来可针对非规范化地图环境进行研究并得到曲线路径，或者考虑对路径适应度评价模型进行进一步优化．

关键字：优秀论文

上一篇：聚脲微胶囊反应动力学参数及其pH数值法测定
下一篇：面向未知环境的理鞋机器人系统设计与实现

栏目分类

热门排行

推荐信息

期刊知识

基于多约束场景的BFO-ACO漫游路径规划

1 多约束环境路径规划

2 BFO-ACO算法

3 仿真及实验

结 语

栏目分类

结语