Physics-Based Task Generation through Causal Sequence of Physical Interactions

In recent years, researchers have developed various environments as benchmarks and testbeds to evaluate the physical reasoning capabilities of AI agents. These environments are mainly based on tasks that involve taking actions in a physical environment (Xue et al. 2023; Bakhtin et al. 2019), reasoning about images of physical scenarios (Hong et al. 2021; Wolf 2020), and reasoning about videos of physical scenarios (Riochet et al. 2020; Yi et al. 2020). Among them, task generation methods used in action-based environments are related to this work as we also focus on generating tasks that an agent can interact with and take actions to solve them. Examples of recent action-based environments include Phy-Q (Xue et al. 2023), PHYRE (Bakhtin et al. 2019), Virtual Tools (Allen, Smith, and Tenenbaum 2020), OGRE (Allen et al. 2020), CausalWorld (Ahmed et al. 2021), and RLBench (James et al. 2020).

The design and development of tasks in these works are predominantly done manually by developers, with most utilizing automated generation techniques to create simple variations of handcrafted task templates. For example, Phy-Q testbed has handcrafted task templates for 15 physical scenarios, and tasks are generated from those templates by slightly varying the locations of objects in the template and adding distracting objects. PHYRE, Virtual Tools, and OGRE follow a similar procedure. They all have pre-designed task templates and tasks are generated by either varying the shape, size, and location of the original template. CausalWorld is a robotic benchmark with eight types of tasks, such as pushing, picking, picking and placing, and stacking. They have separate generators to generate tasks for each of those task types. The generators have hard-coded templates, and the tasks are generated by sampling new tasks from those templates.

Despite the use of automated generation techniques to some extent in these benchmarks and testbeds, task generation is still heavily reliant on pre-defined templates. The process of creating these templates can be tedious and time-consuming, as the template developer must ensure that the template is stable under gravity and other physical constraints, solvable, and flexible enough to allow for modifications in task generation. In contrast, our proposed generation method does not require any initial task templates. Instead, the input to the generator is a minimal description of the physical scenario, defined as a sequence of physical interactions between objects that leads to solving the task. This approach eliminates the need for pre-designed templates and simplifies the task generation. Furthermore, tasks generated from this method consider the physical interactions involved in solving the task, allowing for systematic categorization of tasks into distinct physical scenarios based on the involved physical interactions. This feature is particularly valuable for physical reasoning testbeds and benchmarks, as it can be used to classify tasks systematically and evaluate AI agents’ strengths and weaknesses more comprehensively. The current task classifications on those benchmarks do not justify why a given task belongs to its class.

Physics-based puzzle games have gained popularity in the field of Procedural Content Generation (PCG) owing to the intriguing physics-related challenges that are encountered while generating content for such games, which are applicable to real-world physics challenges. Popular physics puzzle games, such as Angry Birds (Stephenson et al. 2018) and Cut the Rope (Shaker, Shaker, and Togelius 2013), have been used as test domains by researchers to investigate physics-based content generation techniques. Of these games, Angry Birds has received considerable attention in the research community, particularly in the fields of PCG (Stephenson et al. 2018) and AI game-playing agent development (Renz et al. 2019). Consequently, in this study, we utilize Angry Birds as a test domain to showcase our proposed task generation methodology.

Angry Birds is a 2D physics simulation game wherein players must destroy pigs in a given game level by launching a designated number of birds from a slingshot. The levels in the game consist of dynamic objects (birds, blocks, and pigs) that adhere to Newtonian physics and static objects (platforms) that are not influenced by external forces. The dynamic objects possess health points that decrease upon collision and are destroyed when their health points are completely depleted. In this study, we use Science Birds (Ferreira and Toledo 2014), a research clone of the game developed in Unity with the Box2D physics engine. A modified version of Science Birds, with adjusted physics parameters and health points of objects, is employed to effectively showcase the proposed methodology. The modifications address limitations in Science Birds’ object dynamics and fragility, ensuring a more accurate demonstration of the methodology. Figure 1 displays a game level from Angry Birds in Science Birds, showcasing the primary game objects utilized in this study.

