-
摘要: 复杂系统间的相互作用能够用复杂网络描述. 复杂网络中某些节点遭受攻击或破坏会造成网络故障, 导致整个网络能控性变化. 不同节点失效会对网络能控性有不同的影响. 本文提出一种网络节点的分类方式, 将网络中的节点根据边的方向和匹配关系分成九种类型, 并给出了辨识节点类型的算法. 另外, 本文给出了基于此分类方式下复杂网络中某类节点失效时, 网络中驱动节点数量(用来衡量网络能控性大小的指标)的变化规律. 并通过模型网络进行仿真实验, 验证了当节点失效时本文给出的驱动节点数量变化情况, 同时还分析社交网络中不同类型节点的占比与实际中人际交往的对应关系.Abstract: The interaction between complex systems can be described by complex networks. In complex network, some nodes are attacked or destroyed, which may cause network failure and lead to the change of the whole network controllability. Different node failures have different effects on network controllability. In this paper, a classification method of network nodes is proposed, which divides the nodes into nine types according to the direction of the edge and the matching relationship, and the algorithm for identifying the type of nodes is given. In addition, the change rule of the number of driving nodes is given when a certain type of node fails in the complex network based on this classification method, which is used to measure the controllability of the network. And simulation experiments are carried out through the model network to demonstrate the change of the number of driving nodes given in this paper when the node fails. At the same time, the corresponding relationship between the proportion of different types of nodes in social networks and actual interpersonal communication is also analyzed.
-
Key words:
- Complex networks /
- network controllability /
- nodes failure /
- driver node
-
机器人在危险或恶劣环境下进行侦查、搜救、探测等复杂任务时, 多机器人区域搜索有着广泛的应用[1-2]. 相比于单个机器人, 多机器人系统在灵活性、鲁棒性和并行性等方面具备显著优势, 可以极大地提高区域搜索任务的效率[3-5]. 目前针对战场、灾难现场等复杂多变的未知环境或非结构化环境, 由于先验知识缺乏或环境要素难以辨识, 缺少全局的地图信息, 需要多机器人协同对未知环境进行区域覆盖搜索, 即多机器人需要尽快探索未知区域, 以找到所需的目标信息[6-7]. 在复杂未知的障碍环境中, 机器人通常会面临以下约束: 1) 有限的探测范围. 机器人的探测范围相对于整个任务区域的面积较小, 这一约束限制了机器人同时感知整个环境的能力. 2) 缺乏先验环境信息. 机器人在没有任何先验知识或环境信息的情况下开始区域搜索任务, 它们从零开始, 在前进的过程中不断探索和收集信息. 3) 实时避障. 机器人必须实时规划和运动, 以避开未知环境中的障碍物和其他机器人; 每个机器人需要进行实时决策, 以确保安全高效地执行搜索任务.
在多机器人协同区域搜索框架中, 机器人首先整合当前时刻自身及其他机器人获取的环境信息, 然后与其他机器人进行协同决策, 最后规划路径并运动至下一步位置, 重复上述过程, 直至整个区域搜索任务完成. 此外, 多机器人系统在决策过程中必须考虑如何减少机器人之间决策冲突等问题. 因此, 相较于已知环境下的多机器人区域搜索任务, 未知环境下的多机器人区域搜索任务更具挑战性, 并受到了广泛关注.
目前, 研究人员针对多机器人区域搜索问题提出了一系列解决方法, 大致可划分为五类: 1)基于生成树覆盖 (STC) 的区域搜索算法. 例如, Zheng等[8]提出一种基于STC的区域搜索算法(MSTC), 以实现多机器人对已知地形的区域搜索. Pehlivanoglu等[9]提出一种结合Voronoi图和STC的多机器人协同区域搜索方法. 此外, Dong等[10]进一步提出一种人工加权生成树覆盖算法(AWSTC), 有效地提升了区域搜索效率. 虽然基于STC的区域搜索算法增强了机器人遍历整个区域的鲁棒性, 但主要适用于已知环境下的区域搜索任务[11]. 2)基于群体智能的区域搜索方法. 例如自适应粒子群优化算法[12-13] (A-RPSO)、蝙蝠群算法[14] (BAT)免疫遗传算法[15] (IGA)、细菌群趋化[16] (BC)、灰狼算法[17] (GWO)等. 这些方法通常根据目标信号值设计算法的适应度函数, 引导机器人搜索任务区域. 然而在复杂未知环境中, 机器人通常难以对目标信号进行全局感知. 3)基于任务分配的区域搜索方法. Hou等[18]开发了一个任务规划系统(MPS), 由初步规划层、任务分配层和规划后层组成. Dai等[19]在多机器人区域搜索任务中采用一种基于拍卖的方法来实现任务分配. 任务分配是提高搜索效率的有效途径, 然而, 如何在未知环境下实现多机器人任务分配协作仍有待解决. 4)基于学习的区域搜索算法. 例如, Li等[20]针对群机器人中的多目标搜索问题提出一种两阶段模仿学习框架. Liu等[21]提出一种基于强化学习引导机器人规划搜索路径方法. Wang等[22]提出一种采用动作偏好选择策略的改进强化学习算法, 该算法在强化学习的基础上, 通过改变优选动作的选择方式, 解决了随机策略中无效搜索的问题. 然而, 此类基于学习的区域搜索方法可能不适合实时应用, 因为学习过程是必要的, 且需要大量的时间. 5)基于仿生神经网络(Bio-inspired neural network, BNN)的区域搜索方法. BNN主要受Hodgkin和Huxley[23]的生物神经系统模型和分流模型[24]启发. BNN中神经元连接权值是在模型设计时设定的, 可以在很大范围内选择, 无需寻找神经元之间的最优连接权值. 因此, 基于BNN的区域搜索算法不需要学习过程, 可实时运行[25]. 此外, 与其他方法相比, 基于BNN的区域搜索算法不依赖任何环境变化的先验知识[7]. 近年来, Luo等[26]提出一种基于BNN的多机器人区域搜索算法, 增强了多机器人整体之间的协作性. Sun等[27]进一步提出一种基于离散时间BNN的区域搜索算法, 在保证多机器人区域搜索效率的同时减少了计算量. Muthugala等[28]从节能的角度提出一种基于BNN的多机器人完全区域搜索算法. Chen等[6]提出一种基于BNN的多机器人分布式协作区域搜索(DCRS)算法. DCRS算法通过引入分布式模型预测控制(Distributed model predictive control, DMPC)思想, 每个机器人结合其他机器人的决策信息滚动优化自身的搜索路径, 进而提升了多机器人系统搜索效率. 然而, 上述算法主要应用于简单障碍物环境下的多机器人区域搜索任务. 当上述算法应用于复杂未知的障碍物环境时, 机器人可能陷入局部最优的状态且难以快速逃离, 导致区域搜索效率可能会出现下降.
因此, 针对上述挑战, 本文提出一种基于分层仿生神经网络的多机器人协同区域搜索算法, 在机器人陷入局部最优时, 引导机器人快速找到未搜索区域, 并通过分层协同决策机制减少机器人之间的决策冲突, 从而保证多机器人系统在复杂未知的障碍物环境下高效完成区域搜索任务. 本文的主要创新贡献如下:
● 构建了新的分层仿生神经网络信息模型: 将BNN分别和栅格地图及覆盖地图结合, 构建了区域搜索神经网络信息模型(Area search neural network information model, AS-BNN)和区域覆盖神经网络信息模型(Area coverage neural network information model, AC-BNN). 任务搜索区域内的相应环境信息将转换为AS-BNN和AC-BNN中神经元的动态活性值, 分别作为机器人处于正常搜索状态下和陷入局部最优状态下的决策基础.
● 设计了一种多机器人分层协同决策机制: 在DMPC协同决策框架下, 当机器人处于正常搜索状态时, 将基于AS-BNN进行搜索路径滚动优化决策; 当机器人陷入局部最优状态时, 则启用AC-BNN引导机器人快速找到新的未搜索区域.
本文剩余部分安排如下: 第1节介绍本文的研究问题; 第2节介绍分层仿生神经网络信息模型; 第3节详细介绍多机器人协同搜索决策过程, 尤其是分层协同决策机制; 第4节进行相应的仿真实验与分析; 第5节进行总结与展望. 本文涉及的主要符号说明如表1所示.
表 1 主要符号说明Table 1 Description of main symbols主要符号 具体含义 $ N_r $ 机器人的数量 ${ S}_{{\rm cov}}^{k}$ 第$ k $个机器人搜索的面积大小 ${ S}_{{\rm cov}}^{\rm rep}$ $ N_r $个机器人重复搜索的面积大小 $ { S}(G(x,\;y)) $ 栅格$ G(x,\;y) $的状态 ${ S}(A(\hat{x},\;\hat{y}))$ 子区域$A(\hat{x},\;\hat{y})$的状态 $ K_{\rm u} $ 未搜索栅格状态标记 $ K_{\rm o} $ 障碍物栅格状态标记 $ K_{\rm c} $ 自由栅格状态标记 $ A $ 神经元活性值衰减速率 $ B $ 神经元活性值上限 $ -D $ 神经元活性值下限 $M_r$ 第$i$个神经元的相邻神经元个数 $\psi_{i}$ AS-BNN第$i$个神经元的活性值 $\psi_{i}'$ AC-BNN第$i$个神经元的活性值 $w_{ij} $ 神经元之间连接权重系数 $I_{i}$ AS-BNN神经元外部输入信号 $I_{i}'$ AC-BNN神经元外部输入信号 $L$ DMPC框架下机器人决策预测步长 $h_{s}(k)$ 机器人在栅格地图下位置状态 $h_{s}'(k)$ 机器人在覆盖地图下位置状态 $A(\hat{x}_g,\;\hat{y}_g)$ 机器人局部最优状态下预测的目标子区域 ${x}_s(k),\;{y}_s(k)$ $k$ 时刻机器人在栅格地图所处位置 $\hat{x}_{s}(k),\;\hat{y}_{s}(k)$ $k$ 时刻机器人在覆盖地图所处位置 $J$ 用于机器人正常搜索状态下搜索路径预测的搜索收益函数 $J_E$ 用于机器人局部最优搜索状态下子区域引导路径预测过程的搜索收益函数 $J_H$ 用于机器人局部最优搜索状态下目标子区域搜索路径预测过程的搜索收益函数 $ J^{(L)} $ 机器人$L$步累积搜索收益函数 $J_c$ 神经元活性值增益函数(搜索路径预测) $J_c'$ 神经元活性值增益函数(子区域引导路径预测) $J_t$ 转弯代价函数 $J_g$ 目标子区域引导函数 $\lambda_1$ 函数$J_c$对应的权重系数 $\lambda_2$ 函数$J_t$对应的权重系数 $\lambda_3$ 函数$J_g$对应的权重系数 1. 问题描述
多机器人协同区域搜索在协同形式上可分为两类: 1)集中式协同搜索; 2)分布式协同搜索. 区别于集中式协同搜索, 在分布式协同搜索中, 多机器人系统没有主机器人负责整体决策过程, 所有机器人通过显式或隐式的通信方式相互共享信息, 实现对特定任务区域的协同搜索. 与集中式协同相比, 分布式协同具有更强的灵活性和鲁棒性, 广泛应用于复杂的非结构化环境中. 因此, 本文重点研究复杂未知环境下的多机器人分布式协同区域搜索问题.
1.1 任务搜索区域表示模型
假设多机器人系统的任务搜索区域形状为矩形, 任务区域用栅格地图表示. 将区域划分为大小相同的$ { N_1}\times{ N_2} $个栅格, 所有栅格的集合记为$ G= \{(x,\;y)\mid x=1,\;2,\;\cdots,\;{ N_1};\;y=1,\;2,\;\cdots,\;{ N_2}\} $, $ G(x, y) $表示位置为$ (x,\;y) $的栅格, 并命名为区域搜索地图, 如图1所示. 每个机器人占据一个栅格, 其探测范围为$ m\times n $个栅格, 一旦障碍物和目标出现在探测范围内, 则机器人可通过机载传感器(如测距传感器、视觉传感器等[7, 27])获取其相应位置信息. 根据机器人在搜索过程中获取的环境信息, 将区域搜索地图内栅格的状态划分为三种, 分别是未搜索栅格、障碍物栅格、自由栅格, 如式(1)所示. 由于所有机器人都没有先验环境信息, 因此每个栅格的初始状态为$ K_{\rm u} $, 即未搜索栅格.
$$ { S} \left(G(x,\;y)\right)=\left\{ \begin{aligned} & K_{\rm u},\; & & G{(x,\;y)\; \text{为未搜索栅格}}\\ & K_{\rm o},\; & & G{(x,\;y)\; \text{为障碍物栅格}}\\ & K_{\rm c},\; & & G{(x,\;y)\; \text{为自由栅格}} \end{aligned}\right. $$ (1) 其中, $ {S}(G{(x,\;y)} ) $表示$ \,G(x,\;y) $的状态, $ K_{\rm u} $, $ K_{\rm o} $, $ K_{\rm c} $分别表示栅格的三种状态标记.
本文在区域搜索地图的基础上进一步构建了区域覆盖地图, 如图2右侧所示. 区域覆盖地图中每个子区域包含$s_f\times s_f$ 个栅格, 所有子区域的集合记为$A=\{{(\hat{x},\;\hat{y}) \;|\; \hat{x} = 1,\;2,\;\cdots,\;N_x;\; \hat{y} = 1,\;2,\;\cdots,\; N_y}\} $, 其中$N_x=N_1/s_f$, $N_y=N_2/s_f$. 每个子区域 $A(\hat{x},\;\hat{y})$包括两种状态, 如式(2) 所示. 如果子区域$A(\hat{x},\;\hat{y})$对应区域搜索地图的所有栅格存在未搜索栅格, 标记该子区域为未覆盖状态, 否则标记为已覆盖状态.
图 2 区域搜索地图与区域覆盖地图映射示例$(s_f=2)$Fig. 2 The example of mapping the area search map with the area cover map$(s_f=2)$$$ \begin{array}{*{20}{l}} { S}(A(\hat{x},\;\hat{y}))=\left\{ \begin{aligned} & K_{\rm uc},\; && A{(\hat{x},\;\hat{y})\; \text{为未覆盖子区域}}\\ & K_{\rm co},\; & & A{(\hat{x},\;\hat{y})\; \text{为已覆盖子区域}} \end{aligned}\right. \end{array} $$ (2) 其中, $ { S}(A(\hat{x},\;\hat{y})) $表示子区域$ A(\hat{x},\;\hat{y}) $的状态, $ K_{\rm uc} $, $ K_{\rm co} $分别表示子区域的两种状态标记. 区域覆盖地图相较于区域搜索地图可以视作一种粗粒度环境表示模型, 其目的是在全局范围内表征任务搜索区域的覆盖状态信息.
1.2 多机器人协同区域搜索任务
本文采用$ { R}=\left\{{ R_1},\;{ R_2},\;\cdots,\;{ R_{N_r}}\right\} $表示参与区域覆盖搜索任务的$ N_r $个机器人. 每个机器人都可以通过其携带的传感器进行定位, 感知目标信息和障碍物. 在与其他机器人通信后, 机器人可以在通信范围内保持通信. 机器人$ { R}_s $ ($ s=1,\;2,\;\cdots,\;N_r $)的运动模型满足式(3)[29]
$$ \begin{array}{*{20}{l}} \left\{\begin{aligned} &\dot{x}_s(k)=\left\|V_s(k)\right\| \cos(\theta_s(k)) \\ &\dot{y}_s(k)=\left\|V_s(k)\right\| \sin(\theta_s(k)) \\ &\left\|V_s(k)\right\| \leq V_{\max } \end{aligned}\right. \end{array} $$ (3) 其中, $V_s(k)$表示机器人在$k$时刻的速度, $V_{\max}$为机器人的最大速度, ${x}_s(k),\;{y}_s(k)$为机器人在k时刻的位置信息, $\theta_s(k)$为机器人的运动方向角.
如前文所述, 在复杂未知的障碍物环境中, 机器人通常会遇到以下约束: 1)检测范围有限; 2)缺乏先验环境信息; 3)实时避障和碰撞等. 由于这些约束, 每个机器人需要在避开环境障碍物以及避免机器人之间发生碰撞的前提下, 不断地探索未搜索区域. 此外, 在障碍物未知的复杂环境中, 多机器人难以完全规避对已搜索区域的重复探测. 因此, 多机器人协同搜索策略在提升机器人个体搜索能力的同时, 也需减少机器人之间的重复搜索, 从而实现高效区域搜索. 综上, 多机器人协同搜索任务的优化目标函数如式(4)所示[7]:
$$ OBJ=\max \left( \sum\limits_{k=1}^{N_r}{ S}_{{\rm cov}}^{k}-{ S}_{{\rm cov}}^{\rm rep} \right)$$ (4) 其中, $ \sum_{k=1}^{N_r}{ S}_{{\rm cov}}^{k} $ 表示$ N_r $个机器人搜索的面积之和, $ { S}_{{\rm cov}}^{k} $表示第$k$个机器人搜索的面积大小, $ { S}_{{\rm cov}}^{\rm rep} $表示$ N_r $个机器人重复搜索的面积大小.
2. 分层仿生神经网络信息模型
为了表征多机器人区域搜索过程中的动态环境信息, 本节引入仿生神经网络, 将其分别与区域搜索地图、区域覆盖地图结合, 构建分层仿生神经网络信息模型, 作为多机器人运动决策的基础.
2.1 仿生神经网络结构
二维BNN结构如图3所示. 神经元之间只有局部的横向连接, 每个神经元都有一个相匹配的神经元活动值$ \psi $, 网络中第$ i $个神经元活动值的动态特性如式 (5)所示[26]
$$ \begin{split} \frac{{\rm d}\psi_{i}}{{\rm d}t}=\;&-A\psi_{i}+(B-\psi_{i})\left([I_{i}]^++\sum\limits_{j=1}^{M_r}w_{ij}[\psi_{j}]^+\right)-\\&(D+\psi_{i})[I_{i}]^- \\[-1pt] \end{split} $$ (5) 式中, $ I_{i} $表示第$ \;i $个神经元接收到的外部输入信号, $ [I_{i}]^{+}+\sum_{j=1}^{M_r}w_{ij}[\psi_{j}]^{+} $表示兴奋性输入, $ [I_{i}]^{-} $表示抑制性输入; $ [I_{i}]^{+}={\rm max}(I_{i},\;0) $, $ [I_{i}]^{-}={\rm max}(-I_{i}, 0) $, $ \psi_{j} $表示与神经元$ \;i $相邻的神经元$ \;j $, $ [\psi_{j}]^{+}= {\rm max}(\psi_{j},\;0) $; $ M_r $是第$ i $个神经元的相邻神经元的数量(在其半径$ r $内, $ r $ = $ \sqrt{2} $); $ A $, $ B $, $ D $均为正常数, $ A $表示$\, \psi_{i} $的衰减率, $ B $, $ -D $分别为$\, \psi_{i} $的上下限, 即$ \psi_{i}\in[-D,\;B] $. 假设BNN包含$H_1\times H_2$个神经元, 且每个神经元最多有8个局部连接, 因此神经连接总数为$8H$ ($H=H_1\times H_2$). 因此, BNN的计算复杂度为${\rm{O}} (H)$. 需要注意的是, BNN的外部输入信号可以根据实际场景的需要进行定义.
在式(5)中, $ w_{ij} $表示神经元$ i $与相邻神经元$ j $之间的连接权重系数, 定义为式(6)
$$ \begin{split} w_{ij}=\;&f_1(\|e_{i}-e_{j}\|)=\\ &\left\{\begin{aligned} &\frac{\alpha}{\| e_{i}-e_{j}\|} ,&&0<\| e_{i}-e_{j}\|\leq r\\ &0 ,&&\|e_{i}-e_{j}\|> r \end{aligned}\right. \end{split} $$ (6) 其中, $ f_1(\cdot)$表示神经元连接权重系数函数, $ \| e_{i}-e_{j}\| $表示状态向量$ e_{i} $和$ e_{j} $之间的欧氏距离, $ \alpha $是一个正的常数, 通常$ w_{ij}\in [0,\; 1] $. 在本文中, $ \alpha $设置为0.1.
2.2 分层信息模型构建
本节构建的分层仿生神经网络信息模型旨在将多机器人区域搜索过程中的动态环境信息转换为BNN的神经元活性值. 该模型具体包括两层BNN, 其中第一层为区域搜索神经网络信息模型, 将BNN与区域搜索地图状态信息结合; 第二层为区域覆盖神经网络信息模型, 将BNN与区域覆盖地图状态信息结合. 每个机器人均拥有一个单独的分层仿生神经网络信息模型, 并与其他机器人实时交换环境信息与路径决策信息. 在整个多机器人区域搜索过程中, AS-BNN和AC-BNN将根据机器人探测到的环境信息进行实时动态更新.
首先构建AS-BNN, 根据式(5)可以看出, BNN中每个神经元活性值的变化主要取决于外部输入信号$ I_{i} $ (兴奋性输入或抑制性输入)和周围神经元活性值$ \sum_{j=1}^{M_r}w_{ij}[\psi_{j}]^{+} $. 其中$ \sum_{j=1}^{M_r}w_{ij}[\psi_{j}]^{+} $确保兴奋性输入可以在全局传递, 而抑制性输入仅起局部作用. 通过定义适当的外部输入, 将区域搜索地图状态信息与BNN神经元外部输入信号结合, 如式(7)所示. 区域搜索地图中每个栅格将对应AS-BNN中的一个神经元. 未搜索栅格对应的神经元活性值将位于所有神经元活性值的峰值, 而障碍物对应的神经元活性值将位于最低点. 由于正神经元活性值的传播效应, 未被搜索的区域会全局吸引机器人. 此外, 障碍物对应的神经元活性值仅在小范围内具有局部影响, 其排斥作用可使得机器人实现避障. 在制定区域搜索策略时, 机器人通常可以选择向神经元活动值较大的区域移动, 从而规避障碍物, 并避免重复探索同一区域.
$$ \begin{array}{*{20}{l}} I_{i}(x,\;y)=\left\{ \begin{aligned} & E,\; & & {{ S}(G(x,\;y))=K_{\rm u}}\\ & 0,\; & & {{ S}(G(x,\;y))=K_{\rm c}}\\ & - E,\; & & {{ S}(G(x,\;y))=K_{\rm o}} \end{aligned}\right. \end{array} $$ (7) 其中, $ E\gg B $是一个足够大的正值.
其次构建AC-BNN. 在区域搜索任务后期, 可能出现剩余未搜索栅格与机器人之间距离较远的情况. 此外, 由于复杂障碍物的影响, 导致机器人长时间未能找到未搜索区域, 出现局部最优, 此时须引导机器人有效地向未搜索区域运动. 因此, 在AS-BNN基础上, 另外构建AC-BNN, 具体过程为将区域覆盖地图状态信息与BNN中神经元外部输入信号结合, 如式(8)所示. 区域覆盖地图中每个子区域将对应AC-BNN中的一个神经元. 与区域搜索信息模型类似, 未覆盖子区域对应的神经元活性值将处于AC-BNN中所有神经元活性值的顶峰, 而已覆盖子区域对应的神经元由于外部输入信号为0, 其活性值将逐步衰减. 当机器人基于区域搜索神经网络信息模型决策陷入局部最优时, 可结合区域覆盖神经网络信息模型跳出局部最优, 快速完成剩余未搜索区域的探测任务.
$$ \begin{array}{*{20}{l}} I_{i}'(x,\;y)=\left\{ \begin{aligned} & E,\; & & {{ S}(A(\hat{x},\;\hat{y}))=K_{\rm uc}}\\ & 0,\; & & {{ S}(A(\hat{x},\;\hat{y}))=K_{\rm co}} \end{aligned}\right. \end{array} $$ (8) 3. 多机器人协同搜索决策
在分层仿生神经网络信息模型的基础上, 本文进一步引入分布式模型预测控制框架, 用于多机器人协同搜索决策. DMPC的主要特点是利用建立的系统模型预测系统在某一控制动作下的未来动态行为. 在此基础上, 根据给定的约束条件和性能要求, 滚动求解最优控制动作并实现当前控制, 并根据实时信息修正对未来动态行为的预测[29–30]. 每个机器人结合自身和相邻机器人的共享信息进行预测, 规划出下一步运动位置. 此外, 考虑到机器人在搜索过程可能出现局部最优的情况, 本文在DMPC框架下, 结合分层仿生神经网络信息模型, 提出分层协同搜索决策机制.
3.1 DMPC框架
机器人系统的运动模型在式(3)中已经给出, 选择$ [{V^{\rm T} _{s}}(k),\; \theta_s(k)]^{\rm T} $作为系统$ { R}_s $ ($ s=1,\;2,\;\cdots,\;N_r $)的控制输入$ u_{s}(k) $. $ { R}_s $在第$ \,k $步的位置状态为$ h_{s} (k) = [x_{s}(k),\;y_{s}(k)] ^{\rm T} $, 则机器人的位置状态方程记为
$$ \begin{array}{*{20}{l}} h_{s}(k+l|k)=f(h_{s}(k+l-1|k),\;u_{s}(k+l-1|k)) \end{array} $$ (9) 其中, 函数$f(\cdot) $表示机器人的位置状态转移函数, 由式 (3) 决定. $ l=1,\;2,\;\cdots $, $ L $, $ L $是最大预测步数; $ h_{s}(k+l|k) $是基于$ { R}_s $第$\, k+l-1 $步的状态和控制输入信息预测的下一步位置状态.
根据式(9), 如果给定$ { R}_s $的控制输入$ u_{s} (k) $, 则$ { R}_s $的状态由$ h_{s} (k) $转移到$ h_{s} (k+1) $, 栅格地图的状态和神经元活性值也被更新, 从而可以计算出搜索收益函数$ J $的值, 机器人搜索收益函数$ J $如式(10)所示.
$$ \begin{array}{*{20}{l}} J((h_s(k),\; u_s(k))=\lambda_1 J_c(k)+\lambda_2J_t(k) \end{array} $$ (10) 其中, $J_c(k)$是神经元活性值增益函数, $J_t(k)$是转弯代价函数, $\lambda_1$, $\lambda_2$分别是对应函数的权重系数. 建立$J_c(k)$的目的在于利用BNN中正活性值的全局吸引作用, 引导机器人向神经元活性值较大的未搜索区域运动. $J_t(k)$的作用在于减少机器人在搜索过程频繁转弯, 降低能量损耗.
优化求解可以使$ J $最大, 进而计算出最优控制输入$ u_{s} (k) $. 推广到$ L $步的预测, 将每一步的搜索收益函数累加, 得到预测$ L $步的累积搜索效能函数:
$$ \begin{split}& J^{(L)}(h_{s}(k),\;u_{s}(k))=\\ &\qquad\sum\limits_{j=0}^{L-1} J(h_{s}(k+j),\; u_{s}(k+j)) \end{split} $$ (11) 其中, $J(h_{s}(k+j),\; u_{s}(k+j))$为$ { R}_s $预测第$k+j$步的搜索收益. 通过最大化累积搜索效能函数$ J^{(L)} $, 并通过差分进化算法[5, 31]优化求解出$ \,{R}_s $未来$ L $步运动控制输入$ U^{*}(L) $, 如式(12)所示. 考虑到动态变化的环境, 取最优解的第一步$ u_{s}(k) $为$ \,{R}_s $的下一步控制输入. 然后在第$ k+1 $步, 基于新的状态$ h_{s}(k+1) $, 得到一个新的决策序列, 不断滚动优化求解.
$$ \begin{split} &U^{*}(L)={\rm arg\; max\; }J^{(L)}(h_{s}(k),\;u_{s}(k))\\ &{\mathrm{s.t}}.\left\{\begin{aligned} &h_{s}(k+l|k)=f(h_{s}(k+l-1|k),\;\\ &\;\quad u_{s}(k+l-1|k))\\ &l =1,\;2,\;\cdots,\; L \\ &h_{s}(k|k)=h_{s}(k) \end{aligned}\right. \end{split} $$ (12) 其中, $ U^{*}(L) = \left\{u_{s}(k),\; u_{s}(k + 1),\; \cdots ,\; u_{s}(k + L - 1)\right\} $.
3.2 分层协同决策机制
在DMPC框架下, 考虑到机器人在搜索过程可能陷入局部最优状态, 即机器人连续$T$次在预测的路径都没发现未搜索栅格. 虽然BNN正活性值全局吸引作用可保证机器人最终脱离局部最优状态, 但花费时间较长, 对搜索效率会产生较大影响. 因此, 为了提升多机器人系统的搜索效率, 本文基于分层仿生神经网络信息模型进一步提出多机器人分层协同决策机制: 在区域搜索任务中, 当机器人处于正常搜索状态时, 将基于AS-BNN进行搜索路径滚动优化决策; 当机器人陷入局部最优状态时, 则启用AC-BNN进行子区域引导路径预测, 将预测路径经过的第一个子区域作为目标区域, 并结合AS-BNN引导机器人向目标区域移动. DMPC框架下的多机器人分层协同决策机制充分考虑了机器人在执行区域搜索任务时面临的不同情况, 尤其是在搜索任务后期, 当机器人陷入局部最优状态时, 分层协同决策机制基于分层仿生神经网络信息模型中的AC-BNN进行决策, 可快速引导机器人发现新的未搜索区域, 逃离局部最优状态, 从而进一步提升多机器人系统区域搜索效率. 下面分别介绍正常搜索状态下和局部最优状态下的多机器人区域搜索决策过程.
机器人处于正常搜索状态时基于AS-BNN的搜索路径预测方法如下: 机器人$ {R}_s $ ($ s=1, \; 2, \; \cdots, N_r $)在前述DMPC框架下基于式(10) ~ (12)预测其下一步运动控制输入, 而搜索收益函数$ J $具体由神经元活性值增益函数$J_c(k)$和转弯代价函数$J_t(k)$组成. $J_c(k)$的定义如式(13)所示, 若$ {R}_s $预测的位置状态$ h_{s} (k) $与其他机器人预测的位置状态$h_{\sim s}(k)$未发生重叠, 则搜索收益为$B_e(k)$, 否则表明$ {R}_s $与其他机器人出现决策冲突, 相应的搜索收益为$-D$, 即神经元活性值的最小值.
$$ \begin{array}{*{20}{l}} J_c(k)=\left\{ \begin{aligned} &B_e(k),\; & & h_{s} (k)\notin h_{\sim s}(k)\\ & - D,\; & & h_{s} (k)\in h_{\sim s}(k) \end{aligned}\right. \end{array} $$ (13) 其中, $B_e(k)$的定义如(14)所示, 若机器人$ {R}_s $预测的位置$ h_{s} (k) $所处栅格状态为非障碍物, 即$ {{S}} (G(h_{s} (k))) \neq K_ {{\rm o}} $, 则计算$ {R}_s $当前位置覆盖范围内非障碍物栅格对应的神经元活性值均值; 否则表明$ {R}_s $将与障碍物发生碰撞, $B_e(k)$的值为$-D$.
$$ \begin{array}{*{20}{l}} B_e(k)=\left\{ \begin{aligned} &\frac{\sum\limits_{z=1}^{\eta} \psi_s^z(k)}{\eta \psi_{{\rm max} }},\; & & { S} (G(h_{s} (k)))\neq K_{\rm o}\\ &- D,\; & &{ S}(G(h_{s} (k)))=K_{\rm o} \end{aligned}\right. \end{array} $$ (14) 其中, ${{S}} (G(h_{s} (k)))$表示机器人$ {R}_s $当前位置所在栅格$ G(h_{s} (k)) $的状态; $ \psi_s^z(k) $表示$ {R}_s $当前位置探测范围内非障碍物栅格对应的AS-BNN神经元活性值, $ \eta $表示$ {R}_s $当前位置探测范围内的非障碍物栅格数量; $ \psi_{{\rm max} }=B $, 即神经元活性值的最大值. $J_t(k)$的定义如式(15)所示, 是机器人当前位置方向$\theta_s(k)$与前一步位置方向$\theta_s(k-1)$之差的单调递减函数.
$$ J_t(k)=1-\frac{| \theta_s(k)-\theta_s(k-1)|}{\pi}$$ (15) 当机器人$ {R}_s $连续$\,T$次在基于AS-BNN预测的路径上均未发现未搜索栅格时, 表明该机器人陷入了局部最优状态, 此时将启动分层协同决策机制, 其具体决策过程如下: 机器人在DMPC框架下基于AC-BNN进行子区域引导路径预测, 并将其预测经过的第一个子区域作为目标子区域$A(\hat{x}_g,\;\hat{y}_g)$. 区别于搜索路径预测, 子区域引导路径预测过程中神经元活性值增益函数定义如式(16)所示(为区别于式(13), 记为$J_c'(k)$):
$$ \begin{array}{*{20}{l}} J_c'(k)=\left\{ \begin{aligned} & \psi_s'(k),\; & & h_{s}' (k)\notin h'_{\sim s}(k)\\ & - D,\; & & h_{s}' (k)\in h_{\sim s}'(k) \end{aligned}\right. \end{array} $$ (16) 其中, $\psi'_s(k)$表示机器人在覆盖地图上当前位置所处子区域对应的AC-BNN神经元活性值, $h_{s}' (k)$表示机器人$ {R}_s $在覆盖地图中的第$k$步所处位置状态$(\hat{x}_{s}(k), \hat{y}_{s}(k))$, $h_{\sim s}'(k)$表示除$ {R}_s $外其他机器人预测的第$k$步所处位置状态. 相应地, 子区域路径预测过程中搜索收益函数$J_E$定义更新如下:
$$ \begin{array}{*{20}{l}} J_E\left((h_s'(k),\;\ u_s(k)\right)=\lambda_1 J_c'(k)+\lambda_2J_t(k) \end{array} $$ (17) 机器人基于式(17)和式 (12)获取预测的目标子区域位置$A(\hat{x}_g,\;\hat{y}_g)$后, 为引导机器人向目标子区域移动, 结合AS-BNN进行目标子区域搜索路径预测, 在式(10)中增加新的引导函数$J_g(k)$, 相应的搜索收益函数由式(10)替换为式(18). 机器人将基于式(18)和式 (12)进行目标子区域搜索路径预测.
$$ J_H((h_s(k),\; u_s(k))=\lambda_1 J_c(k)+\lambda_2J_t(k)+\lambda_3 J_g(k) $$ (18) 其中, $\lambda_1$, $\lambda_2$, $\lambda_3$分别是对应函数的权重系数; $J_g(k)$的定义如下
$$ \begin{array}{*{20}{l}} J_g(k)=\left\{ \begin{aligned} & B_g(k),\; & & G(h_{s} (k))\in A(\hat{x}_g,\;\hat{y}_g)\\ &0,\; & & G(h_{s} (k))\notin A(\hat{x}_g,\;\hat{y}_g) \end{aligned}\right. \end{array} $$ (19) 当机器人第$k$步的位置处于目标子区域时, 则根据机器人在栅格地图中所占据栅格状态${{S}} (G(h_{s} (k)))$设定$B_g(k)$的值, $B_g(k)$的定义如式(20)所示. 当机器人所处目标子区域内的栅格未搜索时 (${{S}} (G(h_{s} (k))) = K_{\rm{u}} $), $B_g(k)$的值为$\psi'_s(k)$, 其目的是吸引机器人朝目标子区域运动; 当机器人所处目标子区域内的栅格为自由栅格时, $B_g(k)$的值为$c_1\psi'_s(k)$, 其中$c_1$为权重系数, $c_1\in (0,\;1)$, 即对$\psi'_s(k)$的值进行一定衰减; 当机器人所处目标子区域内的栅格为障碍物栅格时, $B_g(k)$的值为$-D$, 其目的是吸引机器人朝目标子区域移动的同时, 避免机器人与该区域内的障碍物发生碰撞.
$$ \begin{array}{*{20}{l}} B_g(k)=\left\{ \begin{aligned} & \psi_s'(k),\; & & {S} (G(h_{s} (k)))= K_{\rm u}\\& c_1\psi_s'(k),\; & & {S} (G(h_{s} (k)))= K_{\rm c}\\& - D,\; & &{S}(G(h_{s} (k)))=K_{\rm o} \end{aligned}\right. \end{array} $$ (20) 当满足以下条件之一时, 机器人将进入新的局部最优状态判断周期, 并重新基于AS-BNN进行搜索路径决策, 直至区域搜索任务结束: 1)搜索路径预测发现未搜索栅格; 2)机器人偏离子区域预测路径或到达目标区域. 对于多机器人系统中的任意机器人$ { R}_s $ ($ s=1,\;2,\;\cdots,\;N_r $), 其决策流程如图4所示. 需要指出的是, 多机器人系统区域搜索任务完毕的条件可分为两种情况: 当任务区域内目标数量已知时, 如果目标全部被找到, 则区域搜索任务终止; 当目标数量未知时, 则多机器人系统需要将整个区域搜索完毕, 才视为任务终止.
3.3 算法稳定性分析
本文所提出的多机器人协同区域搜索算法具备稳定性和收敛性, 具体分析如下: 多机器人系统在执行区域搜索任务时基于分层仿生神经网络信息模型进行滚动优化决策, 该信息模型由两层BNN构成(AS-BNN和AC-BNN). 而BNN的稳定性和收敛性证明过程如下, 通过构造新的变量$ \varphi_i=\psi_i-B $, 则可由式(5)得到式(21):
$$ \begin{split} \frac{{\rm d}\varphi_i}{{\rm d}t}=\;&-\varphi_i\Bigg(\frac{1}{\varphi_i}(AB+\varphi_i(A+[I_{i}]^++[I_{i}]^-)\;+\\&(B+D)[I_{i}]^-)-\sum\limits_{j=1}^{M_r}(-w_{ij})[B+\varphi_j]^+\Bigg) \end{split} $$ (21) 然后, 在式(21)中的模型可以写成Grossberg的一般形式[32]
$$ \frac{{\rm d}\varphi_{i}}{{\rm d}t}=a_i(\varphi_i)\left(b_i(\varphi_i)-\sum\limits_{j=1}^{M_r}c_{ij}d_j(\varphi_j)\right) $$ (22) 其中
$$ \begin{array}{*{20}{l}} a_i(\varphi_i)=-\varphi_i \end{array} $$ (23) $$ \begin{split} b_i(\varphi_i)=\;&\frac{1}{\varphi_i}(AB+\varphi_i(A+[I_{i}]^++[I_{i}]^-)\;+\\ &(B+D)[I_{i}]^-) \end{split} $$ (24) $$ \begin{array}{*{20}{l}} c_{ij}=-w_{ij} \end{array} $$ (25) $$ \begin{array}{*{20}{l}} d_j(\varphi_j)=[B+\varphi_j]^+ \end{array} $$ (26) 根据式(6), 神经元之间的连接权值是对称的, 即$ w_{ij}=w_{ji} $, 相应地, $ c_{ij}= c_{ji} $. 由于 $ \psi_{i}\in[-D,\;B] $, $ \varphi_{i}\in[-B-D,\;0] $, 其中$ B $, $ D $是非负常数, 则$ \varphi_{i} $ 是非正数. 因此缩放函数$ a_i(\varphi_i) $ 是非负的, 即 $ a_i(\varphi_i)\geq 0 $. 从函数 $ [B+\varphi_j]^{+} $ 的定义看, 当 $ \varphi_j< -B $ 时, $ {\rm d}(d_j (\varphi _j))/{{\rm d} t}=0 $; 当 $ \varphi_j\geq-B $ 时, $ {{\rm d} (d_j(\varphi _j))}/ {{\rm d} t}= 1 $. 因此, 函数 $ d_j(\varphi_j) $ 的导数非负$\left( {{\rm d} (d_j(\varphi _j))}/ {{\rm d}t}\geq0 \right)$. 根据上述推导, 式(5) 全部满足Grossberg一般形式要求的三个稳定性条件[32], 如式(27)所示, 可以保证BNN系统模型的稳定性和收敛性.
$$ \begin{array}{*{20}{l}} \; c_{ij}=c_{ji},\; \; a_i(\varphi_i)\geq0, \; \; \dfrac{{\rm d} (d_j(\varphi _j))}{{\rm d} t}\geq0 \end{array} $$ (27) 在提出的分层协同决策机制中, 机器人无论是基于AS-BNN或者基于AC-BNN进行决策, 每个机器人始终保持向神经元活性值高的区域(未搜索区域)前进. 由于BNN中正活性值对机器人的全局吸引特性, 当AS-BNN和AC-BNN中所有神经元活性值均收敛到均衡时, 多机器人能够完成区域搜索任务. 由于在前述分析中已证明BNN是稳定和收敛的, 因此, 本文所提出的多机器人协同区域搜索算法具备稳定性和收敛性.
4. 仿真实验与分析
为了验证算法的有效性, 本文利用MATLAB软件搭建区域搜索平台进行仿真实验, 如图5所示, 任务区域面积大小为30$ \times $30个栅格单元, 每个栅格单元的面积为1 m2, 区域内包括各种形状的障碍物, $s_f$= 2. 总共6 ($N_r=6$)个机器人参与区域搜索任务, 其中每个机器人占据一个栅格, 探测范围为3$ \times $3个栅格 ($m,\;n=3$). 在初始时刻, 所有机器人均无先验环境信息, 包括任务区域内障碍物的分布情况和目标分布情况. 多机器人之间可以进行全局通信, 交换其在区域搜索过程中获取的环境信息、自身的位置信息以及搜索路径决策信息. 根据文献[7]、文献[33]对BNN中参数$A$, $B$, $D$的设置讨论, BNN模型对参数不敏感. 同时, 一般$E$> $2B $. BNN参数设置如下: $ A $ = 0.2, $ B $ = 0.5, $ D $ = 0.5, $ E $ = 2. 分层协同搜索决策机制如下: $L$ = 3; $\lambda_1$ = 0.9, $\lambda_2$ = 0.1, $\lambda_3$= 0.8; $c_1$ = 0.5, $T$ = 3.
4.1 算法有效性验证
本节通过一个多机器人系统区域搜索任务来验证所提算法的有效性. 设置6个机器人的初始位置为 $ {R_1 } $ (1, 22), $ {R_2 } $ (24, 30), $ {R_3 } $ (1, 3), $ {R_4 } $ (16, 1), $ {R_5 } $ (18, 30), $ {R_6 } $ (1, 30). 多机器人在不同时刻的区域搜索轨迹如图6所示. 相应的神经元活性值分布如图7所示. 由于任务区域的环境信息未知, 在搜索过程中, 机器人不断地探测周围环境信息, 并更新分层仿生神经网络信息模型中对应的神经元活性值. 未搜索栅格对应的神经元活性值始终保持在所有神经元活性值中的峰值. 对于自由栅格, 随着外部正激励信号的减弱, 活性值逐渐减小为0. 当机器人探测到障碍物或其他机器人时, 其相应位置对应的神经元将处于所有神经元活性值中的最低值.
图 6 六个机器人在区域搜索过程中不同时刻下的搜索轨迹Fig. 6 The search trajectories of six robots at different moments during the area search process
图 7 分层仿生神经网络信息模型在区域搜索过程中不同时刻下的活性值Fig. 7 The activity values of the hierarchical bio-inspired neural network information model at different moments during the area search process在正常搜索状态下, 每个机器人在DMPC框架下基于AS-BNN进行滚动优化决策, 朝神经元活性值较高的区域运动, 每个机器人将其他机器人视作动态障碍物, 对应的活性值最小, 如图7(a)、图7(b)、图7(d)所示. 当机器人运动步数$k$为47时, 如图6(b)所示, 机器人$ { R_3 } $连续3步在基于AS-BNN预测的路径上均没发现未搜索栅格, 表明其陷入了局部最优状态. 此时启用AC-BNN(图7(c))进行子区域引导路径预测, 并选择预测路径中经过的第一个子区域$A(7,\;13)$作为目标子区域. 再结合AS-BNN引导机器人$ { R_3 } $向其运动, 如图6(c)所示. 重复上述子区域引导路径预测过程, 当机器人运动步数$k$为51时, 将成功找到未搜索栅格$G(16,\;25)$, 并抵达该栅格所在子区域$A(8,\;13)$, 如图6(d) ~ 6(e)所示.
当机器人运动步数$k$为84时, 整个任务区域完全被探测, 此时区域搜索任务结束. 从图6可以看到, 在没有环境先验信息的情况下, 每个机器人都可以实时规划搜索路径. 此外, 每个机器人在运动过程中不会与障碍物或其他机器人发生碰撞, 机器人之间轨迹很少重叠, 验证了本文所提区域搜索算法的有效性.
4.2 算法比较与分析
为了验证所提算法的优越性, 选取3种算法作为基线, 它们分别是原始的BNN算法[26]、A-RPSO算法[12]和DCRS算法[6]. 图8(a) ~ 8(d)显示了4种算法在复杂未知环境中生成的搜索轨迹(运动时间步长: 84), 表2统计了4种算法对应的搜索性能, 包括区域覆盖率与平均决策时间. 从图8看到BNN算法和A-RPSO算法在复杂未知环境下未能引导多机器人有效搜索障碍物周围区域, 区域覆盖率分别为94.11%和90.33%. 这表明它们在适应复杂未知环境方面存在挑战. 而DCRS算法虽然在区域覆盖率上达到了97.56%, 但任务区域左上角却被忽略, 且机器人没有向其运动的趋势, 表明机器人在复杂环境下陷入了局部最优状态. 相比于其他3种算法, 本文所提算法在相同时间下已经完成了整个任务区域的搜索, 区域覆盖率为100%. 图8(e)展示了4种算法在区域搜索过程中的覆盖率变化, 可以看到本文算法和DCRS算法在前期搜索速度均高于原始BNN算法和A-RPSO算法, 而本文算法在中后期搜索速度均高于其他3种算法, 表明本文算法相较于其他3种算法具备更高的搜索效率. 在平均决策时间方面, 4种算法的平均决策时间分别是
0.0156 s (BNN算法)、0.0181 s (A-RPSO算法)、0.0251 s (DCRS算法)、0.0214 s (本文算法). 本文算法的平均决策时间略高于BNN算法和A-RPSO算法, 但远低于DCRS算法, 在提升搜索效率的同时不影响多机器人系统在区域搜索任务过程中的实时运动决策.
图 8 六个机器人在不同算法驱动下的区域搜索轨迹Fig. 8 Six robots search trajectories in a region driven by different algorithms此外, 本文还进一步验证了不同机器人数量下4种算法在复杂未知环境下的区域搜索性能. 在不同机器人数量下随机设置50组不同的多机器人起始位置, 进行仿真实验. 统计50次仿真实验过程中的平均覆盖率 (Average coverage, AVE-C)、覆盖率标准差 (Standard deviation of coverage, STD-C)、最高覆盖率 (Maximum coverage, MAX-C)、最低覆盖率 (Minimum coverage, MIN-C)作为性能指标, 相应的仿真结果如表3所示. 可以看到, 当机器人数量为2时, 本文所提算法和DCRS算法的平均覆盖率分别为99.564%和97.164%, 远高于BNN算法 (84.047%) 和A-RPSO算法 (82.764%). 此外, 本文算法不仅在平均覆盖率上高于其他3种算法, 同时在覆盖率标准差上均低于其他3种算法. 说明本文所提算法在提升多机器人区域搜索效率的同时也增强了对环境的适应性. 随着机器人数量依次增加为4、6、8, 本文算法始终在搜索性能上保持了领先(平均覆盖率均超过99%). 当机器人数量为8时, 4种算法的平均覆盖率分别是82.489% (BNN算法)、88.438% (A-RPSO算法)、96.106% (DCRS算法)、99.428% (本文算法), 覆盖率标准差为
0.0712 (BNN算法)、0.0309 (A-RPSO算法)、0.0231 (DCRS算法)、0.0057 (本文算法), 本文所提算法在平均覆盖率和覆盖率标准差上均占优. 在不同机器人数量下仿真实验的最高覆盖率和最低覆盖率方面, 本文所提算法的最高覆盖率均达100.000%, 最低覆盖率均超过98%, 而其他算法的最高覆盖率和最低覆盖率均出现大幅波动. 上述结果充分验证了本文所提算法应用在复杂未知环境下多机器人区域搜索任务的优越性.表 3 不同机器人数量下4种算法区域搜索性能对比Table 3 Comparison of area search performance of four algorithms under different number of robots机器人
数量运动
步数BNN算法[26] A-RPSO算法[12] DCRS算法[6] 本文所提算法 AVE-C STD-C MAX-C MIN-C AVE-C STD-C MAX-C MIN-C AVE-C STD-C MAX-C MIN-C AVE-C STD-C MAX-C MIN-C 2 252 84.047% 0.1375 93.556% 72.111% 82.764% 0.0893 94.000% 64.333% 97.164% 0.0330 100.000% 83.556% 99.564% 0.0062 100.000% 98.778% 4 126 84.592% 0.0737 96.556% 76.333% 85.500% 0.0631 96.111% 65.000% 96.836% 0.0232 99.667% 91.111% 99.656% 0.0039 100.000% 99.111% 6 84 86.290% 0.0843 95.667% 75.556% 88.587% 0.0391 93.778% 82.889% 97.438% 0.0162 99.889% 92.778% 99.596% 0.0070 100.000% 98.778% 8 56 82.489% 0.0712 92.444% 71.333% 88.438% 0.0309 93.333% 80.111% 96.106% 0.0231 99.111% 87.444% 99.428% 0.0057 100.000% 98.889% 5. 结束语
本文针对复杂未知环境下的区域搜索问题, 提出一种新的基于分层仿生神经网络的多机器人协同区域搜索算法. 该算法主要由两个部分组成: 分层仿生神经网络信息模型以及多机器人分层协同决策机制. 在分层仿生神经网络信息模型中, 两层信息模型(AS-BNN和AC-BNN)对应的神经元活性值信息构成了机器人不同状态下的决策基础. 此外, 本文设计了一种分层协同决策机制来引导机器人摆脱复杂未知环境中可能出现的局部最优状态. 这种机制确保了机器人的高效搜索能力, 同时避免了多机器人间决策冲突和搜索路径重复. 仿真结果验证了本文所提算法对复杂未知环境下多机器人区域搜索任务的有效性. 与3种基线算法相比, 所提算法具备更高的区域搜索效率, 表明本文所提算法在应对复杂未知环境下区域搜索任务的优越性. 在未来的工作中, 我们将研究大范围任务区域下多机器人协同搜索问题, 并考虑进一步增大机器人数量规模后相应的区域搜索策略.
-
图 5 ER网络
$V_{I}$ 和$V_{O}$ 失效可控性变化Fig. 5 Controllability changes of
$V_{I}$ and$V_{O}$ failure in ER networks
图 6 BA网络
$V_{I}$ 和$V_{O}$ 失效可控性变化Fig. 6 Controllability changes of
$V_{I}$ and$V_{O}$ failure in BA networks
图 7 WS网络
$V_{I}$ 和$V_{O}$ 失效可控性变化Fig. 7 Controllability changes of
$V_{I}$ and$V_{O}$ failure in WS networks
图 8 ER网络
$V_{IO}$ 失效可控性变化Fig. 8 Controllability changes of
$V_{IO}$ f ailure in ER networks
图 9 BA网络
$V_{IO}$ 失效可控性变化Fig. 9 Controllability changes of
$V_{IO}$ failure in BA networks
图 10 WS网络
$V_{IO}$ 失效可控性变化Fig. 10 Controllability changes of
$V_{IO}$ failure in WS networks表 1 模型网络不同类型节点占比表
Table 1 Proportion of different types of nodes in the model network
ER网络 BA网络 WS网络 节点数 500 500 500 边数 2485 1968 1000 INM 27 25 0 IM 24 43 0 ONM 24 46 10 OM 31 39 2 INM&ONM 272 266 358 INM&OM 51 48 105 IM&ONM 42 33 20 IM&OM 32 0 5 $ V_{D}$ 0 0 0 
下载: 导出CSV
表 2 实际网络不同类型节点占比表
Table 2 Proportion of different types of nodes in the actual network
经理社交网络 律师社交网络 银行员工社交网络 (1) 银行员工社交网络 (2) 银行员工社交网络 (3) 学生社交网络 (1) 学生社交网络 (2) 节点 21 71 11 11 11 73 73 边 190 892 30 51 27 243 263 $\langle k \rangle$ 9.05 12.56 2.73 4.64 2.54 3.33 3.60 INM 0 1 1 2 1 1 1 IM 3 0 0 0 0 0 0 ONM 0 1 2 0 0 4 4 OM 0 0 1 0 1 2 2 INM&ONM 18 67 3 8 3 44 47 INM&OM 0 2 1 0 3 13 10 IM&ONM 0 0 3 0 2 3 5 IM&OM 0 0 0 0 1 3 0 $V_{D} $ 0 0 0 0 0 3 4
下载: 导出CSV
-
[1] Watts D J. The “new” science of networks. Annual Review of Sociology, 2004, 30(1): 243-270 doi: 10.1146/annurev.soc.30.020404.104342 [2] Yan G, Vértes P E, Towlson E K, Chew Y L, Walker D s, Schafer W R. Network control principles predict neuron function in the caenorhabditis elegans connectome. Nature, 2017, 550(7677): 519-523 doi: 10.1038/nature24056 [3] Zhang Z K, Liu C, Zhan X X, Lu X, Zhang C X, Zhang Y C. Dynamics of information diffusion and its applications on complex networks. Physics Reports, 2016, 651(1): 1-34 [4] Urena R, Kou G, Dong Y C, Chiclana F, Herrera-Viedma E. A review on trust propagation and opinion dynamics in social networks and group decision making frameworks. Information Sciences, 2019, 478(1): 461-475 [5] 任卓明. 动态复杂网络节点影响力的研究进展. 物理学报, 2020, 69(4): 048901 doi: 10.7498/aps.69.20190830Ren Zhuo-Ming. Research progress of node influence in dynamic complex networks. Acta Physica Sinica, 2020, 69(4): 048901 doi: 10.7498/aps.69.20190830 [6] Li A, Cornelius S P, Liu Y Y, Wang L, Barabási A L. The fundamental advantages of temporal networks. Science, 2017, 358(6366): 1042-1046 doi: 10.1126/science.aai7488 [7] Gao J X, Liu Y Y, D'Souza R M, Barabási A L. Target control of complex networks. Nature Communications, 2014, 5(1): 5415-5422 doi: 10.1038/ncomms6415 [8] Wang X F, Chen G R. Pinning control of scale-free dynamical networks. Physica A, 2002, 310(3): 521-531 [9] Li X, Wang X F, Chen G R. Pinning a complex dynamical network to its equilibrium. IEEE Transactions on Circuits and Systems I: Regular Papers, 2004, 51(10): 2074-2087 doi: 10.1109/TCSI.2004.835655 [10] Liu X W, Chen T P. Cluster synchronization in directed networks via intermittent pinning control. IEEE Transactions on Neural Networks, 2011, 22(7): 1009-1020 doi: 10.1109/TNN.2011.2139224 [11] Liu X W, Chen T P. Finite-time and fixed-time cluster synchronization with or without pinning control. IEEE Transactions on Cybernetics, 2018, 48(1): 240-252 doi: 10.1109/TCYB.2016.2630703 [12] Yu W W, DeLellis P, Chen G R. Distributed adaptive control of synchronization in complex networks. IEEE Transactions on Automatic Control, 2012, 57(8): 2153-2158 doi: 10.1109/TAC.2012.2183190 [13] Su H S, Rong Z H, Chen M Z. Decentralized adaptive pinning control for cluster synchronization of complex dynamical networks. IEEE Transactions on Cybernetics, 2013, 43(1): 394-399 doi: 10.1109/TSMCB.2012.2202647 [14] 杨青林, 王立夫, 李欢, 余牧舟. 基于相对距离的复杂网络谱粗粒化方法. 物理学报, 2019, 68(10): 100501 doi: 10.7498/aps.68.20181848Yang Qing-Lin, Wang Li-Fu, Li Huan, Yu Mu-Zhou. A spectral coarse-graining algorithm based on relative distance. Acta Physica Sinica, 2019, 68(10): 100501 doi: 10.7498/aps.68.20181848 [15] 王振华, 刘宗华. 复杂网络上的部分同步化: 奇异态、遥同步与集团同步. 物理学报, 2020, 69(8): 088902 doi: 10.7498/aps.69.20191973Wang Zhen-Hua, Liu Zong-Hua. Partial synchronization on complex networks: singular state, remote synchronization and group synchronization. Acta Physica Sinica, 2020, 69(8): 088902 doi: 10.7498/aps.69.20191973 [16] Ren H R, Karimi H R, Lu R Q, Wu Y Q. Synchronization of network systems via aperiodic sampled-data control with constant delay and application to unmanned ground vehicles. IEEE Transactions on Industrial Electronics, 2020, 67(6): 4980-4990 doi: 10.1109/TIE.2019.2928241 [17] 张檬, 韩敏. 基于单向耦合法的不确定复杂网络间有限时间同步. 自动化学报, 2020, 46(x): 1-9Zhang Meng, Han Min. Finite-time synchronization between uncertain complex networks based on unidirectional coupling method. Acta Automatica Sinica, 2020, 46(x): 1-9 [18] 潘永昊, 于洪涛. 基于网络同步的链路预测连边机理分析研究. 自动化学报, 2020, 46(12): 2607-2616Pan Yong-Hao, Yu Hong-Tao. Analysis of linkage mechanism of link prediction based on network synchronization. Acta Automatica Sinica, 2020, 46(12): 2607-2616 [19] 郭天姣, 涂俐兰. 噪声下相互依存网络的自适应 $ H_{\infty}$ 异质同步. 自动化学报, 2020, 46(6): 1229-1239GUO Tian-Jiao, TU Li-Lan. Adaptive$ H_{\infty}$ Heterogeneous Synchronization for 0.3 nterdependent Networks With Noise. Acta Automatica Sinica, 2020, 46(6): 1229-1239[20] Ren H R, Lu R Q, Xiong J L, Wu Y Q, Shi P. Optimal filtered and smoothed estimators for discrete-time linear systems with multiple packet dropouts under markovian communication constraints. IEEE Transactions on Cybernetics, 2020, 50(9): 4169-4180 doi: 10.1109/TCYB.2019.2924485 [21] Liu Y Y, Slotine J J, Barabási A L. Controllability of complex networks. Nature, 2011, 473(7346): 167-173 doi: 10.1038/nature10011 [22] Yuan Z, Zhao C, Di Z, Wang W X, Lai Y C. Exact controllability of complex networks. Nature Communications, 2013, 4(1): 2447-2455 doi: 10.1038/ncomms3447 [23] Posfai M, Hovel P. Structural controllability of temporal networks. New Journal of Physics, 2014, 16(12): 123055 doi: 10.1088/1367-2630/16/12/123055 [24] Wu J N, Li X, Chen G R. Controllability of deep-coupling dynamical networks. IEEE Transactions on Circuits and Systems I: Regular Papers, 2020, 67(12): 1-12 doi: 10.1109/TCSI.2020.3033927 [25] Tommaso M, Danielle S. Bassett, Fabio P. Structural controllability of symmetric networks IEEE Transactions on Automatic Control, 2019, 64(9): 3740-3747 doi: 10.1109/TAC.2018.2881112 [26] Sun C, Hu G Q, Xie L H. Controllability of multi-agent networks with antagonistic interactions. IEEE Transactions on Automatic Control, 2017, 62(10): 5457-5462 doi: 10.1109/TAC.2017.2697202 [27] Posfai M, Gao J, Cornelius S P, Barabási A L. Controllability of multiplex multi-time-scale networks. Physical Review E, 2016, 94(3): 032316 [28] Pu C L, Pei W J, Michaelson A. Robustness analysis of network controllability. Physica A, 2012, 391(18): 4420-4425 doi: 10.1016/j.physa.2012.04.019 [29] Liu Y Y, Slotine J J, Barabási A L. Control centrality and hierarchical structure in complex networks. PloS One, 2012, 7(9): e44459 doi: 10.1371/journal.pone.0044459 [30] Lu Z M, Li X F. Attack vulnerability of network controllability. PloS One, 2016, 11(9): e0162289 doi: 10.1371/journal.pone.0162289 [31] Pu C L, Cui W. Vulnerability of complex networks under path-based attacks. Physica A: Statistical Mechanics and its Applications, 2015, 419(1): 622-629 [32] Hopcroft J E, Karp R M. An $ n.{5/2}$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 1971, 2(4): 122-125[33] Erdos P, Renyi A. On random graphs. Publicationes Mathematicae, 1959, 6(1): 290-297 [34] Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509-512 doi: 10.1126/science.286.5439.509 [35] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks. Nature, 1998, 393(6684): 440-442 doi: 10.1038/30918 [36] Coleman J S. Introduction to mathermatical sociology[Online], available: http://moreno.ss.uci.edu/data.html, September 10, 2020 -
下载:
计量
- 文章访问数: 1553
- HTML全文浏览量: 548
- PDF下载量: 222
- 被引次数: 0
