杨琳艺

摘  要： 导览路径规划作为园林智能辅助导览系统中的重要一环，能够为游客提供实时的目的地地图路径指导，直接影响着用户的使用体验。为了提高其准确性和实时性，提出一种基于人工鱼群算法的园林导览路径规划方法。对导览环境模型及相关问题进行描述，并通过总长度和平滑度两个方面设计了路径规划的目标函数。对采用的人工鱼群优化算法进行分析，并针对人工鱼群算法存在的缺点，在步长更新方式上进行了改进，有利于提高寻优精度和运行速度。仿真环境下的测试结果表明，提出的改进算法具有更好的最优解和快速收敛性能。实际案例应用结果验证了提出路径规划方法的可行性和有效性。

关键词： 园林导览; 路径规划; 人工鱼群算法; 自适应步长; 目标函数; 迭代曲线

中图分类号： TN911.1?34; TP393                    文献标识码： A                  文章编号： 1004?373X（2020）03?0169?04

Research on garden guiding path planning method

based on artificial fish swarm algorithm

YANG Linyi

（Sichuan Tourism University， Chengdu 610000， China）

Abstract： Guiding path planning， as an important part of the garden intelligent assistant guiding system， can provide visitors with real?time destination map path guidance， which directly affects the user experience. In order to improve its accuracy and real?time performance， a garden guiding path planning method based on artificial fish swarm is proposed. The guiding environmental model and related problems are described， and the objective function of path planning is designed by total length and smoothness. In addition， the artificial fish swarm algorithm is analyzed. In consideration of the shortcomings of the artificial fish swarm algorithm， the step size update method is improved， which is beneficial to the improvement of the optimizing precision and running speed. The test results in the simulation environment show that the improved algorithm has better optimal solution and fast convergence performance. The actual application results verify the feasibility and effectiveness of the proposed path planning method.

Keywords： garden guiding; path planning; artificial fish swarm algorithm; adaptive step size; objective function; iterative curve

0  引  言

隨着各种高性能电子设备的成本不断下降，物联网技术应用也开始得到了社会的认可和推广。智能交通、智慧医疗和智能安防等新型市场均采用了物联网的理论和框架。随着国内旅游事业的不断增长，各大景区对硬件和软件服务的投入不断增加，基于物联网技术的景区、园林导览系统正逐渐得到普及，以便为游客提供更加人性化和便捷化的服务[1?3]，例如依托移动设备的园林智能辅助导览系统等，能够以APP的形式为游客提供各种在线服务，承载了实现用户人机交互的关键功能。其中，导览路径规划作为园林智能辅助导览系统中的重要一环，能够为游客提供实时的目的地地图路径指导，改变了传统的人工导览方式，节省了人工成本，更提高了便捷性。

通过调查发现，目前应用于园林导览方面的路径规划研究仍处于空白阶段，因此，本文提出将群体智能优化算法中较为先进的人工鱼群算法应用于园林导览路径规划，并对标准的人工鱼群算法进行了自适应步长改进，有效提高了收敛速度和寻优精度。在仿真测试和实际案例应用中均得到了较为理想的运行效果。

1  问题描述及其环境模型

1.1  研究思路介绍

导览路径规划功能中导航的精确度和运行速度是两个关键的技术指标，也成为各种相关领域研究的重点和难点。例如，文献[4]建立了车辆的运动学模型并提出了一种基于滑模控制的自动泊车系统路径跟踪方法，实现了智能泊车入库导航。文献[5]提出了一种基于概率地图的工业机器人路径搜索优化算法，能够自动搜索出一条无碰撞的全局优化路径。相比于其他类似方法，文献[6]将及时性与安全性作为最主要的约束目标，提出了一种应用于地震救援路径优化问题的混合遗传算法，得到了较高的求解精度和收敛速度。但是，目前应用于园林导览方面的路径规划研究仍处于空白阶段，因此，本文提出将群体智能优化算法中较为先进的人工鱼群算法应用于园林导览路径规划。因为相比遗传算法，人工鱼群算法具有较好的全局寻优能力和较快的收敛速度，并针对人工鱼群算法存在的缺点，在步长更新方式上进行改进，有利于提高寻优精度和运行速度。此外，在目标函数的确定方面本文引入了文献[5?6]的理念，从总长度和平滑度两个方面来建立路径的总目标函数。

1.2  环境模型

假设园林导览的场景在直角坐标系[XOY]中，起始点表示为[S（xs，ys）]，目标点表示为[T（xt，yt）]，经过坐标变换，起始点和目标点之间的直线线段[ST]设为[x]轴，得到新环境坐标系[xOy]，其中的任一点表示为[P（X，Y）]，坐标变换的公式如下：