Numerous research studies have explored various methods for creating game levels in Angry Birds. Prior investigations have tackled this problem from diverse angles, proposing solutions to intriguing challenges, such as generating stable structures within the physical environment (Stephenson and Renz 2017), dynamically adjusting the game levels’ difficulty (Stephenson and Renz 2019), creating block structures based on hand-drawn sketches (Stephenson et al. 2021), generating deceptive levels to deceive AI agents (Gamage et al. 2021a), generating novel scenarios for physics environments (Gamage et al. 2023, 2021b) and, most recently, using prompt engineering to create prompts for level generation (Taveekitworachai et al. 2023). None of the previous studies has treated the level generation for Angry Birds as a task generation problem that incorporates the physical interactions between the game objects. This paper proposes a novel approach that defines a task as a causal sequence of physical interactions and generates tasks whose solution follows this sequence. The generation process considers the effect of force and motion on the interactions of objects, resulting in a more scientifically grounded approach in terms of dynamic physics. By generating tasks based on the physical interactions present in the solution, agents can be evaluated and compared based on their performance in specific interaction sequences of interest. Therefore, the proposed generation method enables a rigorous evaluation of AI agents’ physical reasoning abilities, similar to the evaluation conducted in the Phy-Q testbed that uses handcrafted Angry Birds levels.

The introduced grammar is used to describe objects, interactions, restrictions, and object layouts in a physical environment. The grammar consists of four components, namely, object grammar, interaction grammar, restriction grammar, and layout grammar. The first three grammar components are utilized to define physical scenarios, while the last grammar component is utilized in the generation process for defining the object layouts within the physical environment.

As stated previously, the object grammar, interaction grammar, and restriction grammar components are used to define the scenarios. The initial step of defining a scenario involves identifying the objects that are relevant to the scenario, which are characterized using the object grammar. The next step is to determine the intended sequence of physical interactions that must take place between these objects to obtain a solution for the scenario. These interactions are described using the interaction grammar and are arranged sequentially based on their causality. If any interaction needs to be restricted between the objects in the scenario, the restriction grammar is employed to add them.

Table 5 displays 16 sample scenarios, which were defined for illustrative purposes in this study. Scenarios one through seven were created to replicate the physical scenarios of Single Force (1 to 3), Rolling (4), Falling (5), Sliding (6), and Bouncing (7) in the Phy-Q testbed. For instance, in the first scenario, the bird collides with the pig from any direction, causing the pig to be destroyed, and there are no associated restrictions. In the second and third scenarios, the bird cannot collide with the pig from above or from the left, respectively, due to imposed restrictions. In the fourth scenario, the bird hits a rollable block, causing it to roll on a surface and then collide with a pig, leading to its destruction. The restrictions in this scenario state that the bird cannot collide directly with the pig (i.e., the player cannot shoot the bird directly at the pig to solve the task) and that the rollable block must not fall during its movement. Scenarios eight to 12 combine two out of Rolling, Falling, Sliding, and Bouncing, while scenarios 13 to 16 combine three of them.

The generation process begins by determining the objects required to be present in the scenario and inferring the layout constraints between the objects. To achieve this, the scenario definition is used to identify all objects required for the scenario. Then, the layout constraints are inferred based on the interactions and restricted interactions between objects and the constraints are described using the layout grammar. The layout constraints that can be inferred are shown in Table 6. The layout constraint graph is then generated with the objects in the scenario as nodes and the directed edges representing the layout constraints between the objects. In this process, a layout optimization is conducted to remove redundant layout constraints and ensure physical stability. This stability enhancement involves confirming that dynamic objects are supported by static ones and adding static objects beneath those not adequately supported, ensuring equilibrium under gravity assuming that the task is initially stable. Figure 2 presents the layout graphs of scenarios 6 and 9.

In this phase, the graph of layout constraints is transformed into a spatial relationship graph among objects in 2D Euclidean space. To accomplish this, we draw inspiration from various QSR calculi, including cardinal direction relations (Frank 1991), interval relationships (Allen 1983), and topological relationships (Clementini and Di Felice 1997). To meet the requirements of this study, we introduce a range of spatial predicates that are relevant to objects in 2D Euclidean space. Usually, in QSR literature, 2D objects are represented using their Minimum Bounding Rectangle (MBR) (Chen et al. 2013). However, this approach has limitations when determining the actual corner positions of an object if it is rotated, which is important for determining the precise placement of neighbouring objects, especially when satisfying the layout terms such as touching. To overcome this, we suggest a 5-point representation for a 2D object using the positions of 5 points lower left (ll), centre (c), upper right (ur), upper left (ul), and lower right (lr). When defining QSRs, we assume that objects have a maximum of 90 degrees of rotation. The defined QSRs are illustrated in Figure 3. The layout constraints are translated into spatial constraints using these QSRs. The QSRs in our defined set that can be inferred for the layout constraints are shown in Table 7.

