用于长距离智能体交互的行为球谐函数

# 用于长距离智能体交互的行为球谐函数 ## 1. 引言 基于智能体的模拟（ABS）涵盖广泛领域。许多现有的ABS框架为不同智能体领域的常见问题提供通用解决方案，但大多数具有挑战性的问题仍需特定领域的解决方案。例如，智能体之间的长距离交互在许多实际场景中是必需的，但通常采用特定上下文的解决方案。 在人群模拟中，人群被建模为一组智能体，每个智能体试图到达目标位置，同时避免与其他智能体和环境中的静态障碍物发生碰撞。在大型人群中，考虑所有智能体对之间的交互成本很高，通常只考虑指定半径内的相邻智能体，这限制了前瞻性行为的可能性。更复杂的避碰方法使用两种算法：一种用于局部碰撞，另一种用于全局长距离碰撞。基于连续体的避碰方法提供了一个有趣的解决方案，但它们假设同一单元格网格中的智能体方向性是均匀的，否则会丢失重要的方向信息。因此，类似的解决方案在不同领域之间不可移植，它们仅适用于丢失方向信息没有后果或至少可以粗略近似的上下文。 为了解决这些问题，我们引入了行为球谐函数（BSH），这是一种新颖的行为模型，它以紧凑的数学公式编码通常在智能体行为中表达的方向信息。为此，我们使用球谐函数（SH），通过投影步骤将多个智能体的方向投影到一组小的系数上。SH函数具有有用的属性，并且可以轻松组合（例如相乘）。一旦新的智能体需要计算其依赖方向的行为，BSH可以轻松地从先前投影的智能体中重建方向信息。 主要贡献包括： - 一种基于球谐函数的新颖行为模型（BSH），它紧凑地编码多个智能体的方向信息。 - BSH用于支持长距离交互的应用。 - 一个GPU/OpenCL实现，利用了BSH的自然并行性和紧凑表示，并在NVIDIA GPU上通过多个交互式智能体模拟进行了测试。 ## 2. 背景 基于智能体的模拟和建模的研究人员和从业者长期以来一直在研究针对广泛架构的并行实现，包括多核、GPU和分布式内存架构。 多个ABS系统研究了避碰算法，其中每个智能体的运动通常由一些高级公式和局部交互规则（例如避碰）控制。ClearPath提出了一种局部避碰算法，将无碰撞导航的条件表述为二次优化问题。PLEdestrians为多智能体模拟中的每个个体引入了一种生物力学上节能的轨迹。人群模拟中的局部避碰算法通常忽略一定大小邻域之外的智能体，但这种截断可能导致当大群智能体进入或离开这些邻域时轨迹发生急剧变化。这种长距离交互比局部避碰需要更多的计算，即使对于分布式和并行模拟也是如此。HybridCrowd通过两种方法执行近似的长距离避碰：低密度人群使用离散方法建模，而高密度人群利用连续体方法。 球谐函数（SH）是一种用于表示定义在球面上的函数的频率空间基。SH已用于各种问题，如热方程、电场、引力场以及模拟电子的量子角动量。在计算机图形应用中，Cabral等人首先使用SH通过在SH中展开双向反射系数来估计BRDF的积分。最近，Kaplanyan和Dachsbacher使用一组谐波函数实时传播间接照明。 我们的方法类似于一种连续体方法，其中智能体的位置和速度在背景网格中累积。然而，在我们的情况下，速度被编码为SH，以消除诸如对智能体目标数量的敏感性或高密度人群中的过度拥挤等困难。 ## 3. 行为球谐函数 ### 3.1 球谐函数 球谐函数（SH）是一种类似于傅里叶变换的数学系统，但定义在球面表面。SH是球坐标中拉普拉斯方程解的角部分，并在球面上定义了一个正交基。一般来说，SH函数基于虚数，但我们只对近似球面上的实函数（即智能体方向）感兴趣。对SH函数的引用等同于对实球谐函数的引用。 给定单位球面上点的标准球坐标参数化，点$(x, y, z)$的笛卡尔坐标可以使用变量$\theta$和$\phi$表示为球坐标： $(x, y, z) \to (\sin\theta\cos\phi, \sin\theta\sin\phi, \cos\theta)$ SH函数传统上用符号$y$表示： \[ y_{l}^{m}(\theta, \phi) = \begin{cases} \sqrt{2}K_{l}^{m}\cos(m\phi)P_{l}^{m}(\cos\theta), & m > 0 \\ \sqrt{2}K_{l}^{m}\sin(-m\phi)P_{l}^{-m}(\cos\theta), & m < 0 \\ K_{l}^{0}P_{l}^{0}\cos(\theta), & m = 0 \end{cases} \] 其中$P$是关联勒让德多项式，$K_{l}^{m}$是缩放归一化常数，定义为： \[ K_{l}^{m} = \sqrt{\frac{(2l + 1)(l - |m|)!}{4\pi(l + |m|)!}} \] $l$和$m$是整数常数索引，分别称为阶或带（$l$）和度（$m$）。为了生成所有的SH正交基函数，参数$l$和$m$的定义与勒让德多项式略有不同：$l$仍然是从0开始的正整数，但$m$取从$-l$到$l$的有符号整数值。可以认为SH函数以特定顺序出现，因此我们可以使用更简单的一维向量： $y_{l}^{m}(\theta, \phi) = y_{i}(\theta, \phi)$，其中$i = l(l + 1) + m$ 在本文中，我们使用3阶SH表示，因此只使用9个基函数，如下表所示： | 阶（$l$） | 度（$m$） | 基函数 | | --- | --- | --- | | 0 | 0 | $y_{0}^{0}(\theta, \phi) = \frac{1}{2}\sqrt{\frac{1}{\pi}}$ | | 1 | -1 | $y_{1}^{-1}(\theta, \phi) = \frac{1}{2}\sqrt{\frac{3}{\pi}}\sin\theta\sin\phi$ | | 1 | 0 | $y_{1}^{0}(\theta, \phi) = \frac{1}{2}\sqrt{\frac{3}{\pi}}\cos\theta$ | | 1 | 1 | $y_{1}^{1}(\theta, \phi) = -\frac{1}{2}\sqrt{\frac{3}{\pi}}\sin\theta\cos\phi$ | | 2 | -2 | $y_{2}^{-2}(\