Improving Playtesting Coverage via Curiosity Driven Reinforcement Learning Agents
通过好奇驱动的强化学习代理改进游戏测试覆盖率

We evaluate our approach on a relatively large ($500\text{\,}\mathrm{m}$ x $500\text{\,}\mathrm{m}$ x $50\text{\,}\mathrm{m}$) map designed for the purpose of creating an elaborate navigation landscape. We created a scenario with complex navigation mechanics (e.g. jumps, climbable walls and elevators) in a 3D space as shown in Fig. 1. Moreover, and similar to what it is normally seen in modern video games, we have designed the scenario so that complex navigation strategies are required to fully explore the different areas around the map. More details about the environment, navigation mechanics and final results can be found in the accompanying video¹¹1https://www.youtube.com/watch?v=cfm3R94FB_4
我们在一个相对较大的（ $500\text{\,}\mathrm{m}$ x $500\text{\,}\mathrm{m}$ x $50\text{\,}\mathrm{m}$ ）地图上评估我们的方法，该地图旨在创建一个复杂的导航景观。我们创建了一个具有复杂导航机制（例如跳跃、可攀爬的墙壁和电梯）的场景，如图 1 所示。此外，与现代视频游戏中通常看到的情况类似，我们设计了场景，以便需要复杂的导航策略才能完全探索地图周围的不同区域。有关环境、导航机制和最终结果的更多详细信息，请参见附带视频 ¹ 。.

The character in our environment (see Fig. 2) is $1.7\text{\,}\mathrm{m}$ tall and has a total of 3 continuous navigation actions: forward/backward, left/right turn, left/right strafe, plus a discrete action for jumping. The character also has the ability to climb on special surfaces located around the map.
我们环境中的角色（见图 2）身高为 $1.7\text{\,}\mathrm{m}$ ，共有 3 个连续的导航动作：前进/后退，左/右转，左/右平移，以及一个离散的跳跃动作。角色还具有爬上地图周围特殊表面的能力。

Because the purpose of our approach is to test the game and identify any potential issues, we introduced a set of known bugs into the map. These bugs include missing collision boxes, design oversights, places where players may get stuck, etc.
因为我们的方法的目的是测试游戏并识别任何潜在问题，所以我们在地图中引入了一组已知的错误。这些错误包括缺少碰撞箱、设计疏忽、玩家可能被卡住的地方等。

It is important to remark that, contrary to similar approaches like the one presented in [4], we make no use of navigation meshes within our environment. As discussed in [2], navigation meshes are often not designed to resemble the freedom of movement that human players will have. Any agent constrained by these meshes will, most likely, fail at exploring the environment to the same degree a human would, and will therefore miss those bugs frequently found by human players. In the next section we discuss how an RL agent can be used to control navigation and improve exploration.
需要指出的是，与[4]中提出的类似方法不同，我们在环境中没有使用导航网格。正如[2]中讨论的那样，导航网格通常并不设计成类似于人类玩家将拥有的移动自由。受这些网格限制的任何代理人很可能会在探索环境时失败，而不像人类那样全面，因此会错过人类玩家经常发现的那些错误。在下一节中，我们将讨论如何使用 RL 代理来控制导航并改善探索。

We make use of proximal policy optimization (PPO) [14] as our RL training algorithm. PPO is a robust and well established baseline within the RL community when working with continuous action spaces. We evaluate and compare the performance of the agents when providing two different types of observations. The first one consists of an aggregate vector of 37 values: agent position ($\mathbb{R}^{3}$), agent velocity ($\mathbb{R}^{3}$), agent world rotation ($\mathbb{R}^{4}$), is climbing ($\mathbb{B}$), is in contact with ground ($\mathbb{B}$), jump cool-down time ($\mathbb{R}$), and a vision array ($\mathbb{R}^{24}$). The vision array consists of 12 ray casts projected in various directions around the agent (see Fig. 2). Each of these rays provides two values: a collision distance and a semantic meaning depending on the type of object it collides with. All values are normalized to be kept between $[-1,1]$. We also explore a second configuration by providing the agents with an additional first person view of the environment and we compare both models in Section IV-A.
我们使用近端策略优化（PPO）[14]作为我们的强化学习训练算法。在处理连续动作空间时，PPO 是强化学习社区内一个稳健且成熟的基准。我们评估并比较代理的性能，当提供两种不同类型的观察时。第一种包括一个包含 37 个值的聚合向量：代理位置（ $\mathbb{R}^{3}$ ），代理速度（ $\mathbb{R}^{3}$ ），代理世界旋转（ $\mathbb{R}^{4}$ ），是否攀爬（ $\mathbb{B}$ ），是否接触地面（ $\mathbb{B}$ ），跳跃冷却时间（ $\mathbb{R}$ ），以及一个视觉数组（ $\mathbb{R}^{24}$ ）。视觉数组包括 12 个射线投影在代理周围不同方向上（见图 2）。每条射线提供两个值：碰撞距离和语义含义，取决于它碰撞的对象类型。所有值都被归一化以保持在 $[-1,1]$ 之间。我们还探索了第二种配置，通过为代理提供额外的第一人称视角环境，并在第 IV-A 节中比较这两种模型。

