基于改进生物启发神经网络的机器人目标搜索方法

张智彤，倪建军，莫正佩

(河海大学物联网工程学院，江苏 常州 213022)

0 引 言

针对未知环境中目标搜索的问题，国内外的学者做了大量的研究。戴良军等[1]提出了协同搜索策略，并分析了分区域搜索和横队平行搜索的优势与不足。肖潇等[2]提出了一种结合全区域搜索与动态模板匹配的未知环境中目标搜索方法，与常规的覆盖搜索算法[3]相比，可以不受起始位置影响，具有较好的避障能力，但该方法仍属于覆盖搜素，尽管具有较强的鲁棒性，但搜索时间和空间的开销太大，搜索效率不高。为了降低搜索代价，Aydemir等[4]提出了一种间接搜索的方法，即首先搜索与目标有关的“中间对象”，然后根据关联关系对目标进行搜索。该方法由于利用了目标关联信息，在一定程度上可以提高搜索效率，但通常间接关系很难确定，同时对间接目标的搜索也很困难。动态目标搜索问题的最优解很难通过理论方法得到其解析形式。在动态搜索问题中，最主要的难题在于搜索过程中搜索者会逐步退化，导致对环境的探索能力降低。在动态目标搜索中，任何关于目标运动行为的先验知识都将对预测目标有极大的帮助。当目标的运动模型完全已知时，称其为“确定性”搜索问题，对导弹的航迹追踪即为经典确定性跟踪问题。当目标的运动模式可以用一类包含随机变量的模型表示时，称其为“概率性”搜索问题[5]。关于此类问题的研究通常采用递归贝叶斯估计模型更新目标在空间中的概率分布，逐步获得目标的准确位置[6-8]。

获得目标的状态信息是异构机器人目标搜索的目的。根据异构机器人对目标状态信息的了解程度，有2种目标搜索方法，例如杨日杰等[9]提出了基于马尔科夫过程的目标启发式搜索方法，根据已知的目标先验位置分布信息，对目标的运动位置进行估计和更新以得到更为精确的目标后验分布，再利用启发函数得到下一步的最佳搜索节点。这是目标先验信息已知的情况下。另一种是在目标状态信息完全未知的情况下进行目标搜索，如王宏健等[10]提出了一种分区域随机搜索方法，其意是将机器人分配到自己的责任区后开始搜索，运动目标点随机选取。虽然此方法的优点是计算量小、反应快速，但是缺点明显。若要搜索任务高效完成，需要将子区域的范围划分得很小，即多机器人系统的成员数量大，否则在一个较大范围的三维环境中随机搜索一个目标，随机性大，成功率低。雷斌等[11]首先采用全局随机搜索方式检测到目标信号强度较大的区域，然后采用PSO算法进行局部搜索，通过更新局部最优和全局最优位置信息寻找目标。

在未知环境中对目标进行搜索，目标位置信息以及障碍物的信息是未知的，移动目标在某时刻有可能出现在已经搜索过的区域，也可能出现在未搜索过的区域，但是目标会在局部范围内释放一些信息素，这些信息素会随着时间的推移而减少，而且机器人可以探测到这些信息素。针对这种情况，本文提出改进生物启发神经网络的方式并结合遗传算法，根据机器人能力不同分配不同的搜索区域。

1 基于遗传算法机器人区域分配

本文采用遗传算法[12-13]根据机器人搜索能力的大小对搜索区域进行划分，并让机器人移动到相应的搜索区域进行下一步的搜索。

1)编码方式。

染色体的长度为机器人个数。染色体表示给每个机器人分配区域的范围。每一条染色体p表示为：

p={[(xmin 1,xmax 1),(ymin 1,ymax 1)],…,

[(xmin k,xmax k),(ymin k,ymax k)]}

(1)

2)适应度函数。

结合本次搜索区域的分配，应该考虑以下的问题：①机器人的初始位置；②机器人搜索能力；③划分范围的面积。所以适应度函数如公式(2)所示。

(2)

其中，posi和roboti分别表示区域的中心位置和第i个机器人的初始位置，posAreai和robotCapi分别表示第i个区域的面积和第i个机器人的搜索范围的能力。

基于遗传算法区域分配的操作步骤如下：

1)初始化。初始化种群大小为PopSize，迭代次数为PopGeneration，染色体长度为ChromeLength，变异概率为MutProb，交叉概率为CrossProb，最好个体的适应度值为BestPop和整个群体最佳的适应度值为BestFitness。

2)计算个体适应度值。根据公式(2)计算每个个体的适应度值fi。

3)选择操作。采用轮盘赌策略，则每个个体被选择到下一代的概率为：

(3)

4)交叉操作。根据交叉概率随机选择2条染色体进行交叉，并对交叉后的结果按步骤6进行调整，使得分配搜索的每个区域范围的合集可以覆盖整个地图。

