Lu, Cong, Raluca Georgescu和Johan Verwey. 《Go-Explore Complex 3D Game Environments for Automated Reachability Testing》. arXiv, 2022年9月1日. http://arxiv.org/abs/2209.00570.
Absract
现代AAA级视频游戏拥有庞大的游戏关卡和地图，对于关卡测试人员来说，这些地图日益难以进行彻底的覆盖。因此，游戏通常会出现严重的错误，比如玩家会从地板上掉下去，或者被卡在墙壁里。我们提出了一种针对模拟3D环境中可达性错误的方法，该方法基于强大的探索算法Go-Explore，该算法保存地图上的唯一检查点，然后从中选择有潜力的检查点进行探索。我们证明，当结合游戏导航网格的简单启发式方法时，Go-Explore能够发现复杂环境中具有挑战性的错误，并且无需人工示范或对游戏动态的了解。在覆盖导航网格和发现地图上的唯一位置方面，Go-Explore明显优于更复杂的基准算法，包括基于内在好奇心的强化学习。最后，由于我们使用了并行代理，我们的算法可以在单台计算机上在10小时内完全覆盖一个广阔的1.5km x 1.5km游戏世界，因此非常适用于持续测试套件。
核心贡献
- 应用了一种简单高效的算法，Go-Explore，用于在具有挑战性的探索地图中发现可达位置，而无需人工示范或对游戏动态的了解。
- 提出了一种将发现的位置与游戏NavMesh进行比较，从而将其分类为预期和意外的标准。未探索的导航网格区域也可能被标记出来。
- 展示了通过在单个游戏实例中并行化代理，能够在单台计算机上在10小时内彻底覆盖广阔的1.5km x 1.5km游戏地图，使得我们的算法非常适用于持续测试套件。
强化学习中的探索
基于奖励函数
对于每一个空间状态赋予s，赋予值n(s)，在探索时每次到达此状态给予奖励r
$$
r_t = \frac{1}{n(s)}
$$
但此方法难以处理状态空间较大的情况，并且利于并行计算加快训练速度。
Random Network Distillation
一种用于高维状态空间的探索奖励计算的灵活方法，通过估计一个固定随机初始化神经网络给出的游戏观察特征的预测误差来计算探索奖励。RND算法的基本思想是，使用一个随机初始化的神经网络来预测游戏观察的特征，然后使用另一个神经网络来预测这些特征的误差。探索奖励是由这个误差的大小来计算的。这种方法的优点是可以适用于高维状态空间，而且不需要对环境进行任何先验知识的假设。RND算法的一个缺点是需要训练两个神经网络，这可能会增加算法的计算成本。
GoExplore算法
Go-Explore是解决难以探索问题的另一种方法，它维护先前探索过的状态的缓存，然后使用启发式方法周期性地选择有潜力的状态，并从这些状态进行探索。一旦找到了具有足够高回报的轨迹，就会使用模仿学习来使发现的行为更加稳健。该算法旨在避免“偏离轨道”的现象，在没有显式记忆的算法中，如RND，预测器网络可能会因为灾难性遗忘而丢失关于先前达到的状态的信息。在大型地图中，这种现象可能更容易发生。
- 初始化：算法开始时，初始化一个已访问状态的地图和一个未探索状态的优先队列。优先队列按照每个状态被访问的次数排序，访问次数最少的状态具有最高的优先级。
- 探索：算法进入一个循环，重复选择优先级最高的未探索状态，并对其进行探索。为了探索一个状态，算法从该状态开始进行随机游走，直到到达一个之前未访问过的新状态。然后，算法将新状态添加到已访问地图和优先队列中。
- 缓存：为了避免重新访问已经探索过的状态，算法维护了一个已发现位置的缓存。如果算法遇到一个已经在缓存中的状态，它会跳过该状态的探索，并在当前状态和缓存状态之间添加一个链接。
- 回溯：如果算法到达了一个死路或已经探索过的状态，它会回溯到优先队列中最后一个未探索的状态，并从那里继续探索。
- 可达性测试：当算法探索游戏环境时，它会标记远离导航网格的已发现点。这有助于识别可达性问题并在地图上突出显示有问题的点。
- 连续测试：Go-Explore可以集成到连续测试框架中，以在每个级别更新时发现错误，并在质量保证方面节省大量资源。
实验方法
使用Unreal Engine 5设计的专有测试游戏关卡上评估了方法。考虑了三个难度逐渐增加的地图：
- 小地图：一个小的测试区域，包含障碍物和两个有意放置的错误（约100米 x 100米）。
- 大地图：一个广阔的城市景观，用于测试每种算法的可扩展性（约1.5公里 x 1.5公里）。这个地图是现代自动化方法所考虑的最大地图之一。
- 遍历地图：一个具有挑战性几何结构的大型多层地图，用作难度较高的探索挑战。
游戏使用丰富的3D观测数据，包括可选的射线投射、位置和旋转特征。代理使用与标准游戏手柄相匹配的多离散动作空间进行移动。这些地图在图2中有所说明。
对于Go-Explore，我们评估了前一节中描述的所有重置启发式方法——基于访问的、基于目标的和混合的。我们使用默认的距离阈值K = 1来添加新的点，并且在评估代理在训练过程中访问了多少个唯一位置时使用相同的阈值。代理每隔t_reset = 128步重置一次。首先，我们在三个测试地图上评估了Go-Explore与基准算法RND（使用Proximal Policy Optimization进行优化，Schulman等人，2017年）和随机探索的性能。接下来，我们消融了各种组件，首先表明Go-Explore对超参数选择稳定，其次，随机探索对大规模地图的强大性能至关重要。
对于每个实验，通过在每个地图内运行16个独立代理来加速训练，这些代理不能相互交互或看到对方。每个代理与中央的发现位置缓存进行同步。我们在小地图上进行了200,000个时间步的训练，在两个大地图上进行了10,000,000个时间步的训练，并使用4个随机种子重复每个实验。由于我们使用了并行化，小地图的墙钟时间约为30分钟，而大地图只需要在一台F8 Azure虚拟机上进行10小时的训练即可完成。对于RND基准算法，我们仅使用了GeForce RTX 2080 GPU。
总结
采用了一种不使用神经网络的方式解决地图遍历的问题，思路和深搜差不多，在地图上按一定间隔生成坐标点，探索到一个点就把附近一定距离内的点删了，再将仍然存在的点加入队列中。在本论文中，我们展示了Go-Explore算法能够在现代AAA级视频游戏中可扩展、高效且无需学习的情况下进行广阔的3D游戏地图可达性测试，而无需任何人工示范或对游戏动态的了解。与之前基于好奇心的强化学习方法相比，Go-Explore通过维护一个发现位置的缓存来避免灾难性遗忘的问题。Ecoffet等人（2019年）提倡的随机探索方法在实现上明显更简单，而且避免了使用神经网络。通过标记远离导航网格的发现位置，我们能够廉价地识别可达性问题，并突显地图上的问题点。由于算法运行快速且易于实现，我们预期Go-Explore可以轻松地整合到连续测试框架中。通过这样做，每个关卡在更新时都可能发现错误，并且在质量保证方面可能节省大量资源。
Sestini, Alessandro, Linus Gisslén, Joakim Bergdahl, Konrad Tollmar和Andrew D. Bagdanov. 《CCPT: Automatic Gameplay Testing and Validation with Curiosity-Conditioned Proximal Trajectories》. arXiv, 2022年2月21日. http://arxiv.org/abs/2202.10057.
摘要
该论文提出了一种新颖的深度强化学习算法，用于在复杂的3D导航环境中进行自动分析和检测游戏问题。该算法名为Curiosity-Conditioned Proximal Trajectories（CCPT），它结合了好奇心学习和模仿学习，训练代理在从专家示范中得到的已知轨迹附近进行系统性探索。我们展示了CCPT如何在复杂环境中进行探索，发现游戏问题和设计缺陷，并直接向游戏设计师识别和强调这些问题。我们进一步在一个反映现代AAA级视频游戏复杂性的新颖3D导航环境中展示了该算法的有效性。我们的结果显示，CCPT相比基准方法具有更高的覆盖率和更多的错误发现，因此可以为游戏设计师提供一个有价值的自动识别游戏设计问题的工具。
导航模型
agent观察到的状态由以下内容组成：以3D语义占用地图的形式的局部感知(conv3d)，以及agent物理属性的标量信息（全局位置，是否在地面上，是否附着在可攀爬表面上，是否可以执行二段跳，速度和方向）。
全局位置使用positional embeddings编码生成:
$$
PE_{(pos, 2i)} = \sin\left(\frac{pos}{10000^{(2i/d)}}\right)
$$
$$
PE_{(pos, 2i+1)} = \cos\left(\frac{pos}{10000^{(2i/d)}}\right)
$$
文章认为在3D场景中仅仅使用归一化的坐标或learned embeddings时网络不足以理解不同状态之间的区别
最后将这些信息concatenanted送入网络
在图中，展示了作为网络输入的示例3D语义地图。这些地图是对空间和代理周围元素的分类离散化表示，每个体素由该位置上对象的语义整数值来定义。给予的唯一外部奖励是当代理到达一个活动目标时，每个step都会获得+10的奖励。由于在如此庞大的环境中奖励非常稀疏，代理很难获得一个非零的奖励，因此训练非常困难。此外，仅有外部奖励的话，即使代理学会到达目标位置，它们也会始终遵循相同的轨迹而不去探索新路径。相反，我们需要代理能够在继续寻找未探索路径的同时，高效地到达目标区域，因此将探索和模仿的奖励结合起来。
模仿学习模型
使用基于GAIL算法基础上构建的AMP算法，给定一组专家演示M，目标是学习衡量策略与演示之间的相似性，然后通过前向强化学习更新策略。目标被建模为一个判别器D(s, a)，用于预测一个给定的状态-动作对(s, a)是否来自演示集或者是由运行策略生成的。AMP采用了最小二乘GAN [Mao等人，2017]提出的损失函数
$$
L_{\text{AMP}} = \arg \min_D \mathbb{E}{d_M(s,a) } \left[ (D(s, a) - 1)^2 \right] + \mathbb{E}{d_{\pi}(s,a)} \left[ (D(s, a) + 1)^2 \right]
$$
好奇心模型
前置：RND网络
RND这类文章是基于强化学习在解决Atari游戏中蒙德祖玛的复仇的困境提出的。由于在这类游戏中存在非常稀疏的奖励，Agent在探索利用上存在很大的问题。RND提出了一种只需要做前向传播就能很好计算得到的探索奖励，使用agent过去的经验的预测误差来估计新经验探索性的启发，RND使用了一个确定的随机初始化的神经网络，来预测当前状态的输出，进而确定这个探索奖励。
总奖励值为：extrinsic reward + intrinsic reward，其中extrinsic reward是由环境给与的，反应设计者的意图，原始奖励，intrinsic reward是算法为了达到最终目标而学习到的有益行为。从设计方面来看，intrinsic reward function是一个带参数的需要在训练过程中优化的目标函数，而非人为设计的某一种计算方式；
从目的方面来看，intrinsic reward function是想让智能体自己学到应当是要做一件什么事情（what to do)，而不是通过辅助式的设计告诉它如何做（how to do）
RND使用随机网络和预测网络的误差值来计算intrinsic reward，鼓励agent更多在环境中进行探索。
这里基于RND网络的基础上将奖励函数设置为：
$$
R(s_t, a_t) = \alpha \cdot r_c(s_{t+1}) + (1 - \alpha) \cdot r_i(s_t, a_t) + r_e(s_t, a_t)
$$
将好奇心奖励和模仿学习奖励按比例加起来作为intrinsic reward，再加上环境的extrinsic reward。
α ∈ [0, 1] i在每一轮训练开始时随机初始化一个值，使得算法随机在模仿学习和探索中采样。
好奇心驱动探索
好奇心驱动探索的流程如下：
- 首先，CCPT使用专家演示来指导智能体的探索，以便智能体能够更快地学习到期望的行为。
- 然后，有意识地探索期望轨迹的附近。CCPT使用一个称为“探索条件内在奖励函数”的函数来驱动探索。这个函数会根据智能体的行为和环境的状态来计算一个奖励值，以鼓励智能体探索未知的区域。
- 接下来，CCPT使用深度强化学习来训练智能体，以便智能体能够自主地探索和学习。在训练过程中，智能体会不断地尝试新的行为，并根据探索条件内在奖励函数的奖励值来调整自己的行为。
- 最后，CCPT使用并行训练来提高训练效率，以便智能体能够更快地学习到期望的行为。在并行训练中，多个智能体会同时进行训练，以便更快地收敛到最优解。
通过这个流程，CCPT能够有意识地探索期望轨迹的附近，并帮助游戏设计师自动检测复杂3D游戏场景中的错误和问题。
测试问题路径
首先将α >0.5的路径筛选出来，即依据好奇心算法探索的路径，再将其中平均奖励大于指定阈值的路径显示在地图上，这些一般都是测试过程中发现的问题路径。
总结
在本文中，我们介绍了一种新颖的强化学习方法，用于自动化测试复杂的3D场景。”Curiosity-Conditioned Proximal Trajectories”（CCPT）允许开发人员和设计师通过专家演示来指定测试区域。CCPT使用模仿学习和好奇心的组合，由我们称之为”exploration-conditioned intrinsic reward function”驱动，在展示轨迹的附近进行探索。我们的方法不仅能够发现故障和疏漏，还能够自动识别和突出显示包含潜在问题的轨迹。我们的结果在提出的导航环境中显示出高水平的覆盖率和错误发现，证明好奇心和模仿的特定组合对此目的非常有效。我们相信，这个算法将成为AAA游戏设计师的有用工具，可以自动识别问题或潜在的漏洞，减少对人工测试人员的依赖。
CCPT应用于自动化游戏玩法分析的一个限制是我们必须为每个要测试的区域执行一个实验。一种可能的解决方案是提供大量的演示，并同时测试不同的区域。然而，众所周知，基于GAN的方法在拟合大数据集时容易出现模式崩溃（mode collapse）。在这种情况下，策略可能只模仿一小部分示例行为，从而仅专注于一个区域。另一个缺点是CCPT不能保证在环境中找到所有的错误和问题。特别是，那些与专家演示相距较远的问题可能被我们的代理程序错过。我们正在尝试的一个可能的解决方案是在第一次迭代中使用发现的问题轨迹作为专家演示执行另一次CCPT迭代：由于它们涉及相同的区域，策略将不会受到模式崩溃的影响，同时增加探索性。