汪志文 郑州轻工业大学食品与生物工程学院

摘要

本文设计了一个可行的纳米机器人集群运动系统：基于粒子群优化的元启发算法思想，使用Boids模型进行集群运动模拟；个体使用Elman神经网络，结合Vicsek和Kuramoto模型的趋于有序同步作用，实现使局部无序以在恢复稳态过程中改变集群运动状态的调节机制，达到分布式控制目的协调运动方案。

1 集群运动算法及模型

1.1 粒子群优化

在计算科学中，粒子群优化(PSO)是一种计算方法，它通过迭代尝试改进给定质量度量的候选解决方案来优化问题。它通过拥有一组候选解决方案（此处称为粒子）并根据粒子位置和速度的简单数学公式在搜索空间中移动这些粒子来解决问题。每个粒子的运动都受到其局部已知最佳位置的影响，但也会被引导至搜索空间中的最佳已知位置，这些位置会随着其他粒子找到更好的位置而更新。预计这将使群体走向最佳解决方案。粒子群优化最初旨在模拟社会行为，作为鸟群或鱼群中生物体运动的程式化表示

在计算机科学和数学优化中，元启发是一种高级的程序或启发式算法，专门用于搜索、生成或选取一个启发式结果（局部搜索算法），该结果可以为一个最优化问题提供足够好的解，尤其适用于信息不完备或者计算能力受限时的最优化问题。

1.2 Boids模型

Boids是一个人工生命模拟程序，由Craig Reynolds于1986年开发，模拟鸟类的集群行为。与大多数人工生命模拟程序一样，Boids 是涌现现象的一个例子。也就是说，Boids 的复杂性源于遵守一组简单规则的各个个体的交互。最简单的Boids模型应用的规则如下：

排斥：避免拥挤同伴

校准：转向同伴的平均方向

凝聚：转向同伴的平均位置（质心）

可以添加更复杂的规则，例如避障和目标寻找。

1.2.1 基于Boids模型的集群可视化

将这三个规则转化为具有周期性边界条件的 3D 空间中的微分⽅程：

每个个体 i 的位置根据速度Vi,确定地迭代更新。凝聚、排斥和校准规则分别由第一项、第二项和第三项表示。 每个规则在每个个体周围都有一个交互范围，分别用 Satt, Srep, 和 Sali 表示。 在方程中，这些相互作用的幅度分别由Watt ，Wrep 和Wali给出。 相互作用范围（其角度为 3D 圆形扇区）分别固定为 ∕2、∕2 和 ∕3。 为了避免速度过度增加或减少，将速度幅度限制在Vmin和Vmax之间，可以认为这是重要参数。

图1 模拟结果的⼆维投影，可以观察到球状图案和绳状图案，绳状群体通过个体快速⻜⾏将球状群体连接起来

如图所示，个体通过呈现特征形状不均匀地分布在空间中。 许多集群相互影响并动态变化。 不同群体规模分布呈现幂律，且规模存在不同类型的波动。

分析结果都取决于我们如何对群体进行分类以及我们应用什么类型的算法。我们主要应用了聚类算法：DBSCAN 是一种基于密度的聚类算法，它统计超过k个点包围的内部点以及与内部点相邻但被稀疏地包围的外围点。

图2 快速组和慢速组的DBSCAN聚类结果（不同的颜⾊代表不同的群体）

图2展示了一个在根据速度幅度将所有个体分为两类后对不同群体进行分类的示例。然后我们将DBSCAN应用于每个组，以查看不同群体在空间上的分布情况。最意想不到的观察是快速移动的个体存在于较大的群体的表面，也可以形成绳状的群体。 群体是暂时组织起来的，会自发地产生或崩溃。通过简单的观察，个体通过形成绳状模式逃离群体。

1.2.2 基于Boids模型规则的⻥群模型

图3 鱼群模型示意图。每个个体i都有一个位置ci和一个方向vi，排斥区域由半径为rr的圆表示，而取向和吸引区域由内半径rr和外半径rp的圆环表示。所有个体都有f度的视野和 (2-f)度的盲区。

在集体行为模型中，有两条规则在模拟中起着至关重要的作用。在第一条规则中，个人试图始终保持自己与他人之间的最小距离。该规则具有最高优先级，并且对应于自然界中动物经常观察到的行为。在第二条规则中，如果个体没有执行回避策略来保持最小距离，他们往往会被其他个体吸引（以避免被孤立）并与邻居保持一致。这些行为倾向是使用局部感知和简单的反应行为来模拟的。