The reward given to the agents is a function of novelty and it is described, together with the reset logic, in the following sections. The algorithm’s hyperparameters and the model’s architecture are presented in Table I.
给予代理的奖励是新颖性的函数，并且它与重置逻辑一起在以下部分中描述。算法的超参数和模型的架构在表 I 中呈现。

One of the great advantages of automated testing is the ability to parallelize and scale to a degree which is unfeasible to reach with human participants alone. The results described in this paper were collected while simulating and training 320 agents distributed across multiple machines. Our distributed setup allows us to train a single and centralized model using data collected from multiple environment instances. Instantiating a single training server also allows us to easily process, analyze, and store all the data collected by the agents in a single place.
自动化测试的一个巨大优势是能够并行化和扩展到人类参与者无法达到的程度。本文描述的结果是在模拟和训练 320 个代理分布在多台机器上时收集的。我们的分布式设置允许我们使用从多个环境实例收集的数据来训练单一和集中的模型。实例化单个训练服务器还允许我们轻松处理、分析和存储代理收集的所有数据在一个地方。

The reward given to the agents is computed following the idea of count-based exploration [15] and becomes, therefore, inversely proportional to how frequent a given game state has been visited. We define these states as the 3D position of the agent at a given point in time. Keeping track of these visit counters on a continuous space, however, quickly becomes intractable. To solve this problem, we discretize the space by means of a threshold $\uptau$. An agent is only considered to have entered a new state once its distance to any previously visited state is larger than $\uptau$.
奖励给予的代理根据基于计数的探索思想[15]计算，因此与给定游戏状态的访问频率成反比。我们将这些状态定义为代理在某一时间点的三维位置。然而，在连续空间中跟踪这些访问计数很快变得难以处理。为了解决这个问题，我们通过一个阈值 $\uptau$ 对空间进行离散化。只有当代理到先前访问的任何状态的距离大于 $\uptau$ 时，才认为代理已进入新状态。

Using a small value for $\uptau$ increases the number of points we will need to keep track of and may therefore hinder performance when working with large maps. A high value, on the contrary, results in a very sparse reward signal for our agents which significantly increases the difficulty of the task. The value of $\uptau=$5\text{\,}\mathrm{m}$$ was empirically found after a couple of experiments and has proven to be a sensible choice not only on the scenario presented here, but also in other maps not shown in this paper.
使用较小的 $\uptau$ 值会增加我们需要跟踪的点的数量，因此在处理大地图时可能会影响性能。相反，较高的值会导致我们的代理程序获得非常稀疏的奖励信号，从而显著增加任务的难度。 $\uptau=$5\text{\,}\mathrm{m}$$ 的值是在几次实验后经验性地找到的，并且已经被证明不仅在这里提出的场景中是一个明智的选择，而且在本文未展示的其他地图中也是如此。

When a new observation is received, the first step to compute a reward is to extract the position $p$ of the agent and compare it to all the previously visited states. This buffer is initially empty and gets populated as exploration takes place. We also keep track of a visit counter $N_{i}$ for each point $i$ in the current buffer. If the minimum distance between the current position $p$ and the points in the buffer is larger than $\uptau$, then point $p$ is added to the buffer and its visit counter is set to 1. If, on the contrary, the minimum distance is smaller than $\uptau$, we identify the point $i$ within the buffer closest to $p$ and increment $N_{i}$ by 1. Having done this, the reward for reaching point $i$ is computed using Equation 1, where $R_{max}$ is set to 0.5 and defines the reward for exploring a new point, and $max\_counter$ is set to 500, thus annealing the reward down to zero as a given point gets more frequent visits.
当收到新的观察时，计算奖励的第一步是提取代理的位置 $p$ 并将其与所有先前访问过的状态进行比较。该缓冲区最初为空，并随着探索的进行而填充。我们还跟踪当前缓冲区中每个点 $i$ 的访问计数器 $N_{i}$ 。如果当前位置 $p$ 与缓冲区中的点之间的最小距离大于 $\uptau$ ，则将点 $p$ 添加到缓冲区，并将其访问计数器设置为 1。相反，如果最小距离小于 $\uptau$ ，我们将识别缓冲区中距离 $p$ 最近的点 $i$ ，并将 $N_{i}$ 增加 1。完成此操作后，使用方程式 1 计算到达点 $i$ 的奖励，其中 $R_{max}$ 设置为 0.5，并定义探索新点的奖励， $max\_counter$ 设置为 500，因此将奖励降低到零，因为给定点的访问次数更频繁。