5)变异操作。根据变异概率选择某条染色体进行变异，这里变异操作采用增大或减小某个搜索的范围，并对变异后的结果按步骤6进行调整，使得分配搜索的每个区域范围的合集可以覆盖整个地图。

6)调整。当出现某个染色体表示搜索区域的范围发生重叠的时候，随机选择一个发生重叠的区域，并把该区域重叠的部分去除掉。当出现搜索范围没有覆盖整个地图时，则终止本次交叉或变异操作。

2 基于改进生物启发神经网络的目标搜索

2.1 未知环境中地图的划分

地图构建是目标搜索任务的关键。在未知环境下机器人在搜索之前不可能获得地图信息。

图1 环境建模方法

由于环境的全局信息是未知的，所以不可能用全局环境信息来构建地图。然而，该机器人可以利用车载传感器对周围环境信息进行检测，因此，可以根据机器人检测到的局部信息，利用栅格法建立地图，并根据此地图获得障碍物的坐标。环境建模方法如图1所示。

2.2 生物启发神经网络方程改进

在传统的生物启发神经网络[14-16]中，每一个神经元(表示为q)对应于环境中的一个位置。机器人总是选择邻居神经元中活性值最大的神经元作为它的下一步动作位置，其选择规则是[15-16]：

qn←xqn=max{xj,j=1,2,…,k}

(4)

在一个范围很大的环境中，该特性会大幅度增加计算的复杂度。为了降低计算复杂度，本文采用动态生物启发神经网络模型，即BINN是一个动态的网络，以机器人为中心，以机器人的传感器所能探测的最大范围为半径(R)。当机器人在环境中运动时，只更新自己所能探测到范围内的神经元的活性值。在动态生物启发神经网络模型搭建完成后，生物启发神经网络模型中每个神经元的活性值由如下方程计算得到：

(5)

其中，xi是第i个神经元的活性值；A, B, D均为非负常数，分别代表被动率、活性值的上限和下限；k表示第i个神经元的邻居神经元个数。ωij是第i个神经元与第j个神经元之间的连接权值。函数[x]+和[x]-是非线性函数，定义为：[x]+=max{x, 0}, [x]-=max{-x, 0}。

由于目标在不断运动中，并且目标走过的地方会留下目标特有的信息素。某时刻它既可能出现在已经搜过的区域，也有可能出现在未搜索的区域。所以对于已经搜索过区域的活性值会随着时间的变化而变化，对传统的生物启发神经网络公式进行改进：

(6)

当第i个神经元已经被探测过但在本时刻不在其探测范围内时，采用公式(7)计算。

(7)

其中，Activityi表示第i个神经元的活性值，由公式(5)计算得到，ωia代表神经元i和机器人位置a之间的权重，dia代表神经元i和机器人a之间的距离。NArea指的是机器人a所探测的范围中栅格的数目。visitedi表示神经元i访问的次数，t表示当前循环次数，tmax表示总的循环次数，-t×visitedi/tmax可以防止多次选择同一个神经元。targetInfoi表示目标在第i个神经元上留下的信息素大小。Rangea表示第a个机器人探测的范围。

机器人搜索的过程如下：

1)当机器人走到指定的搜索区域之后，首先在探测范围的外围随机选择一个位置作为初始目标点，初识目标点的选择如图2所示。按公式(5)更新活性值。

2)选择活性值最大的点作为下一个搜索的位置，把已经探测过的范围的活性值降为0，使用公式(6)，对未探测过的进行更新，并使得该位置处的访问记录加1。如果该位置的访问次数达到禁忌阈值，则把该位置加入禁忌表中，当禁忌表的长度达到某个数值后，把禁忌表中最初加入的几个数据从禁忌表中删除，并重置该位置的活性值和访问次数。

3)对于已经探测过的并且不在本次探测范围内的活性值，按照公式(7)进行更新。

图2 初始目标点选取

3 仿真实验及结果

为了验证未知环境下的基于禁忌搜索的动态生物启发神经网络方法的有效性，进行了多次仿真实验。在机器人进行目标搜索的过程中，有2种情况：一种情况是目标静止的，另一种是目标随机运动。针对这2种情况进行了多次实验。为了简化实验，机器人以质点表示，并且不考虑各种噪声的干预。机器人和目标分别用不同的颜色进行标识。机器人初始位置以及基于遗传算法机器人搜索区域分配如表1所示。

表1 基于遗传算法机器人搜索区域

Robot1Robot2Robot3Robot4初始位置(15,29)(0,17)(15,17)(0,29)最大搜索能力/栅格3453搜索范围X[14,30][0,13][14,30][0,13]搜索范围Y[18,30][0,17][0,17][18,30]

3.1 目标处于静止状态实验结果

