群体运动仿真控制技术是目前计算机图形学和虚拟现实领域的研究热点，其主要研究内容是在计算机虚拟环境下对现实生活中的各类群体进行仿真和控制以增强虚拟场景的真实性和沉浸感。群体运动仿真控制的相关研究成果可以应用于传统的计算机游戏、影视特效制作以及新型虚拟现实交互仿真系统等计算机应用。

目前大多数群体仿真技术致力于模拟由大量自由移动个体组成的群体行为，如鸟群、人群和蚁群等。然而，现实生活中还存在着许多规则化的群体，此类群体的形状和运动受到一定规则的限制，如军队行进、车流运动和团体表演等。此外，这类群体在遇到障碍物时应当能够保持队形稳定，如高速路上发生事故导致道路阻塞，其他车辆应当在通过阻塞区域后恢复原来秩序继续运行。

本文提出了一种基于可变形引导网格的群体编队控制算法。该算法为群体建立刚性可变形网格控制群体队形，并通过改进的网格引导方法控制智能体运动，以此实现对规则化群体的运动仿真。过去基于网格的群体编队控制算法往往直接使用队形网格顶点来描述智能体位置^[1]以维持群体队形的稳定，但这种方法缺少灵活性，群体在队形发生变化时容易出现阻塞现象。Henry等人^[2]提出使用质量运输规划(MTS)的方法驱使智能体向队形网格顶点运动，该方法有效减少了阻塞现象并提高了智能体的全局移动效率，但同时也增加了算法的计算代价。通过本文提出的基于吸引点的网格引导方法可以使群体在队形发生变化时避免发生阻塞现象，同时，群体在绕过障碍物后能尽快恢复原来队形。该方法无需在每个仿真步中都为所有智能体规划全局最优的目标点，因此减少了系统内存占用，提高了算法效率。

群体运动仿真算法根据建模方式的不同可以大体分为以下3类：基于智能体的方法、基于流的方法和基于数据驱动的方法。其中基于智能体的方法将每个个体都视为具有独立判断能力的个体，从微观的角度进行群体控制，能较好地模拟小规模群体运动，因此本文采用智能体建模。在给定了智能体的起始点与目标点后，如何为智能体规划一条最佳路径也是群体仿真的关键问题之一。常见的路径规划算法有著名的A^*算法^[3]、Dijkstra算法^[4]和走廊图(CMM)算法^[5]等。此外，研究人员还提出了基于人工势场的方法^[6]、基于相对速度障碍(RVO)的方法^[7]以及基于碰撞包围盒的方法^[8]等来避免智能体在移动过程中与障碍物或其他智能体发生碰撞。

本文主要研究群体运动的编队控制，即控制群体按照给定队形进行移动和碰撞避免。在群体的移动过程中，智能体之间有保持相对位置不变的倾向，并且智能体在进行碰撞避免时应当尽可能使整体队形的变化最小。Kwon等人^[1]利用拉普拉斯网格变形方法对既有群体的队形进行变换和连接，从而形成大规模群体动画。Zhou等人^[9]针对无人机的编队运动问题提出了基于层次分解策略的编队避障方法。Dai等人^[10]采用改进的人工势场法对避障算法进行优化，加入“回环力”使群体在通过障碍物区域后能够恢复编队继续运行。Igarashi等人^[11]提出了基于刚性网格的实时交互系统，用户可以通过该系统对2维图像进行变形操作。在此基础上，Henry等人^[2]结合MTS方法通过多点触控设备对群体运动进行控制，实现了群体编队移动的实时交互仿真。Takahashi等人^[12]利用基于光谱分析的插值方法实现了规则化群体在多种不同队形之间的自然切换。现有的基于网格的群体控制算法常用Delaunay三角网格描述群体队形并使用网格顶点表示队形中的智能体。常用的Delaunay三角剖分算法有Bowyer-Watson算法^[13-14]和Lawson算法^[15]等。