Each training episode is simulated for 3000 steps (equivalent to 1 minute of game play) and the agents are respawned once time is up. An initial spawning location was defined for this scenario and is located near the middle of the map at ground level. As training goes on spawning locations are sampled from the current buffer using the inverse of the corresponding visit counters as sample weights. This logic prevents biasing the exploration by respawning the agents in previously unexplored positions while giving priority to less frequently visited locations.
每个训练周期模拟进行 3000 步（相当于 1 分钟的游戏时间），并且当时间到达时，代理会重新生成。为此场景定义了一个初始生成位置，位于地图中间靠近地面的位置。随着训练的进行，生成位置将从当前缓冲区中使用相应访问计数器的倒数作为样本权重进行抽样。这种逻辑可以防止通过重新生成代理在先前未探索的位置引入偏见，同时优先考虑访问频率较低的位置。

To prevent agents from spawning in mid-air, we take advantage of one of the values available in the observation vector: $is\_in\_contact\_with\_ground$. When storing a new point in the buffer we keep track of whether or not the character was stepping on something when at that location. Then, when sampling a new spawn position, we can just consider the points in the buffer for which this condition is true.
为了防止代理在半空中生成，我们利用观察向量中的一个可用值之一： $is\_in\_contact\_with\_ground$ 。在将新点存储到缓冲区时，我们会跟踪角色在该位置时是否站在某物体上。然后，在抽样新的生成位置时，我们只考虑满足此条件的缓冲区中的点。

This way of respawning the agents at previously visited states strongly resembles algorithms such as Rapidly-Exploring Random Trees (RRT) [16]. In contrast to the exploration strategies proposed in [6], however, we take advantage of the complex navigation strategies developed by our agents to explore around those spawning locations. In Section IV we compare the performance of our approach to the one of a random policy very similar to the chaos monkey strategy proposed in [6]. This random policy employs the same respawning logic presented above which allows us to fairly compare both techniques.
这种在先前访问过的状态重新生成代理的方式与诸如快速探索随机树（RRT）[16]等算法强烈相似。然而，与[6]中提出的探索策略相比，我们利用我们的代理开发的复杂导航策略来探索这些生成位置周围。在第四节中，我们将我们的方法的性能与类似于[6]中提出的混沌猴策略的随机策略进行比较。这种随机策略采用了上述相同的重新生成逻辑，这使我们能够公平地比较这两种技术。

Different kinds of data are continuously processed and stored while the agents interact with the environment. Most of this data is handled by the centralized training process which receives all episodic information (i.e. observations, actions, rewards). Some of the data, however, is recorded directly by the environments based on possible events triggered by the agents which are harder to identify outside the engine. The nature of this data, and how it is used to identify and correct problems, is described together with the corresponding experiments in the next section.
与环境交互时，不同类型的数据会持续处理和存储。大部分数据由集中式训练过程处理，该过程接收所有情节信息（即观察、动作、奖励）。然而，一些数据是由环境直接记录的，基于代理触发的可能事件，这些事件在引擎外部很难识别。这些数据的性质以及如何用于识别和纠正问题，将在下一节中与相应的实验一起描述。

Other relevant metrics such as the number of visited states and values relevant to the RL algorithm are also continuously logged and visualized as training goes on. These logs are very useful to quickly judge and/or compare the performance of a set of experiments without the need of waiting until their completion.
其他相关指标，如访问状态的数量和与 RL 算法相关的值，也会持续记录和可视化，随着训练的进行。这些日志非常有用，可以快速评估和/或比较一组实验的性能，而无需等待它们完成。

