基于改进的随机路径图及和声算法的舰船航线规划

Route planning based on improved probabilistic roadmap and harmony search

中文关键词  随机路径图  和声  航线规划  避障

英文关键词  probabilistic roadmap  harmony search  route planning  obstacle avoidance

中文摘要

      针对海上航行中障碍物躲避问题, 提出改进的随机路径图及和声算法为舰船进行航线规划. 该算法首先利 用改进的随机路径图, 在障碍物边缘、起点与终点连线等关键区域进行节点设置及扩充, 根据舰船及障碍物运动特 征, 分阶段在海图上设置节点并连接, 利用较少的节点生成完备的路径网络图, 基于此选择节点生成初始全局航线; 其次利用改进的和声算法对航线进行优化, 障碍物的运动特性导致解空间为复杂的多峰形态, 为避免节点位置变动 导致新生成航线不可行, 设置限定条件, 仅对满足要求的航线利用航线交叉、消除节点、微调等策略进行优化. 实验 结果表明, 相较对比算法, 所提算法能够有效生成更高质量的全局航线, 且在优化过程中生成的不可行航线数量远 低于其余几种算法, 具有更高的可靠性及稳定性.

英文摘要

      Aiming at obstacle avoidance during marine navigation, improved probabilistic roadmap and harmony search are proposed to design routes for ships. The proposed algorithm makes use of an improved probabilistic roadmap at first. It sets and expands nodes around obstacles and the line which connects the starting point and ending point. All nodes are set and connected in phases according to the motion characteristics of obstacles and ships. A complete path network map is generated by making use of a relatively small number of nodes, based on which initial global routes can be generated by choosing nodes. Then the initial global routes are optimized by employing an improved harmony search. The motion characteristics of obstacles result in the multimodal solution space. Slight changes of the nodes can make the new routes unworkable. To avoid situations like that, only the routes which satisfy the optimization conditions can be updated by overlapping, nodes elimination and fine-tuning. Experimental results show that compared with other algorithms, the proposed algorithm can generate global routes with higher quality. The number of unworkable routes generated in the optimization process is less than that of other algorithms. The proposed algorithm is more applicable and stable.