此例研究实现了最初由Couzin提出并由Li修改的鱼群模型。在这个模型中，每个个体对其所占据的空间都有严格的局部感知。群体中的任何个体都无法完全了解整个群体。因此，每个个体在做出决定时都必须仅考虑从其视野f感知到的附近邻居。

群体由n个个体组成。在时间t，每个个体i都有位置ci(t)、方向vi(t)、速度si和最大转动速率 θ（图 3）。个体通过考虑两个行为区域内的邻居来确定新的期望行进方向。第一个区域称为排斥区域，具有局部相互作用范围rr。每个个体都试图通过转身来避免自己与该区域中的其他个体j发生碰撞。

此行为始终具有最高优先级。如果在排斥区域中没有检测到邻居，那么个体i倾向于与第二个区域（称为取向和吸引区域）中的j个邻居对齐。该区域是围绕个体的内半径rr和外半径rp的环。在这种情况下所需的行进方向是：

ωa和ωo分别是吸引力和方向的权重。通过这些权重，个体可以平衡他们的取向和吸引偏好。例如，如果ωo > ωa，个体更感兴趣的是确定与邻居的行进方向，而不是对邻居的吸引力，而如果权重大致相同，个体会平衡其取向和吸引偏好。通过将向量di旋转一个从正态分布绘制的角度，可以将随机性包含在模型中，从而给出所需的行进方向。由于个体只能在一个单位时间步骤内转动 θΔt 弧度，因此如果di(t)和di(t+Δt)之间的角度大于 θΔt，则不考虑所取方向，并且个体朝该方向旋转 θΔt。同时，如果角度小于 θΔt，则个体位置更新为

其中di是归一化向量。在计算所需方向时，我们认为方向和排斥区域具有(2-f)度的盲区，这些区域内的邻居无法被检测到，而对于排斥区域和取向区域，个体可与邻居进行通信。

以上所示的模型需要识别全部个体，特别是确定落在排斥区域以及取向和吸引区域内的所有个体。 暴力方法需要O(n­2)的步骤进行邻近筛选，即将每个个体与所有其他个体进行比较，并统计rr和rp范围内的所有个体。

根据以上集群运动算法及模型，我们可以建立描述纳米机器人实际运动状况的理想模型，从而为下文集群动态协调运动控制系统的设计奠定基础。

2 集群动态协调运动控制系统

2.1 Vicsek模型和Kuramoto模型

2.1.1 Vicsek模型

Vicsek模型是用于描述集体运动的数学模型。物理学家研究集体运动的动机之一是与该领域相关的大量现象，群聚是研究最多的现象之一。在为从微观描述中捕捉此类行为而开发的大量模型中，最著名的是 Tamás Vicsek 等人在1995年提出的Vicsek模型。

物理学家对这个模型非常感兴趣，因为它是最小化的并且描述了一种普遍性。它由点状自驱动粒子组成，这些粒子以恒定的速度演化，并在存在噪声的情况下使其速度与其邻居的速度一致。这样的模型显示了高密度粒子的集体运动或排列上低噪声的情况。

由于该模型的目标是最小化，因此它假设聚集是由于任何类型的自推进和有效对准的组合所致。个体 i 由在时间 t 时其位置 ri(t) 和其速度偏向角 Θi(t)来描述。 一个粒子的离散时间演化由两个方程设定：

在每个时间间隔Δ t内，每个个体在给定距离 r 内与其邻居对齐，由于噪声而具有不确定性 ηi(t) ：

然后粒子以恒定速度 v 朝着新的方向运动：

该模型显示了从无序运动到大规模有序运动的相变。在大噪声或低密度下，颗粒平均不排列，可以将它们描述为无序气体。在低噪声和大密度下，粒子全局排列并沿同一方向移动（集体运动）。这种状态被解释为有序液体。这两个相之间的转变不是连续的，实际上系统的相图表现出具有微相分离的一级相变。在共存区域中，有限尺寸的液体带出现在气体环境中并沿其横向移动。最近发现了一个新的相位：具有固有选择的交叉角的密度波的极序方波相位。 这种粒子的自发组织体现了集体运动。

2.1.2 Kuramoto模型

