混合细菌觅食算法求解无人艇路径规划问题

Hybrid bacterial foraging algorithm for unmanned surface vehicle path planning

针对细菌觅食优化算法(BFO)解决水面无人艇路径规划存在的易于陷入局部最优的问题,提出了一种混合模拟退火机制的BFO算法.该算法保留BFO算法的三层嵌套结构,将模拟退火机制引入到BFO算法的迁移操作中,计算更新前后的迁移个体的适值度,并以Metropolis准则接受新解,使BFO算法能更好地从局部极值中跳出.按驱动形式对动态障碍物进行分类,并结合COLREGS规则设计水面无人艇产生对遇、交叉和追越三种情况的避碰策略.仿真结果表明:提出的算法收敛速度快、求解质量高,不仅可以成功地避让静态障碍物,还能高效地规划局部路径.

In order to solve the problem that bacterial foraging optimization algorithm(BFO) is easy to fall into local optimal solution in the path planning of unmanned surface vehicle(USV),an optimization algorithm combining simulated annealing(SA)and BFO was proposed. The three-layer nested structure was preserved by the proposed algorithm,and the simulated annealing mechanism was incorporated into the outermost nested dispersal operator. The fitness of the individual was updated after the temperature iteration.Then the new solution was accepted according to Metropolis guidelines.The proposed algorithm can escape the local extremum effectively.Dynamic obstacles were classified according to the driving form.Combining with the COLREGS,the surface unmanned boat was designed to produce collision avoidance strategies in three situations:encounter,crossing and overtaking. The simulation results show that the proposed algorithm has fast convergence speed and high solution quality. It can not only successfully avoid static obstacles,but also complete dynamic path planning efficiently.