为了保证群体队形的规则性与稳定性，使用Delaunay三角网格来描述群体队形。同时，为了使队形网格在避障过程中产生的形变尽可能小，对队形网格作了刚性变形处理。

Delaunay三角网格具有最规则性：该三角网格相较于其他剖分方式所得网格更接近正三角形，即更稳定，因此适用于本文的队形网格划分。同时，Delaunay三角网格还具有空圆性：在Delaunay三角网中任一三角形的外接圆不包含除该三角形顶点外的其他顶点。根据这一特性，可以对空间中的点进行Delaunay三角剖分。本文将所有个体的初始位置作为参考顶点，采用Bowyer-Watson方法^[13-14]对群体进行三角剖分以得出群体的初始队形网格。算法流程如图 1所示。

图 1 队形网格划分流程

Fig. 1 Formation mesh generation

图 2为图 1虚线部分的执行过程。图 2中圆点表示个体，三角形$\left\{ {X, Y, Z} \right\} $表示构造的包含所有个体的最大三角形，点$i $为本轮循环中新插入的个体位置。在每轮循环结束前，还需要对新生成的三角形进行局部最优化处理^[15]使其满足空圆性。循环上述过程直到所有个体位置都已插入完毕，则三角形链表中的三角形($\left\{ {X, Y, Z} \right\} $除外)所组成的三角网格即为初始队形网格。

图 2 队形网格划分关键步骤

Fig. 2 Key steps of formation mesh generation((a) insert a new node $i $; (b) circumcircle detection; (c) delete the common side; (d) form and save new triangles)