Kuramoto模型由Yoshiki Kuramoto首先提出，是用于描述同步的数学模型。更具体地说，它是一大组耦合振荡器的行为模型。它的制定受到化学和生物振荡器系统行为的启发，并且在神经科学和振荡火焰动力学等领域得到了广泛的应用。该模型做出了几个假设，包括存在弱耦合，即振荡器相同或几乎相同，以及相互作用取决于每对物体之间的相位差。

在最流行的 Kuramoto 模型版本中，每个振荡器都被认为具有自己的固有频率 ωi，并且每个振荡器都与所有其他振荡器同等耦合。这个完全非线性模型可以在无限振子的极限下精确求解，或者使用自洽论证也可以获得阶次参数的稳态解。

最流行的模型版本具有以下控制方程：

其中系统由N个极限环振荡器组成，具有相位 θi 和耦合常数K。

噪声可以添加到系统中，在这种情况下，原方程改为

其中ζi是波动和时间的函数。如果我们认为噪声是白噪声，那么

其中 D表示噪声的强度。

Vicsek模型揭示了粒子从无序运动到有序运动的相变原理，而Kuramoto模型可描述耦合振荡器的行为及相互作用，这两个模型共同反映了粒子群（可视为一种振荡器）整体从无序到有序的状态转移，是集群动态协调运动控制系统的基本原理及数学描述。

2.2 Elman神经网络

Elman神经网络是一种典型的局部回归网络，可以看作是一个具有局部记忆单元和局部反馈连接的递归神经网络。Elman神经网络具有与多层前向网络相似的多层结构，在BP网络基本结构的基础上，在隐含层增加一个承接层，作为一步延时算子，达到记忆的目的。从而使系统具有适应时变特性的能力，增强了网络的全局稳定性。它比前馈型神经网络具有更强的计算能力，还可以用来解决快速寻优问题，属于带反馈的BP网络，有短期记忆功能。

Elman神经网络主要结构为：前馈连接, 包括输入层、隐含层、输出层, 其连接权可以进行学习修正。反馈连接由一组结构单元构成,用来记忆前一时刻的输出值，其连接权值是固定的。在Elman神经网络中, 除了普通的隐含层外，还有一个特别的隐含层，称为关联层 (或联系单元层)。该层从隐含层接收反馈信号，每一个隐含层节点都有一个与之对应的关联层节点连接。关联层的作用是通过联接记忆将上一个时刻的隐含层状态连同当前时刻的网络输入一起作为隐含层的输入，相当于状态反馈。隐含层的传递函数为某种非线性函数，一般为 Sigmoid函数, 输出层为线性函数，关联层也为线性函数。

2.3 基于Elman神经网络的控制系统实例

图 4 个体控制器的架构，一个由10个输入神经元（I1 到 I10）、10个隐藏神经元（H1到 H10）、10个承接神经元（C1到C10）和3个输出神经元（O1到O3）组成的递归神经网络。每一层都与下一层完全连接

该个体控制器由改进的 Elman 人工神经网络实现，具有10个输入神经元、10个隐含神经元和3个输出神经元。输出控制两个电机转动角度以及个体发出的通信信号。隐含层获得来自10神经元承接层记忆的反馈，其中包含前一时间步的隐藏层值。 输入神经元对应6个方向信号传感器、3个角度目标传感器和1个固定偏置输入。神经网络中的所有节点都采用 0 到 1 之间的浮点输入值。所有输出值也都是 0 到 1 之间的浮点值，然后将电机输出转换为- 到 之间的角度。每个内部神经元的激活状态根据 sigmoid 函数进行更新，神经网络中每个连接的权重直接存储在一个数组中。

该模型的主要性能瓶颈是计算一个个体从所有其他个体感知到的聚合信号。直接实现的复杂度是O(n2)，并且在数千个个体的规模下已经变得令人望而却步。然而，这项任务类似于计算物理学中的经典 N 体问题，即预测一组天体（表示为粒子）在引力作用下的个体运动的问题。这个问题有一个高效的近似解法，称为 Barnes–Hut 算法。关键的解法是用来自位于粒子团质心，且具有相同聚合质量的一个粒子的力来近似来自远距粒子团的引力。这种聚合是指用来自集群的信号作为单个向量近似计算，不应与群体的集群行为相混淆。