在此实验中，目标处于静止状态。目标初始位置分别为(5，4)和(2，26)。与随机搜索算法和原始的生物启发神经网络相比，结果如图3和表2所示。从图中可以看出，本算法可以有效搜索到目标。

(a) 随机算法

(b) 原始生物启发神经网络

(c) 本文算法图3 静态目标搜索结果

表2 静态目标搜索成功率对比

算法仿真次数成功次数成功率/%平均时间/s本文算法303010028.13原始算法302686.633.26随机搜索30155048.25

3.2 目标处于运动状态实验结果

在此实验中，目标处于运动状态。目标初始位置分别为(5，4)和(2，26)。与随机搜索算法相比，结果如表3和图4所示。从图中可以看出，本算法可以有效搜索到目标。

表3 动态目标搜索成功率对比

算法仿真次数成功次数成功率/%平均时间/s本文算法303010035.56原始算法302273.342.89随机搜索301033.359.78

(a) 随机算法

(b) 原始生物启发神经网络

(c) 本文算法图4 动态目标搜索结果

3.3 有效性验证

为了验证本文算法的有效性，又进行了以下2个实验，第1个是目标静止在不同的位置(图5)，第2个是目标在不同位置移动(图6)。

(a)

(b)图5 目标静止在不同位置

(a)

(b)图6 目标在不同位置移动

4 结束语

本文研究了未知环境下的机器人目标搜索问题，根据机器人搜索能力的不同提出基于遗传算法搜索区域的划分；由于没有目标的状态信息以及目标是随机运动的，在某一时刻目标可能出现在未搜索过的区域也可能出现在已经搜索过的区域，针对这种情况提出了基于禁忌搜索改进生物启发神经网络的搜索方式。为了验证所提方法的有效性，本文设计了仿真实验，实验仿真结果表明，该方法能有效完成目标搜索任务。

参考文献：

[1] 戴良军,陈宇强,周绍磊. 无人机编队协同搜索策略研究[C]// 2014(第五届)中国无人机大会论文集. 2014:610-614.

[2] 肖潇,方勇纯,贺锋,等. 未知环境下移动机器人自主搜索技术研究[J]. 机器人, 2007,29(3):224-229.

[3] Gonzalez E, Alvarez O, Diaz Y, et al. BSA: A complete coverage algorithm[C]// Proceedings of the 2005 IEEE International Conference on Robotics and Automation. 2005:2040-2044.

[4] Aydemir A, Sjöö K, Jensfelt P. Object search on a mobile robot using relational spatial information[C]// Proceedings of the 2010 International Conference on Intelligent Autonomous Systems. 2010:111-120.

[5] Senanayake M, Senthooran I, Barca J C, et al. Search and tracking algorithms for swarms of robots: A survey[J]. Robotics and Autonomous Systems, 2016,75(Part B):422-434.

[6] Esmailifar S M, Saghafi F. Moving target localization by cooperation of multiple flying vehicles[J]. IEEE Transactions on Aerospace and Electronic Systems, 2015,51(1):739-746.

[7] Aziz A M. A joint possibilistic data association technique for tracking multiple targets in a cluttered environment[J]. Information Sciences, 2014,280:239-260.

[8] Lanillos P, Gan S K, Besada-Portas E, et al. Multi-UAV target search using decentralized gradient-based negotiation with expected observation[J]. Information Sciences, 2014,282:92-110.

[9] 杨日杰,吴芳,徐俊艳,等. 基于马尔可夫过程的水下运动目标启发式搜索[J]. 兵工学报, 2010,31(5):1088-1093.

[10] 王宏健,熊伟,陈子印,等. 多自主水下航行器区域搜索与协同围捕方法研究[J]. 中国造船, 2010,51(2):117-125.

[11] 雷斌,李文锋. 基于粒子群优化的多机器人合作目标搜索算法[J]. 武汉理工大学学报, 2009,31(15):73-76.

[12] 刘耀轩,林煦涵,孙海洋. 遗传算法的研究与改进[J]. 电子世界, 2017(8):12-13.

[13] 马永杰,云文霞. 遗传算法研究进展[J]. 计算机应用研究, 2012,29(4):1201-1206.

[14] Ni Jianjun, Wu Liuying, Shi Pengfei, et al. A dynamic bioinspired neural network based real-time path planning method for autonomous underwater vehicles[J]. Computational Intelligence and Neuroscience, 2017-02-01, doi: 10.1155/2017/9269742.

[15] Ni Jianjun, Yang S X. Bioinspired neural network for real-time cooperative hunting by multirobots in unknown environments[J]. IEEE Transactions on Neural Networks, 2011,22(12):2062-2077.

[16] Ni Jianjun, Wu Liuying, Fan Xinnan, et al. Bioinspired intelligent algorithm and its applications for mobile robot control: A survey[J]. Computational Intelligence and Neuroscience, 2015-12-27, doi: 10.1155/2016/3810903.