复杂环境下UUV完全遍历路径规划方法

温志文, 杨春武, 蔡卫军, 毛金明



复杂环境下UUV完全遍历路径规划方法

温志文1,2, 杨春武1, 蔡卫军1, 毛金明1

(1. 中国船舶重工集团公司第705研究所, 陕西西安, 710077; 2. 水下信息与控制国家重点实验室, 陕西西安, 710077)

针对复杂环境下无人水下航行器(UUV)完全遍历路径规划方法的不足, 文中基于蚁群算法和生物激励神经网络, 提出了一种高覆盖率、低重复率的完全遍历路径规划方法。该方法基于栅格法和生物激励神经网络进行环境建模, 将神经元活性值引入蚂蚁转移概率公式中, 既克服了蚁群算法需要对环境提前扫描学习, 运算复杂的不足, 又避免了生物激励神经网络随机性强, 重复率高的缺陷。仿真试验表明, 文中方法不仅有效实现了复杂环境下UUV完全遍历路径规划, 而且能够以最短路线跳出死角, 具有覆盖率大、重复率小, 实用性强的优点。该研究可为进一步开展动态环境中的UUV完全遍历路径规划提供参考。

无人水下航行器(UUV); 蚁群算法; 生物激励神经网络; 完全遍历路径规划

0 引言

随着民用和军用无人水下航行器(unmanned underwater vehicle, UUV)的快速发展, UUV完全遍历路径规划的研究越来越受到关注。完全遍历路径规划是一种在2D环境中特殊的路径规划, 指在满足某种性能指标最优或准优的前提下, 寻找一条在设定区域内从始点出发经过所有可达点的连续路径[1]。

目前, 常用的完全遍历路径规划主要有模板算法和分块算法两类[2]。模板算法对整个环境缺乏整体的规划, 效率低且容易落入“陷阱”, 进入死循环状态; 分块方法根据障碍物分布情况将环境空间划分为一系列不重合的、有限个无障碍子区域, 然后在此基础上进行每个区域的遍历[3]。文献[4]采用模糊控制方法实现移动机器人的遍历路径规划; 文献[5]运用生物激励神经网络实现机器人的遍历路径规划; 文献[6]基于生物激励神经网络、滚动窗口、启发式搜索, 提出了一种新的遍历路径规划方法。

蚁群算法是一种启发式搜索算法, 具有较强的鲁棒性、优良的分布式计算以及易于与其他算法结合等优点[7]。然而, 将蚁群算法直接应用于完全遍历路径规划需要对环境进行先验的扫描学习过程, 使得算法运算复杂、实时性差, 计算机存储量大[8]。生物激励神经网络是由SimonX. Yang提出来的一种新颖的路径规划方法[9]。与其他路径规划方法比较, 该方法不需要对环境做出任何提前扫描, 不受环境中障碍物的形状和位置的影响, 不需要学习过程, 并且计算复杂度小、计算机存储量小、反应速度快。但生物激励神经网络方法, 在应用于遍历路径规划时会出现遍历无规律, 重复遍历次数多的不合理现象, 其规划的路径效率不高, 最大的不足就是跳出“死角”的路径不是最优的。由于以上各种方法的局限性, 方法之间的融合得到了广泛关注。

文中将蚁群算法与生物激励神经网络进行融合, 提出了一种完全遍历路径规划方法。该方法基于栅格法和生物激励神经网络进行环境建模, 将神经元活性值的变化与蚂蚁转移概率公式结合, 克服了蚁群算法需要对环境提前扫描学习的不足。在遍历过程中遇到“死角”时, 采用蚁群优化算法实现UUV以最优路径跳出“死角”, 避免了生物激励神经网络出现随机性选择和重复覆盖多的缺陷。仿真结果表明, 该方法覆盖率高, 重复率小, 在复杂环境条件下实用性更强。

1 环境建模

目前电子海图在水中兵器的应用处于探索阶段, 由于电子海图的复杂性, 通常需要将电子海图转换成可以直接利用的海图数据环境模型。