The first thing we would like to evaluate is the ability of our RL agents to navigate and explore the whole map. To do this, we make use of the buffer of visited states introduced in Section III-C. This set of visited 3D coordinates is stored and updated as training goes on and can be used as a metric for exploration and coverage. Fig. 3 shows the percentage of the map covered by our agents when compared to a random policy. As expected, the random based exploration technique did not cover the whole map due to its complexity and was only able to reach easily accessible areas. Moreover, complementing the observation space of our RL agents with a camera image (first person view) improves the results by allowing the model to better understand its surroundings and by decreasing the uncertainty introduced by the discrete set of ray casts. It currently takes around 24 hours to explore 90% of the map but, as discussed in Section V, we believe that coming up with better and more efficient ways for encoding the environment may boost the performance of the agents and speed up exploration.
我们想要评估的第一件事是我们的 RL 代理在整个地图中导航和探索的能力。为此，我们利用了第 III-C 节介绍的访问状态缓冲区。这组访问过的 3D 坐标被存储并随着训练的进行而更新，可以用作探索和覆盖的度量标准。图 3 显示了我们的代理相对于随机策略覆盖地图的百分比。正如预期的那样，基于随机的探索技术由于其复杂性而未能覆盖整个地图，只能到达易于访问的区域。此外，通过用摄像头图像（第一人称视角）补充我们的 RL 代理的观察空间，可以通过使模型更好地理解周围环境并减少由离散射线集引入的不确定性来改善结果。目前需要大约 24 小时才能探索地图的 90％，但正如第 V 节中讨论的那样，我们相信想出更好更高效的环境编码方式可能会提升代理的性能并加快探索速度。

As shown in Figs. 4 and 5, all the data collected by the agents (e.g. the buffer of visited states) can also be loaded and displayed on top of the map. These visualizations allow the designers to verify whether or not different areas across the map are reachable and also allow us to compare the exploration performance of different navigation strategies. Both figures showcase a couple of relatively complex navigation challenges spread across the map and the extend of the exploration coverage achieved by our RL agents when compared to a simple random exploration strategy.
如图 4 和 5 所示，代理收集的所有数据（例如访问状态的缓冲区）也可以加载并显示在地图顶部。这些可视化使设计人员能够验证地图上不同区域是否可达，还允许我们比较不同导航策略的探索性能。两幅图展示了地图上分布的几个相对复杂的导航挑战，以及我们的 RL 代理相对于简单的随机探索策略所实现的探索覆盖范围。

Another set of interesting findings relates to the agents reaching areas which should have been inaccessible for the player. These areas could be identified either by visually inspecting the distribution of the collected points or, as shown in the next section, by defining exploration boundaries.
另一组有趣的发现与代理到达本应对玩家不可及的区域有关。这些区域可以通过直观地检查收集点的分布或者如下一节所示，通过定义探索边界来识别。

Our method allows the designer to specify both an exploration boundary (EB) and regions of interest (ROIs) across the map prior to training. The EB defines the section of the map which should be explored and the episode terminates whenever the agent exits that boundary. The ROIs, on the other hand, are optional regions inside the EB and serve as a reference for data collection.
我们的方法允许设计师在训练之前指定探索边界（EB）和兴趣区域（ROIs）的地图上。EB 定义了应该被探索的地图部分，当代理程序退出该边界时，该情节终止。另一方面，ROIs 是 EB 内的可选区域，用作数据收集的参考。

Although we would like to record and store the specific trajectories followed by the agents, doing so would quickly become too expensive and intractable during long simulations. The definition of the EB and the ROIs, however, allows us to focus on those trajectories which are likely to be useful for testing the game. Our technique keeps track of the episodic trajectory for each agent but only records them if a couple of conditions are met: first, the trajectory needs to cross over the boundary defining either the EB or a ROI; second, the point at which the agent crosses that boundary needs to be significantly different to the one of any previously recorded trajectories.
尽管我们希望记录并存储代理程序所遵循的具体轨迹，但这样做很快会变得过于昂贵和难以处理，尤其是在长时间模拟过程中。然而，EB 和 ROIs 的定义使我们能够专注于那些可能对测试游戏有用的轨迹。我们的技术跟踪每个代理程序的情节性轨迹，但只有在满足一些条件时才记录它们：首先，轨迹需要越过定义 EB 或 ROI 的边界；其次，代理程序越过该边界的点需要与先前记录的任何轨迹的点明显不同。