As can be seen from Table 7, a single layout constraint can be mapped to various QSRs. Additionally, the generator can leverage the flexibility in defining the scenario by overloading the parameters of the grammar terms, such as in scenario 10, allowing the bird to hit the fBlock from either the left or the above and enabling the fBlock to hit the rBlock from either the above or the left. These opportunities for flexibility in the generation process enable the generation of a varied range of layout configurations for a given scenario definition.

At this stage of task generation, we have a set of spatial constraints among objects in the 2D Euclidean space. These spatial constraints are denoted as point connections using the above-mentioned 5-point representation of the objects. Now, the task at hand is to examine the consistency of these Euclidean spatial constraints among points. The purpose of consistency checking is to ensure the existence of a plausible spatial configuration that satisfies the constraints. To tackle this issue, we use an approach based on the dimension graph representation for managing the spatial constraints between objects (Liu, Shekhar, and Chawla 2001). In this technique, the spatial constraints are projected onto the X and Y dimensions, and the constraints that need to be met for each dimension are stored in separate graphs. From this technique, the problem of checking constraint consistency is reformulated as a graph cycle detection problem on the dimension graph. The constraints are considered consistent if both the X and Y dimension graphs are free of cycles. Figure 4 illustrates the dimension graphs of a sample conjunctive constraint. It is noteworthy that the illustration in this example employs the MBR of the objects for the sake of simplicity, whereas in this study, a more complex 5-point representation is used.

During the construction of dimension graphs, constraints in a general format are converted to the Disjunctive Normal Form (DNF), which is a disjunction of conjunctions without any disjunction within a conjunction. For instance, a constraint graph with N(a,b)$\vee$NE(a,b) and NE(b,c) and SW(c,a) can be transformed to (N(a,b)$\wedge$NE(b,c)$\wedge$SW(c,a))$\vee$(NE(a,b)$\wedge$NE(b,c)$\wedge$SW(c,a)) in DNF format. Consequently, for a given constraint graph, there exists a pool of dimension graph pairs (for X and Y dimensions) that can be generated from all its conjunctions. The pool size is equivalent to the number of conjunctions in the DNF. In the generation process, a random pair of dimension graphs is selected, and its cycles are checked. If there are no cycles, the generation proceeds to the next steps; otherwise, another pair is chosen and tested. In case no pair in the pool without cycles (i.e., all possible combinations of constraints are inconsistent) is found, the scenario defined is considered unfeasible to accomplish in the 2D Euclidean space. Once a consistent set of constraints is determined, the forward checking technique is employed to solve them, and a set of possible values for the points (i.e., object positions) is obtained.

Although qualitative methods can provide a useful starting point to narrow down the extensive and unbounded generative space, they may not be sufficient to fully address the challenges posed by physical environments. The physical environments present a multitude of challenges that are difficult to overcome through purely qualitative methods. Interactions between objects in these environments are complex and even slight variations in these interactions can result in significant changes in the overall outcome. As such, researchers have relied on simulation-based techniques when generating physics-based tasks (Stephenson and Renz 2017; Gamage et al. 2021a).

In this step of the generation process, the destroy interaction and the constraints of liesOnPath and pathObstructed are satisfied by simulating the physics engine of the game. The simulation begins by setting up the objects in the game space according to their predetermined positions from the previous steps. Then, the behaviours of objects are observed for constraint satisfaction by executing potential solution actions (i.e., shooting the bird at the object that initiates the interaction sequence). However, due to the continuous action space in Angry Birds (where shooting angles can be chosen from a continuous range), there exist numerous actions with slight variations. Therefore, the possible solution space is discretized by taking into account the target points and the stretch of the slingshot when shooting the bird. Specifically, only certain points of interest on the target object (such as the ll, ul, and ur) are selected, and it is assumed that the bird is always shot with the full stretch of the slingshot, resulting in only two possible trajectories to reach a target point. Shooting with the full stretch reflects the current capability of Angry Birds playing agents (Xue et al. 2023).

The object destruction model in the game is based on the health points which diminish through collisions and is mainly reliant on the materials of the colliding objects and the relative velocities they attain during the collision. In order to ensure that the destroy interaction is fulfilled, the health points of the objects of interest are closely monitored at the relevant juncture of the interaction sequence.