文中采用海图信息栅格化方法对某海域的数字海图进行渲染, 首先将2D规划空间均匀分解成个栅格单元, 以栅格单元为路径规划中的最小移动单位, 栅格分辨率根据UUV的尺寸自适应调整。如果某个栅格属于碰撞区, 记为1类栅格; 如不属于碰撞区则记为0类栅格, 以此表示海图的碰撞区信息。其次对碰撞区进行处理、合并, 消除不可航行路段和陷阱路段, 将碰撞区规范成多边形图形, 这样构建出的数据空间包含了标识起始点、目标点、障碍区、威胁区以及航路位置信息, 可方便利用算法进行路径规划。文中对环境模型作如下假设: 1) 将UUV视为质点, 规划路径的长度在UUV航程内; 2) 规划环境为2D空间, 将障碍物和危险区域统称为碰撞区, 以不规则区域表示; 3) 不考虑潮流、海流、电子干扰等其他干扰因素的影响。

文中采用栅格法和生物激励神经网络相结合的建模方法。UUV运动空间由若干栅格组成, 每个栅格作为1个神经元, 则整个空间就是神经网络组成的拓扑状态空间, 每个神经元的状态由分流方程确定[10]

(2)

通过计算并对每一个栅格赋予相应的活性值, 未遍历栅格活性值被赋予较大值, 碰撞区栅格活性值被赋予较小值, 已遍历过的栅格活性值减为0。每个神经元都有横向连接其相邻的神经元, 这些神经元间的规范互连构成了平面拓扑网络区域, 从而生成文中的地图环境模型。

2 UUV完全遍历路径规划

2.1 算法融合

文中将蚁群算法与生物激励神经网络相融合, 提出了新的完全遍历路径规划方法。该方法采用基于栅格法和生物激励神经网络建立的环境模型, 使蚂蚁在上述构建的拓扑网络结构中搜索前进。新的蚂蚁转移概率

基本原理为栅格未遍历时, 其活性值最大, 对蚂蚁的吸引力也最大, 吸引蚂蚁对其进行遍历。当蚂蚁对其遍历后, 活性值变为0, 对蚂蚁没有吸引力。而碰撞区的栅格由于其活性值为负, 对蚂蚁具有排斥力, 避免蚂蚁对其进行遍历。由上述蚂蚁转移概率公式可知, 蚂蚁在选择下一遍历栅格时, 与栅格信息素、活性值、距离及转弯角度都有关系, 通过蚁群算法的迭代寻优, 可以得到最优的遍历路径。

文中搜索策略采用内螺旋覆盖方法。内螺旋搜索策略是指UUV在遍历搜索过程中, 当遍历到某一处之后, 发现相邻的若干个未被遍历栅格具有相同的最大转移概率, 此时UUV将优先选择其中某一栅格, 使得这个栅格与已遍历栅格组成的搜索路径总体来看呈逆时针向内螺旋搜索状态。这种方法可以最大限度减少UUV转弯的次数, 使得能源消耗最小。

2.2 跳出“死角”

在遍历路径规划过程中, “死角”为比较恶劣的环境区域, 也是最能体现算法优越性的环境模型。它是指UUV遍历到某一处后, 相邻的8个栅格是障碍区或者已遍历区, 此时判定UUV陷入“死角”。UUV陷入“死角”有2种情况, 情况1: UUV所在栅格的邻域内除上一步经过的栅格外其余全是障碍栅格, 这种情况为UUV落入“死角”, 如图1所示。

情况2: UUV在一个区域内遍历很多栅格之后, 遍历到某一个栅格, 该栅格邻域内所有的可遍历栅格都已经被遍历过, 如图2所示。

在图1中, 黑色栅格表示障碍区。当UUV从栅格44走到栅格34完成栅格34的遍历后, 发现相邻的栅格除栅格44(已遍历)外, 其余的都是障碍区, 此时UUV落入情况1所示的“死角”。UUV沿路线实行回退策略。在栅格54处, UUV检测出临近神经元活性值最大的有多个, 如果仅仅采用生物激励神经网络进行遍历, UUV将随机选取具有最大活性值的神经元其中的一个进行移动, 如此, UUV所走的路径将有可能绕远, 而不是最优路径, 出现覆盖无规律和重复覆盖多的缺陷。