队形网格在群体移动的过程中应当维持自身形状稳定，并且在发生形变后有恢复原来形状的趋势，即具有一定的刚体性质。使用与文献[11]类似的最小化误差测度的方法定义刚性网格的变形规则。该方法主要分为两个阶段：无标度变换阶段和缩放调整阶段。其中，无标度变换阶段的主要目标是在部分队形网格顶点发生相对位置变化时，根据最小化误差测度的原则调整其余顶点位置以获得使整体队形变化最小的中间网格。在缩放调整阶段，对该中间网格进行比例缩放以得到最终的结果网格。缩放调整的简要过程如下：首先，为中间网格中的三角形$ \left\{ {{v_1}, {v_2}, {v_3}} \right\}$构造一个匹三角形$\left\{ {{{v'}_1}, {{v'}_2}, {{v'}_3}} \right\} $。该匹配三角形与对应初始队形网格中的三角形全等且与$\left\{ {{v_1}, {v_2}, {v_3}} \right\} $尽可能接近。然后，通过最小化结果三角形与匹配三角形之间的误差测度$E $来确定最终的结果网格，$E $的定义为

式中，$\left( {i, j} \right) \in \left\{ {\left( {0, 1} \right), \left( {1, 2} \right), \left( {2, 0} \right)} \right\} $，${v''_i} $与${v'_i} $分别表示结果三角形的顶点与对应匹配三角形的顶点。由式(1) 可知，该误差测度仅与结果三角形的边有关，而与顶点位置无关。显然的，当结果三角形全等于匹配三角形时$E $取得最小值(为零)，但由于队形网格中的顶点可能同时属于多个三角形，因此其最终位置应由多个匹配三角形产生的期望位置均值决定。

通过上述最小化初始网格与变形网格间误差测度的方法，在队形网格中的某些顶点发生相对位置变化时，其余顶点能够实时地调整自身位置以维持整体队形稳定。如图 3所示，当障碍物较大时，群体以扭曲队形的方式避开障碍物，如图 3(b)。当可通行区域较窄时，群体队形将被压缩，如图 3(c)。当障碍物较小且分布较为分散时，群体以扩张队形的方式穿过障碍区域，如图 3(d)。

图 3 队形网格变形

Fig. 3 Formation mesh deformation ((a) initial formation; (b) twisted deformation; (c) compressive deformation; (d) expanded deformation)

本节介绍了如何利用障碍势场法实现群体避障，并改进了网格顶点对智能体的引导方式，提出了基于吸引点的网格引导方法。

队形网格的变形是由虚拟环境中的障碍物造成的，每个障碍物都会以自身为中心形成一个势场并影响队形网格顶点的运动方向，如图 4所示。

图 4 障碍势场

Fig. 4 Obstacle potential field

图 4中，$r $表示用户预定义的障碍势场范围，点$ x$的势场大小由该点与障碍物表面的距离$d $计算，即

为了提高算法运行的实时效率，事先将环境划分为一系列均匀网格，并分别为每个环境网格计算其势场大小。同时，为了避免队形网格顶点在绕过较宽的障碍物(如墙壁、河流)时运动速度过慢，将环境网格中的势场方向定义为$\frac{{x-c}}{{\left\| {x-c} \right\|}} $，$x $表示环境网格的中心位置，$ c$表示障碍物的中心位置。这种由障碍物中心向外发散的势场一定程度上增强了使队形网格顶点绕过障碍物的切向力。该切向力使得群体在通过较宽的障碍物时能够加速转向，避免发生阻塞。然而，在障碍物长度远大于整体队形长度且最大宽度大于队形网格形变范围时(如狭长的锥形障碍物)，队形网格可能会发生“割裂”，即部分网格由于障碍物的排斥作用，难以恢复到初始状态。此时，将发生“割裂”的网格从当前队形网格中移除，在变形阶段不再对其进行计算。直到个体间的距离恢复至形变范围内时，才重新对“割裂”的网格进行链接。由于事先已经对群体进行了队形网格划分，因此在链接被割裂的网格时无需再次进行三角剖分，只需根据初始队形网格链表中存储的数据将移除的网格重新添加到当前队形网格链表中。

当队形网格顶点进入障碍势场范围时，根据所在环境网格的势场大小及方向更新这些顶点的位置，避免与障碍物发生碰撞。队形网格中的其余顶点根据2.2节提出的变形规则计算，使整体队形保持稳定，实现了特定队形的群体避障。

传统的基于网格的群体编队控制算法常将智能体与队形网格顶点绑定，即智能体在运动过程中的编队顺序始终保持一致。在队形发生变化时，智能体总是跟随某一确定的网格顶点移动。然而，现实生活中的群体为了避免发生阻塞现象并在绕过障碍物后尽快恢复队形，其智能体的编队顺序往往会发生改变，即“错位现象”，如图 5所示。

图 5 错位现象

Fig. 5 Dislocation phenomenon

针对上述现象，对传统的网格引导方式进行改进，结合CMM算法^[5]中的吸引点驱动提出了基于吸引点的网格引导方法。该方法驱使智能体向距自身最近且未被其他个体占用的网格顶点移动，以此实现高效的队形恢复。

在队形变化的初始阶段，仍采用传统的网格引导方式。令$o $表示队形中的智能体，$v\left( o \right) $表示对应的队形网格顶点，当$o $与$ v\left( o \right)$间的距离小于$L $时，称$v\left( o \right) $被$o $占用，否则称$o $发生了“错位”，$L $表示用户预定义的误差阈值。一旦$o $出现“错位”现象，则取消$v\left( o \right) $对$o $的吸引并在所有未被占用的队形网格顶点中找出距$o $最近的顶点作为$o $的新吸引点$a\left( o \right) $。$a\left( o \right) $对$o $的吸引力${F_o} $为

式中，$f $表示吸引力大小，其取值由$a\left( o \right) $与$o $间的距离$l $决定，即

${R\left( a \right)} $与${r\left( o \right)} $分别表示吸引点的吸引半径和智能体的碰撞半径，且${R\left( a \right)} $应远大于${r\left( o \right)} $以保证${F_o} $不会趋于无穷大。通常可取队形网格中相距最远的两个顶点距离作为${R\left( a \right)} $的参考值。

智能体$o $与局部障碍(如其他智能体或小型障碍物)间的碰撞避免可以通过对$o $施加局部排斥力${F_r} $来实现。因此，智能体在吸引点引导的过程中所受合力$F $由${F_o} $与${F_r} $共同决定。若在$o $靠近其吸引点$ a\left( o \right)$的过程中，$ a\left( o \right)$被其他智能体占用，则取消$a\left( o \right) $对$o $的吸引并重新为$o $指定一个未被占用的最近吸引点。重复此过程，直到所有发生“错位”的智能体与其吸引点间的距离都小于误差阈值$L $，此时队形中的所有智能体都跟随对应的队形网格顶点运动，即恢复为传统的网格引导方式。

基于吸引点的网格引导方法驱使智能体向最近的队形网格顶点运动，提高了智能体在队形发生变化时的移动效率，避免了阻塞现象的发生。该方法仅需对发生错位的智能体进行计算，而无需考虑其余大部分正常移动的个体，因此提高了算法的实时计算效率。

通过本文提出的基于可变形网格的群体运动控制算法，采用基于吸引点的网格引导方式，在Unity中对系列群体运动场景进行了仿真。实现过程主要分为3个阶段：初始化阶段、变形阶段和恢复阶段。

1) 首先对场景中的个体进行分组，分别将同一群组内的所有个体位置存入队列。然后根据Delaunay三角剖分算法对该队列中的点进行三角剖分，形成一个三角形链表，即队形网格。

2) 将场景划分为均匀的环境网格，根据场景中障碍物的分布，分别为每个环境网格计算并存储其障碍势场的大小及方向。

3) 为每个群组设置目标区域，目标区域内无障碍物且对群组内的个体具有较强的吸引力。

1) 队形网格顶点受吸引力的作用向前移动。对于进入障碍势场的顶点，其速度的大小及方向由所受吸引力和排斥力的合力决定。

2) 对于未进入障碍势场的队形网格顶点，通过最小化误差测度的网格变形规则计算出其期望位置，并根据期望位置与当前位置的误差大小决定自身速度。