式中：[（x，y）]表示[P]在新坐标系[xOy]中的坐标;[θ]表示初始轴与[ST]之间的夹角。

规划路径与障碍物的碰撞检测分为两种情况：

1） 多边形障碍物。如果路径线段和多边形某条边的线段满足如下条件，则表示两者相交，存在碰撞。

式中：[P1P2]和[Q1Q2]分别为两条线段的两个端点;[×]和[?]分别表示向量的叉乘和点乘。

2） 圆形障碍物。路径线段和圆形边相交的条件为：

式中：[x1，y1]和[x2，y2]分别表示某一路径段的两个端点坐标;[xo，yo]表示圆形障碍物;[R]表示圆形障碍物的半径。

2  基于改进人工鱼群算法的园林导览路径规划

2.1  人工鱼群算法

人工鱼群算法[7?8]作为一种优化算法，是一种模拟自然界中动物群体智能行为的方法。利用模拟的人工鱼模拟鱼群的觅食行为、聚群行为和追尾行为，以便达到寻优目的。假设AF是真实鱼的一个虚拟实体，称为人工鱼，其视觉概念示意图如图1所示。

图1中，[X]表示AF的当前状态;Visual为其视野范围;[Xv]为其某时刻视点的位置，若此位置的状态优于当前状态，則AF移动到[Xnext]，否则，AF寻找其他位置。人工鱼群的四种基本行为包括[9]：觅食行为、聚群行为、追尾行为、随机行为。具体流程如下：

1） 觅食行为：设该人工鱼此刻的状态为[Pi]，在其感知范围内随机挑选一个状态[Pj]。判断是否移动的数学表达式为[10]：

式中：[Rand]表示一个取值范围为（0，1）的随机数;[step]表示步长;[dij]表示人工鱼的当前邻域;[Yi]和[Yj]分别为两个不同状态下的适应值。

2） 聚群行为：设人工鱼群中人工鱼的[dij]内感知到的伙伴数目为[nf]且中心位置状态为[Pc]，数学表达式为：

式中[δ]表示拥挤度因子。

3） 追尾行为;设人工鱼当前的[dij]内感知到食物浓度的最大状态是[Pmax]，其数学表达式为：

4） 随机行为：设人工鱼此刻的状态是[Pi]，在感知范围[Visual]内随机挑选另外一个状态[Pj]并朝着此方向前进一步[11?12]。

2.2  参数编码

初始化的过程中，设人工鱼的位置是[n×s]维变量，[n]表示聚类中心的数量，[s]为样本向量的维数，则起始的位置编码如下所示[13]：

式中：[cij，j=1，2，…，s]表示种群中每个个体代表的聚类中心。

2.3  参数的改进

研究结果显示：人工鱼的步长越大，收敛速度较快，但会导致寻优精度降低;步长越小，寻优精度提高了，但是收敛速度会较低。因此，动态的步长变化成为了解决该问题的有效方法，本文定义的自适应步长为：

式中：[numbermax]和[numbercur]分别表示最大迭代次数和当前迭代次数;[stepmax]和[stepmin]分别表示设置的最大步长和最小步长。

2.4  目标函数

园林导览方面的路径规划不是一个单目标的优化问题，而应该是一个多目标优化求解问题，因此，本文结合权重系数法，引入总长度和平滑度两个指标系数，来设计路径[P]的总目标函数：

式中：[ω1]为路径长度的权值因子;[ω2]为路径平滑度的权值因子;[f1（P）]和[f2（P）]分别为路径总长度和平滑度，其中平滑度的计算方式与文献[5?6]一致。

3  实验结果与分析

3.1  实验参数

为了验证提出园林导览路径规划方法的有效性，在Matlab仿真环境下进行了模拟实验。本文所有实验的运行环境均为Windows 7系统下的Matlab 2015b，处理器为Intel[?] CoreTM i5?3210M CPU @ 2.50 GHz，内存为8 GB。在本文实验过程中，设置最大迭代次数为2 000，人工鱼群数目为60，[Visual]=6，[step]=0.4， [stepmin]=0.002，[stepmax]=0.6，[ω1=0.5]，[ω2=0.5]，[λ]=0.3，try_number=50。

3.2  仿真结果分析