Fig. 6 shows examples of trajectories leaving the EB when that boundary is defined at the walls surrounding the scenario in Fig. 1. Our technique allows the user to display these trajectories directly in the game engine and, in this case, would reveal design oversights around the map allowing the player to leave the game area. Figs. 7 and 8 show additional examples of the kinds of issues which could be identified using these visualizations. Fig. 7 shows a trajectory leaving the scenario due to a collision box missing in one of the wall segments. This particular oversight was intentionally introduced in the map to validate the usefulness of the collected data. Interestingly, not all of the problems we were able to identify were intentionally added to the game. Fig. 8, for example, shows a trajectory recorded during some of our first design iterations. In this case, the agent was getting stuck in between two objects and the physics engine would eventually throw it upwards forcing the character to leave the EB. This shows the use these visualizations could have for identifying problems early on in the design process.
图 6 显示了当边界在图 1 中定义的围绕场景的墙壁时，离开 EB 的轨迹示例。我们的技术允许用户直接在游戏引擎中显示这些轨迹，并且在这种情况下，将揭示围绕地图的设计疏漏，使玩家能够离开游戏区域。图 7 和图 8 显示了使用这些可视化工具可以识别的问题类型的其他示例。图 7 显示了由于一个墙壁段缺少碰撞框而导致轨迹离开场景。这种特定的疏忽是故意引入地图中的，以验证收集数据的有用性。有趣的是，并非所有我们能够识别的问题都是故意添加到游戏中的。例如，图 8 显示了在我们最初的设计迭代中记录的轨迹。在这种情况下，代理人被卡在两个物体之间，物理引擎最终会将其向上抛出，迫使角色离开 EB。这显示了这些可视化工具在设计过程早期识别问题方面的用途。

The ROIs, on the other hand, allow the user to validate the reachability and access to particular areas in the map. Fig. 9 shows two such regions which were intended to be unreachable for the player. The agents were indeed unable to reach the first region and therefore no trajectories were recorded. The second region, however, ended up having one access point which could be identified using the collected data.
另一方面，ROI 允许用户验证地图中特定区域的可达性和访问性。图 9 显示了两个此类区域，本意是玩家无法到达的。代理确实无法到达第一个区域，因此没有记录到轨迹。然而，第二个区域最终有一个访问点，可以使用收集的数据进行识别。

We can do more than just storing a point cloud of visited states. We can, for instance, configure our training server to build and store a graph structure representing the connectivity between those points. For this reason, the episodic trajectories collected to train our agents are also used to generate a directed graph as the one shown in Fig. 10. Even though the accuracy of such a graph strongly depends on our discretization threshold $\uptau$ (see Section III-C), we believe it has a couple of very promising applications as presented next.
我们不仅可以存储已访问状态的点云。例如，我们可以配置我们的训练服务器来构建和存储表示这些点之间连接性的图结构。因此，用于训练我们的代理的情节轨迹也用于生成一个有向图，如图 10 所示。尽管这样的图的准确性在很大程度上取决于我们的离散化阈值 $\uptau$ （请参见 III-C 节），但我们认为它有几个非常有前途的应用，如下所示。

It is common for players to find themselves stuck in some particular part of the map due to issues in the environment or the location of the game assets which render the playing character immovable. Maximizing exploration coverage gives us the opportunity to automatically identify such locations during training. One approach is to keep track of a termination counter for each point in our buffer of visited states (i.e. how many times an episode ended with an agent in that location). Once training is over, we can proceed and analyze the distribution of terminal states. Any outlier in this distribution can be easily identified and it is likely to be caused by the agents getting stuck in that position.
玩家常常会发现自己因为环境问题或游戏资产的位置而被困在地图的某个特定部分。这使得玩家角色无法移动。最大化探索范围为我们提供了在训练期间自动识别这些位置的机会。一种方法是跟踪我们访问状态缓冲区中每个点的终止计数（即一个情节以代理在该位置结束的次数）。训练结束后，我们可以继续分析终端状态的分布。这个分布中的任何异常值都可以很容易地被识别出来，很可能是由于代理被困在那个位置造成的。

We conducted experiments by introducing areas across the map where the agents could get stuck. Fig. 14 shows some examples of such locations together with the outlier positions identified from the collected data. Due to the high coverage achieved by our agents, all the intentionally introduced issues could be identified, as well as one unintentional design oversights causing a similar problem (see Fig. 14(a)).
我们通过在地图各处引入代理可能被困的区域来进行实验。图 14 显示了一些这样的位置示例，以及从收集到的数据中识别出的异常位置。由于我们的代理实现了高覆盖率，所有故意引入的问题都能被识别出来，以及一个无意中导致类似问题的设计疏忽（见图 14(a)）。