同理, 在图2中UUV由栅格44遍历到栅格34后, 发现相邻的栅格除了障碍区都已被遍历(如栅格24已被遍历), 此时UUV落入情况2所示的“死角”。文中方法将蚁群算法和生物激励神经网络进行融合, 引入规则制导策略。当UUV落入上述“死角”时, 根据神经元拓扑网络结构, UUV搜索附近最近的未被遍历过的神经元, 然后运用蚁群算法, 以当前栅格34为起始点, 目标栅格为终点, 规划一条路径最短的线路, 使得UUV以最短路径跳出死角, 避免了UUV遇到“死角”随机无规律的移动, 减少了重复率, 其中跳出“死角”时的蚂蚁转移概率公式(3)所示。

2.3 性能评价指标

完全遍历路径规划常用的性能评价指标主要有覆盖率和重复率。覆盖率是指已遍历区域的面积与UUV可达区域面积的比值, 数学定义为

重复率是指UUV重复遍历区域的面积与可达区域面积的比值,数学定义

显然, UUV进行遍历搜索路径规划时, 覆盖率越大, 重复率越小, 则其性能更优。

2.4 方法流程

文中遍历路径规划方法的流程如图3所示。

3 仿真结果及分析

为验证文中完全遍历路径规划方法的有效性和可行性, 运用上述建立的环境模型进行仿真试验。文中采用VS2005设计仿真平台界面, 在该界面中, 可随意设计任意形状的碰撞区域, 也可单步查看UUV任一时刻遍历搜索的进程, 仿真结果以直观、形象的方式显示。其中, 蚁群算法使用经过试验测试的参数: 蚂蚁数量, 迭代循环次数, 初始信息素, 标准值。生物激励神经网络方法也使用经过测试的参数:=10,==1,。

由图4可以看出, UUV很好地避开不规则碰撞区, 有效地完成了遍历路径规划, 验证了文中方法的有效性和可行性。表1为对环境地图1的仿真结果。由表中可知, 文中方法规划路径覆盖率为100%, 重复率为7.548%。相比文献[8]覆盖率95%, 重复率10.000%的结果, 文中方法不仅达到了完全覆盖的效果, 而且降低了重复率, 因此更具优越性。

表1 环境地图1仿真结果

相比于文献[8]提出的完全遍历路径规划方法仅仅适用于碰撞区为规则形状的简单环境模型的缺陷, 文中提出的规划方法适用于不规则碰撞区且随机分布的复杂环境模型。建立可以随意布置不规则碰撞区的复杂环境地图2, 其由个栅格的神经网络组成。图5为复杂环境模型中, UUV遍历到第102步跳出“死角”的仿真图。

由图5可以看出, 当UUV落入“死角”时,文中方法能以最优的路径使UUV跳出“死角”。

图6为复杂环境2中UUV完全遍历路径规划仿真结果图。由图6可以看出, 在复杂环境模型中, UUV遍历路径规划的覆盖率仍达100%, 重复率低于10%, 表明文中提出的规划方法更具实用性。

通过以上仿真结果可以看出, 文中的遍历路径规划方法不仅能够有效地实现UUV遍历路径规划, 而且在覆盖率和重复率等性能指标方面优于文献[8]的遍历路径规划方法。同时, 文中方法能够以最短路线跳出“死角”, 在复杂环境下更具实用性。

4 结束语

文中提出蚁群算法与生物激励神经网络相融合的完全遍历路径规划方法, 利用栅格法和生物激励神经网络建立环境建模, 将神经元活性值的变化与蚂蚁转移概率公式结合, 克服了蚁群算法需要对环境提前扫描学习的不足。在遍历过程中遇到“死角”时, 采用蚁群优化算法实现UUV以最短路径跳出“死角”, 避免了生物激励神经网络随机性强, 重复覆盖多的缺陷。仿真结果表明, 文中方法不仅能够有效地实现UUV的遍历路径规划, 而且提高了覆盖率, 降低了重复率, 在复杂环境下具有较高的规划效率。后续, 将在此工作基础上进一步展开动态环境中的UUV完全遍历路径研究。

[1] Choset H. Coverage for Robotics——A Survey of Recent Results[J]. Annals of Mathematics & Artificial Intelligence, 2001, 31(1-4): 113-126.

[2] De Carvalho R N, Vidal H A, Vieira P, et al. Complete Coverage Path Planning and Guidance for Cleaning Robots[C]//IEEE International Symposium on Industrial Electronics: Portugal, 1997(2): 677-682.