这个实例的信号传播方法主要基于 Barnes-Hut 算法，但考虑了个体信号感知模型的细节。 每个粒子（在实例中是个体）不是被重力拉动，而是由每个传感器以定向方式独立地感知来自其他个体的聚合信号。因此，这些信号不能通过对相应的向量求和来简单地聚合。例如，如果个体接收到分别来自左侧和右侧的两个相同强度的信号，则它们不应该像万有引力那样相互抵消。相反，在这种情况下它们将分别由左传感器和右传感器独立感知。

基于以上实例，我们可以设计出用于控制纳米机器人个体的 Elman 神经网络，使得个体可以对传感器感知到的信息或接收到的命令做出反应，并具有一定学习能力。

3 总结

本文设计的集群动态协调运动控制系统是一种分布式的控制系统，它不需要操作者对每个纳米机器人个体发出独立的命令，来控制整个集群的运动。相反，我们给予所有个体基本的调控、移动权限，使得集群在未受命令的情况下，在空间中始终维持相对稳定状态（协调运动）。上文介绍的Vicsek模型和Kuramoto模型、Elman神经网络即为实现集群稳态功能的基础。控制集群运动的方法为：向某些个体发送命令控制其移动，从而打破整个集群的稳态；在集群恢复稳态的过程中，个体必将普遍做出位置调整，使集群在空间中移动，达到控制集群运动的目的。若要实现此系统全部功能，可以基于基础协调运动功能进行多次实验并收集数据，使用元学习机器学习方法推演出集群控制模型，以将集群运动命令转换为个体移动命令，达到控制集群运动目的。

此集群动态协调运动控制系统相对于传统方式，简化了控制流程，降低了控制系统的算力要求，从而提高了纳米机器人集群运动效率，且在鲁棒性、容错率方面具有优势。

引用

[1] CHANDRA R, 2015. Competition and Collaboration in Cooperative Coevolution of Elman Recurrent Neural Networks for Time-Series Prediction[J/OL]. IEEE Transactions on Neural Networks and Learning Systems, 26(12): 3123–3136. http://dx.doi.org/10.1109/tnnls.2015.2404823. DOI:10.1109/tnnls.2015.2404823.

[2] DROZD A, WITKOWSKI O, MATSUOKA S, et al., 2016. Critical Mass in the Emergence of Collective Intelligence: A Parallelized Simulation of Swarms in Noisy Environments[J/OL]. Artificial Life and Robotics, 21(3): 317–323. http://dx.doi.org/10.1007/s10015-016-0303-8. DOI:10.1007/s10015-016-0303-8.

[3]MARUYAMA N, SAITO D, HASHIMOTO Y, et al., 2019. Dynamic Organization of Flocking Behaviors in a Large-Scale Boids Model[J/OL]. Journal of Computational Social Science, 2(1): 77–84. http://dx.doi.org/10.1007/s42001-019-00037-9. DOI:10.1007/s42001-019-00037-9.

[4] ZHEN L, GANG Q, GANG G, et al., 2014. A GPU-Based Simulation Kernel within Heterogeneous Collaborative Computation on Large-Scale Artificial Society[J/OL]. International Journal of Modeling and Optimization, 4(3): 205–210. http://dx.doi.org/10.7763/ijmo.2014.v4.374. DOI:10.7763/ijmo.2014.v4.374.

[5] VICSEK T, CZIRÓK A, BEN-JACOB E, et al., 1995. Novel Type of Phase Transition in a System of Self-Driven Particles[J/OL]. Physical Review Letters, 75(6): 1226–1229. http://dx.doi.org/10.1103/physrevlett.75.1226. DOI:10.1103/physrevlett.75.1226.

[6] Anonymous, 1975. International Symposium on Mathematical Problems in Theoretical Physics[J/OL]. Lecture Notes in Physics. http://dx.doi.org/10.1007/bfb0013294. DOI:10.1007/bfb0013294.

[7] NAST C, @wired, 2013. How the Science of Swarms Can Help Us Fight Cancer and Predict the Future[EB/OL](2013–03–19). https://www.wired.com/2013/03/powers-of-swarms/.

[8] Anonymous, [no date]. Vicsek Model - Wikipedia[EB/OL]([no date]). https://en.wikipedia.org/wiki/Vicsek_model.

[9] Anonymous, 2019. Kuramoto Model - Wikipedia[EB/OL](2019–09–24). https://en.m.wikipedia.org/wiki/Kuramoto_model.