To ensure that the liesOnPath and pathObstructed constraints are satisfied, precise consideration of the moving paths of the objects is required. The simulation results are used to observe the paths of the objects associated with these constraints. To satisfy liesOnPath(a)(b), the position of the object a is adjusted to the location that intersects the most paths of b for different actions from the solution actions. After repositioning, the new object configuration is verified by checking whether it still satisfies all the spatial constraints considered in the previous steps. If not, the process is repeated by repositioning object a to the next position that cuts the most paths, and so on. Once the liesOnPath constraints are satisfied, the pathObstructed constraints are handled. The pathObstructed(a)(b) constraint is satisfied by blocking the paths of a that lead to b, by adding platform objects as obstacles. The simulation results and QSRs between the objects are used to determine the paths of the object a that lead to b. It is ensured that the added obstacles do not interfere with the defined interaction sequence of the task.

If any of the simulation satisfactions fail during the generation process, the approach retries with a different dimension graph pair from the pool of dimension graphs, which is associated with a different conjunctive constraint in the DNF. This process is repeated until a feasible dimension graph pair is found. If the entire pool of dimension graphs is exhausted without finding a feasible solution, it is concluded that the defined scenario is infeasible to achieve.

In this work, the main purpose of generating these tasks is to use them to assess the physical reasoning capabilities of AI agents. But when solving the tasks, agents may rely on spurious patterns instead of reasoning about the underlying physics. To prevent the exploitation of such patterns, we introduce a random number of distracting objects at arbitrary positions within the generated tasks. This approach aims to reduce the likelihood of agents exploiting specific patterns, such as ‘shoot the bird at the path unobstructed block’, and encourages agents to engage in genuine physical reasoning.

In the final step, the solvability of the task is verified by executing the intended solution, which entails shooting the bird at the target object that initiates the interaction sequence. Upon successful completion, the output of the generator is a game level that possesses a definite solution consistent with the defined causal sequence of physical interactions.

In physical environments, ensuring the physical stability of the tasks is crucial. Despite the absence of complex physical structures in the tasks generated through the proposed method, ensuring the physical stability of all the dynamic objects in a task is essential for overall stability. As discussed previously, when creating the layout constraint graph, the physical stability of dynamic objects is ensured by introducing supports. Additionally, during the last stage of generation, distracting objects are placed only in locations that can sufficiently support their stability. The generation process strictly enforces these stability checks, resulting in a 100% physical stability rate for tasks across all scenarios.

In this evaluation, we assess the solvability of the generated tasks using the intended sequence of physical interactions defined in the scenario used to generate the task. To determine the solvability rate, the solution of each task (i.e., the shooting angle of the bird) was recorded during the task generation process and then executed using a playtest agent. Notably, the final step of the generation process that usually validates solvability was skipped in this experiment to evaluate how often the proposed methodology generates a solvable task. The solvability rate was calculated as the percentage of tasks that can be solved using their intended solutions. The results, shown in Table 8, demonstrate that the solvability rate decreases as the number of interactions in the scenario increases. Specifically, the highest rate is 100% for tasks with two interactions, while the lowest rate is 82% for tasks with eight interactions.

There is a potential for unintended interactions leading to solving the tasks in a continuous physical environment, which can be exploited by AI agents, thereby limiting the credibility of the evaluations conducted using those tasks. We propose the accidental solvability evaluation to assess the vulnerability of the generated tasks to unintended solutions. The evaluation involves the deployment of a heuristic agent, that systematically shoots at all dynamic blocks in the game level, excluding the target block for the solution. The heuristic of shooting at different types of objects located at different positions is widely used by many Angry Birds agents (Stephenson et al. 2018).

The accidental solvability rate ($AS_{i}$) of a scenario $i$ is calculated using Equation 1, where $N_{i}$ is the total number of levels tested, $P_{n}$ is the total number of plays used to test the $n^{th}$ level, and $S_{np}$ is 1 if the $n^{th}$ level is solved by the $p^{th}$ strategy, or 0 otherwise. The $AS_{i}$ value ranges between 0 and 1, and a higher value indicates a higher vulnerability to unintended solutions. The results shown in Table 8 demonstrate a decreasing trend in accidental solvability rate as the interaction count of the scenario increases. Specifically, the highest rate is 12% for tasks with two interactions, while the lowest is 3% for tasks with eight interactions.

The task generator is implemented in C# within the Unity game engine and integrated into the Angry Birds clone, Science Birds. The simulation-based components of the generator were executed by accelerating the physics engine by a factor of five. The experiments were performed on a Windows 10 desktop computer with an i9-9900KS CPU and 64GB RAM. The runtime of the generator was measured by recording the time taken to produce tasks for each sample scenario. The last row in Table 8 presents the results of the runtime analysis, indicating that the generation time increases linearly with the complexity of the scenario.