[3] Acar E U, Choset H. Robust Sensor——Based Coverage of Unstructured Environments[C]//Proceedings of the 2001 IEEE/RSJ on Intelligent Robots and Systems. Maui: IEEE, 2001: 61-68.

[4] 陈鹏, 李彩虹. 移动机器人混合式全遍历覆盖路径规划算法[J]. 山东理工大学学报:自然科学版, 2013, 27(5): 22-27. Chen Peng, Li Cai-hong. A Hybrid Algorithm of Com- plete Coverage Path Planning for Mobile Robot[J]. Journal of Shandong University of Technology(Natural Science Edition), 2013, 27(5): 22-27.

[5] 朱博, 邓三鹏, 王英飞, 等. 基于生物激励神经网络的移动机器人遍历路径规划[J]. 装备制造技术, 2014(12): 30-32.

[6] 邱雪娜, 刘士荣, 宋加涛, 等. 不确定动态环境下移动机器人的完全遍历路径规划[J]. 机器人, 2006, 28(6): 586-592.Qiu Xue-na, Liu Shi-rong, Song Jia-tao, et al. A Complete Coverage Path Planning Method for Mobile Robots in Uncertain Dynamic Environments[J]. Robot, 2006, 28(6): 586-592.

[7] 段海滨, 王道波, 于秀芬. 蚁群算法的研究现状及其展望[J]. 中国工程科学, 2007, 9(2): 98-102.

Duan Hai-bin, Wang Dao-bo, Yu Xiu-fen. Ant Colony Algorithm: Survey and Prospect[J]. Engineering Science, 2007, 9(2): 98-102.

[8] 张赤斌, 王兴松. 基于蚁群算法的完全遍历路径规划研究[J]. 中国机械工程, 2008, 19(16): 1945-1949.Zhang Chi-bin, Wang Xing-Song.Complete Coverage Path Planning Based on Ant Colony Algorithm[J]. China Mechanical Engineering, 2008, 19(16): 1945-1949.

[9] Yang S X, Meng M. Neural Network Approaches to Dynamic Collision-free Trajectory Generation[J]. IEEE Tr- ansactions on Systems Man & Cybernetics Part B Cybe- rnetics A Publication of the IEEE Systems Man & Cybernetics Society, 2001, 31(3): 302-318.

[10] Bernabucci I, Conforto S, Capozza M, et al. A Biologically Inspired Neural Network Controller for Ballistic Arm Movements[J]. Journal of Neuroengineering & Rehabilitation, 2007, 4(1): 1-17.

(责任编辑: 杨力军)

A Complete Coverage Path Planning Method of UUV under Complex Environment

WEN Zhi-wenYANG Chun-wuCAI Wei-junMAO Jin-ming

(1. The 705 Research Institute, China Shipbuilding Industry Corporation, Xi′an 710077, China; 2. Science and Technology on Underwater Information and Control Laboratory, Xi′an 710077, China)

A new method with high coverage rate and low repetition rate is presented to solve the complete coverage path planning problem for an unmanned underwater vehicle(UUV) under complex environment. The method integrates ant colony algorithm and biologically inspired neural network. In this method, environment is modeled with grid cell and biologically inspired neural network, and the neuronic activity is introduced into the ant transition probability formula. As a result, the shortcomings of ant colony algorithm, e.g., scanning and learning environment in advance are needed and computation is complicated, are overcome, and the defects of high complexity, high randomness and high repetition rate of the biologically inspired neural network are avoided. Simulation experiment in complex environment shows that complete coverage path planning of UUV can be efficiently implemented by the proposed method, and the method can get rid of the dead corner in the shortest route. The present method has higher coverage rate and lower repetition rate. This research may provide a reference for further improvement of the UUV complete coverage path planning in dynamic environment.

unmanned underwater vehicle(UUV); ant colony algorithm; biologically inspired neural network; complete coverage path planning

10.11993/j.issn.1673-1948.2017.01.005

TJ630.33; TP24

A

1673-1948(2017)01-0022-05

2016-10-08;

2016-12-13.

温志文(1992-), 男, 在读硕士, 主要研究方向为鱼雷总体技术.