将文献[6]中基于混合遗传算法的路径规划方法和本文方法，在100[×]100的仿真环境地图中分别执行10次，得到的规划结果对比如图2所示，两者的迭代曲线如图3所示。从图2可以看出，本文提出方法规划出的路径明显优于混合遗传算法，也就是说，路径导航的精确性更高。从图3可以看出，相比于混合遗传算法，本文方法能够较快地找到全局最优解，反映出改进的人工鱼群算法的快速收敛性能。

3.3  实例应用结果分析

为了验证提出的路径规划方法解决实际园林场景案例的能力，在某大型植物园林场景中进行了具体测试。该植物园林的设计总平面图如图4所示。

图5为两种方法完成路径规划的运行过程对比结果。表1为两种方法的路径规划数据统计结果，本文方法在运行时间上减少了24.7%，说明改进算法减少了所需迭代次数，大大提高了路径规划效率。由最优解、路径长度和平滑度的对比结果能够看出，本文方法在收敛精度上表现更好，能够有效解决多目标优化的路径规划问题。

4  结  语

本文提出将人工鱼群算法应用于园林导览路径规划，并针对人工鱼群算法存在的缺点，在步长更新方式上进行了改进，有利于提高寻优精度和运行速度。此外，结合了权重系数法，引入总长度和平滑度两个指标系数设计路径的总目标函数。仿真环境下的测试和实际案例应用结果验证了提出路径规划方法的可行性和有效性。但是，在实际的寻优过程中，处在障碍物类型不明确的区域时，路径规划算法极易陷入局部最优解，因此效果不够稳定，鲁棒性不高，后续将结合传感器或者GIS系统进行进一步改进。

参考文献

[1] BLETSAS A， ALEVIZOS P N， VOUGIOUKAS G. The art of signal processing in backscatter radio for μW （or less） Internet of Things： intelligent signal processing and backscatter radio enabling batteryless connectivity [J]. IEEE signal processing magazine， 2018， 35（5）： 28?40.

[2] BELLO O， ZEADALLY S. Intelligent device?to?device communication in the Internet of Things [J]. IEEE systems journal， 2016， 10（3）：1172?1182.

[3] GIL D， FERR?NDEZ A， MORAMORA H， et al. Internet of Things： A review of surveys based on context aware intelligent services [J]. Sensors， 2016， 16（7）：1069.

[4] 姜立标，杨杰.基于滑模控制的自动泊车系统路径跟踪研究[J].农业机械学报，2019，50（2）：363?371.

[5] 陈琳，韦志琪，戴骏，等.基于概率地图的工业机器人路径搜索优化算法[J].武汉理工大学学报，2016，38（4）：90?95.

[6] 张涛，曹振刚，吴坤，等.一种混合遗传算法在地震救援路径优化问题中的应用[J].科学技术与工程，2018，18（1）：266?272.

[7] NA F， ZHOU J， RUI Z， et al. A hybrid of real coded genetic algorithm and artificial fish swarm algorithm for short?term optimal hydrothermal scheduling [J]. International journal of electrical power & energy systems， 2014， 62（11）： 617?629.

[8] AZAD M A K， ROCHA A M A C， FERNANDES E M G P. A simplified binary artificial fish swarm algorithm for 0–1 quadratic knapsack problems [J]. Journal of computational & applied mathematics， 2014， 259（4）： 897?904.

[9] ROCHA A M A C， COSTA M F P， FERNANDES E M G P. A filter?based artificial fish swarm algorithm for constrained global optimization： theoretical and practical issues [J]. Journal of global optimization， 2014， 60（2）： 239?263.

[10] YANG Weihong. An improved artificial fish swarm algorithm and its application in multiple sequence alignment [J]. Journal of computational & theoretical nanoscience， 2014， 11（3）： 888?892.

[11] HAN Wei， WANG Honghua， CHEN Ling. Parameters identification for photovoltaic module based on an improved artificial fish swarm algorithm [EB/OL]. [2014?8?27]. https：//www.ncbi.nlm.nih.gov/pmc/articles/PMC4163354/.

[12] LIU Mingzhou， MA Jing， LIN Ling， et al. Intelligent assembly system for mechanical products and key technology based on internet of things [J]. Journal of intelligent manufacturing， 2017， 28（2）： 271?299.

[13] DUAN Qichang， MAO Mingxuan， DUAN Pan， et al. An improved artificial fish swarm algorithm optimized by particle swarm optimization algorithm with extended memory [J]. Kybernetes， 2016， 45（2）： 210?222.

[14] NESHAT M， SEPIDNAM G， SARGOLZAEi M， et al. Artificial fish swarm algorithm： a survey of the state?of?the?art， hybridization， combinatorial and indicative applications [J]. Artificial intelligence review， 2014， 42（4）：965?997.