3) 若两个顶点间距离过大，超过了队形网格的形变范围，则判断这两个顶点间的边发生“割裂”。将发生“割裂”的网格从当前队形网格中移除，在步骤2) 中不再对其进行计算。

4) 群组中的智能体跟随距离自身最近且未被其他个体占用的队形网格顶点移动。每当智能体发生“错位”时，则重新选择自身的吸引点。

5) 在障碍物动态移动的环境下，实时更新环境网格中的障碍势场。

1) 当发生“割裂”的网格恢复到形变范围内时，根据初始队形网格链表中的数据将被移除的网格重新添加到当前队形网格链表中。

2) 到达目标区域后的队形网格顶点不再受到吸引力和排斥力的作用，根据网格变形规则恢复为初始队形。

通过上述3个阶段，可以对以下场景进行模拟：

1) 军队行进场景。模拟一组军队方阵在山地和道路中行进。场景中设置岩石、窄门等障碍物。当群体遭遇分布较为分散的小型障碍物时，通过队形散开的方式穿过障碍，如图 6(a) (b)所示。当障碍物较大时，群体通过队形收拢以避开障碍，如图 6(c)所示。在通过障碍区域后，群体恢复初始队形，如图 6(d)所示。

图 6 军队行进场景

Fig. 6 Army marched scene((a) initial formation; (b) formation spread; (c) formation collapse; (d) formation recovery)

2) 动态车流场景。模拟了车流量较大的城市街道场景。在该场景中，一辆正在执行任务的警车从丁字路口一侧汇入干路车流，并且保持高速前进。警车的速度及运动轨迹是预先定义的，车流中的其他车辆将警车视为动态障碍物进行碰撞避免。实验中，每个车辆都被视作两个并行的个体以实现队形网格划分，如图 7(a)所示。且这两个个体间的相对距离保持不变(等于车身宽度)，车辆的转向角等于两个个体间连线的偏转角。当警车靠近干路车流时，由于警车产生的动态障碍势场作用，车辆整体队形发生扭曲，如图 7(b)所示。当警车进入车流内部后，为了给警车让出足够的通行区域，警车周围车辆的间距扩大，产生了扩张变形，如图 7(c)所示。最后，远离警车的车辆重新恢复正常行驶，如图 7(d)所示。

图 7 车流中的动态障碍避免

Fig. 7 Dynamic obstacle avoidence in traffic flow((a) mesh generation; (b) twisted deformation; (c) expanded deformation; (d) formation recovery)

3) 群体表演场景。设置了两组表演者，假设它们在表演过程中需要互换位置，且要求变换过程中尽可能保持队形，但对变换前后任一表演者在队形中的具体位置没有限制。如图 8所示，两组队伍实现了无碰撞的交叉运动，运动过程中整体队形基本保持不变，且在到达目标区域后恢复了原来队形。

图 8 群体表演场景

Fig. 8 Group show scene((a) initial formation; (b) group interaction; (c) formation recovery)

本文所有实验均运行在配置Win10(64位)的PC上(Intel(R) Core(TM) i7-4200H CPU 2.80 GHz 8 GB内存)。为了检测本文算法的计算效率，在群体表演场景中设置了不同规模的群组交换实验进行对比。实验结果表明，本文算法的实时计算代价主要花费在网格变形阶段(队形网格划分阶段是预先进行的)，如表 1所示。

表 1 算法运行时间抽样
Table 1 Sample of algorithm running time

下载CSV

/ms
个体总数	队形网格 划分阶段	网格变形阶段 (单位仿真步内)
1 000	35	20.15
2 000	78	39.44
3 000	254	94.56

当队形网格的顶点总数小于1 000时，群体运动十分平滑，队形变形的过程中也没有出现卡顿现象。由于基于吸引点的网格引导方式无需在每个仿真步中都为所有智能体实时计算目标顶点位置，而只需考虑少数发生了“错位”的个体，因此在队形中个体数量较多的情况下，本文算法仍能发挥较好的作用。

本文提出了基于可变形网格的群体运动控制算法，并对传统的网格引导方式作了改进。该算法的主要贡献如下：

1) 适用于具有特定队形的多智能体群体仿真，较好地解决了规则化的群体运动过程中的队形保持和碰撞避免问题。

2) 基于吸引点的网格引导方式驱使智能体向队形网格顶点移动，相较于传统的网格引导方式更加灵活，提高了智能体在队形变化过程中的全局移动效率。

Unity中自带的导航网格也能起到类似的群体导航作用，但是其烘焙出的导航网格不均匀，在多个网格的公共顶点处极易出现堵塞现象。且Unity烘焙导航网格的过程较长，在复杂的动态场景中难以实现实时更新。本文将环境划分为一系列均匀网格，在初始化过程中分别为每个环境网格计算障碍势场，并在障碍物运动时进行实时更新。在通过障碍势场进行避障的同时，利用网格变形规则维持队形稳定。最后，采用基于吸引点的网格引导方式引导智能体向队形网格顶点靠近，从而实现具有特定队形的群体仿真。

本文算法仍存在一定局限性，如：当个体模型精度过高时，其渲染效率难以达到实时要求，从而造成仿真结果失真卡顿。在接下来的研究中，考虑使用GPU加速渲染技术以增强仿真的实时性。此外，还考虑在保持算法效率的前提下，将相对速度障碍(RVO)算法^[7]引入本文的网格引导算法中，使智能体更加高效地对局部障碍物进行碰撞避免并进一步提高群体队形仿真的真实性。