Due to the emergence of AI systems that interact with the physical environment, there is an increased interest in incorporating physical reasoning capabilities into those AI systems. But is it enough to only have physical reasoning capabilities to operate in a real physical environment? In the real world, we constantly face novel situations we have not encountered before. As humans, we are competent at successfully adapting to those situations. Similarly, an agent needs to have the ability to function under the impact of novelties in order to properly operate in an open-world physical environment. To facilitate the development of such AI systems, we propose a new benchmark, NovPhy, that requires an agent to reason about physical scenarios in the presence of novelties and take actions accordingly. The benchmark consists of tasks that require agents to detect and adapt to novelties in physical scenarios. To create tasks in the benchmark, we develop eight novelties representing a diverse novelty space and apply them to five commonly encountered scenarios in a physical environment, related to applying forces and motions such as rolling, falling, and sliding of objects. According to our benchmark design, we evaluate two capabilities of an agent: the performance on a novelty when it is applied to different physical scenarios and the performance on a physical scenario when different novelties are applied to it. We conduct a thorough evaluation with human players, learning agents, and heuristic agents. Our evaluation shows that humans' performance is far beyond the agents' performance. Some agents, even with good normal task performance, perform significantly worse when there is a novelty, and the agents that can adapt to novelties typically adapt slower than humans. We promote the development of intelligent agents capable of performing at the human level or above when operating in open-world physical environments. Benchmark website: https://github.com/phy-q/novphy

In response to the growing demand for AI systems that can operate the physical world, there has been an increasing interest in enhancing their physical reasoning capabilities. Equally crucial is the ability to handle unseen novel situations, as such situations frequently arise in real-world environments. To facilitate the development of AI systems with those abilities, researchers have developed testbeds with specialized tasks to evaluate agents' adaptation to novelty in physical environments. In this paper, we propose a method for generating physics-based tasks with incorporated novelties to assess agents' novelty adaptation capabilities. The tasks are defined as causal sequences of physical interactions between objects, and novelties are strategically introduced to disrupt existing causal relationships and construct new ones. This approach ensures that agents must adapt to the effects of novelties to perform those tasks, enabling confident measurement of their novelty adaptation capabilities using task performance. Moreover, our methodology eliminates the need for manual task creation, unlike existing novelty-centric testbeds. The proposed method is demonstrated and evaluated using 12 physical scenarios in the Angry Birds domain. The evaluated metrics include generation time, physical stability, intended solvability, intended unsolvability, and accidental solvability of the tasks, and they yielded favourable results compared to the literature.

This paper presents the second ChatGPT4PCG competition at the 2024 IEEE Conference on Games. In this edition of the competition, we follow the first edition, but make several improvements and changes. We introduce a new evaluation metric along with allowing a more flexible format for participants’ submissions and making several improvements to the evaluation pipeline. Continuing from the first edition, we aim to foster and explore the realm of prompt engineering (PE) for procedural content generation (PCG). While the first competition saw success, it was hindered by various limitations; we aim to mitigate these limitations in this edition. We introduce diversity as a new metric to discourage submissions aimed at producing repetitive structures. Furthermore, we allow submission of a Python program instead of a prompt text file for greater flexibility in implementing advanced PE approaches, which may require control flow, including conditions and iterations. We also make several improvements to the evaluation pipeline with a better classifier for similarity evaluation and better-performing function signatures. We thoroughly evaluate the effectiveness of the new metric and the improved classifier. Additionally, we perform an ablation study to select a function signature to instruct ChatGPT for level generation. Finally, we provide implementation examples of various PE techniques in Python and evaluate their preliminary performance. We hope this competition serves as a resource and platform for learning about PE and PCG in general1.1Source code and raw data: https://github.com/chatgpt4pcg/experiments2024

Due to the emergence of AI systems that interact with the physical environment, there is an increased interest in incorporating physical reasoning capabilities into those AI systems. But is it enough to only have physical reasoning capabilities to operate in a real physical environment? In the real world, we constantly face novel situations we have not encountered before. As humans, we are competent at successfully adapting to those situations. Similarly, an agent needs to have the ability to function under the impact of novelties in order to properly operate in an open-world physical environment. To facilitate the development of such AI systems, we propose a new benchmark, NovPhy, that requires an agent to reason about physical scenarios in the presence of novelties and take actions accordingly. The benchmark consists of tasks that require agents to detect and adapt to novelties in physical scenarios. To create tasks in the benchmark, we develop eight novelties representing a diverse novelty space and apply them to five commonly encountered scenarios in a physical environment, related to applying forces and motions such as rolling, falling, and sliding of objects. According to our benchmark design, we evaluate two capabilities of an agent: the performance on a novelty when it is applied to different physical scenarios and the performance on a physical scenario when different novelties are applied to it. We conduct a thorough evaluation with human players, learning agents, and heuristic agents. Our evaluation shows that humans' performance is far beyond the agents' performance. Some agents, even with good normal task performance, perform significantly worse when there is a novelty, and the agents that can adapt to novelties typically adapt slower than humans. We promote the development of intelligent agents capable of performing at the human level or above when operating in open-world physical environments. Benchmark website: https://github.com/phy-q/novphy.

This study summarizes the first ChatGPT4PCG competition held at the 2023 IEEE Conference on Games. The goal of the competition is to explore emergent abilities of publicly available LLMs in performing complex tasks related to procedural content generation, specifically physics-based level generation for Angry Bird-like games. Participants are tasked with submitting their prompts for ChatGPT to generate Angry Birds-like game structures that resemble English uppercase characters. A structure is a collection of stacked game objects comprising a part of an entire Angry Birds-like level. A prompt is an input for large language models (LLMs) including ChatGPT. Two evaluation metrics, i.e., stability and similarity, are used to evaluate the submitted prompts. Stability measures the sturdiness of a structure to withstand in-game gravity, while similarity measures a structure's resemblance to the target character. With such evaluation, participants are challenged not only to produce character-like but also stable structures by utilizing prompt engineering techniques. Finally, the competition's results are discussed to provide valuable insights for future studies and competitions.

This paper presents the first ChatGPT4PCG Competition at the 2023 IEEE Conference on Games. The objective of this competition is for participants to create effective prompts for ChatGPT–enabling it to generate Science Birds levels with high stability and character-like qualities–fully using their creativity as well as prompt engineering skills. ChatGPT is a conversational agent developed by OpenAI. Science Birds is selected as the competition platform because designing an Angry Birds-like level is not a trivial task due to the in-game gravity; the quality of the levels is determined by their stability. To lower the entry barrier to the competition, we limit the task to the generation of capitalized English alphabetical characters. We also allow only a single prompt to be used for generating all the characters. Here, the quality of the generated levels is determined by their stability and similarity to the given characters. A sample prompt is provided to participants for their reference. An experiment is conducted to determine the effectiveness of several modified versions of this sample prompt on level stability and similarity by testing them on several characters. To the best of our knowledge, we believe that ChatGPT4PCG is the first competition of its kind and hope to inspire enthusiasm for prompt engineering in procedural content generation.

In order to be trusted by humans, Artificial Intelligence agents should be able to describe rationales behind their decisions. One such application is human action recognition in critical or sensitive scenarios, where trustworthy and explainable action recognizers are expected. For example, reliable pedestrian action recognition is essential for self-driving cars and explanations for real-time decision making are critical for investigations if an accident happens. In this regard, learning-based approaches, despite their popularity and accuracy, are disadvantageous due to their limited interpretability. This paper presents a novel neuro-symbolic approach that recognizes actions from videos with human-understandable explanations. Specifically, we first propose to represent videos symbolically by qualitative spatial relations between objects called qualitative spatial object relation chains. We further develop a neural saliency estimator to capture the correlation between such object relation chains and the occurrence of actions. Given an unseen video, this neural saliency estimator is able to tell which object relation chains are more important for the action recognized. We evaluate our approach on two real-life video datasets, with respect to recognition accuracy and the quality of generated action explanations. Experiments show that our approach achieves superior performance on both aspects to previous symbolic approaches, thus facilitating trustworthy intelligent decision making. Our approach can be used to augment state-of-the-art learning approaches with explainabilities.

The Angry Birds AI competition has been held over many years to encourage the development of AI agents that can play Angry Birds game levels better than human players. Many different agents with various approaches have been employed over the competition's lifetime to solve this task. Even though the performance of these agents has increased significantly over the past few years, they still show major drawbacks in playing deceptive levels. This is because most of the current agents try to identify the best next shot rather than planning an effective sequence of shots. In order to encourage advancements in such agents, we present an automated methodology to generate deceptive game levels for Angry Birds. Even though there are many existing content generators for Angry Birds, they do not focus on generating deceptive levels. In this paper, we propose a procedure to generate deceptive levels for six deception categories that can fool the state-of-the-art Angry Birds playing AI agents. Our results show that generated deceptive levels exhibit similar characteristics of human-created deceptive levels. Additionally, we define metrics to measure the stability, solvability, and degree of deception of the generated levels.

Handling novel situations is a critical capability of Artificial Intelligence (AI) agents when working in open-world physical environments. To develop and evaluate these agents, we need realistic and meaningful novelties, that is, novelties that are detectable and learnable. However, there is a lack of research in the area of creating novelties for AI agents in physical environments. Physics-based video games are popular among AI researchers due to the ability to create realistic and controllable physical environments. In this paper, we present a systematic novelty generation framework for physics-based video games. This framework allows the user to define a specific objective when generating novel content that ensures detectability. We instantiate the proposed framework for the video game Angry Birds and conduct experiments to show that the generated novel content is consistent with the user-defined objectives. Furthermore, we use a reinforcement learning agent to experiment with the learnability of the generated novel content.

Detecting, characterizing and adapting to novelty, whether in the form of previously unseen objects or phenomena, or unexpected changes in the behavior of known elements, is essential for Artificial Intelligence agents to operate reliably in unconstrained real-world environments. We propose an automatic, unsupervised approach to novelty characterization for dynamic domains, based on describing the behaviors and interactions of objects in terms of their possible actions. To abstract from the variety of realizations of an action that can occur in physical domains, we model states in terms of qualitative spatial relations (QSRs) between their entities. By first learning a model of actions in the non-novel environment from the state transitions observed as the agent interacts with the world, we can detect novelty by the persistent deviations from this model that it causes, and characterize the novelty by new or modified actions. We also present a new method of learning action models from observation, based on conceptual similarity and hierarchical clustering.

This paper presents a structure generation algorithm, which converts rough human drawings into stable structures comprising rectangular blocks, suitable for physics-based 2-D environments. Generating viable structures for a physics-based environment imposes many additional requirements above those of most traditional sketch-based domains. Our method is sophisticated enough to deal with these requirements, while still ensuring that the generated structure accurately represents the original sketch. We describe and implement a framework for this process, allowing inexperienced users to create complex structures with ease. Multiple structure possibilities are identified for a single drawing and are then compared based on their similarity to the original sketch using a heuristic value. We evaluate our approach by investigating its ability to replicate structures for the video game Angry Birds, based on human drawn sketches of the original levels.

This paper introduces an information-theoretic method for selecting a subset of problems which gives the most information about a group of problem-solving algorithms. This method was tested on the games in the General Video Game AI (GVGAI) framework, allowing us to identify a smaller set of games that still gives a large amount of information about the abilities of different game-playing agents. This approach can be used to make agent testing more efficient. We can achieve almost as good discriminatory accuracy when testing on only a handful of games as when testing on more than a hundred games, something which is often computationally infeasible. Furthermore, this method can be extended to study the dimensions of the effective variance in game design between these games, allowing us to identify which games differentiate between agents in the most complementary ways.

In this paper we present several proofs for the computational complexity of the physics-based video game Angry Birds. We are able to demonstrate that solving levels for different versions of Angry Birds is either NP-hard, PSPACE-hard, PSPACE-complete or EXPTIME-hard, depending on the maximum number of birds available and whether the game engine is deterministic or stochastic. We believe that this is the first time that a single-player video game has been proven EXPTIME-hard.

Over the past few years the Angry Birds AI competition has been held in an attempt to develop intelligent agents that can successfully and efficiently solve levels for the video game Angry Birds. Many different agents and strategies have been developed to solve the complex and challenging physical reasoning problems associated with such a game. However none of these agents attempt one of the key strategies which humans employ to solve Angry Birds levels, which is restarting levels. Restarting is important in Angry Birds because sometimes the level is no longer solvable or some given shot made has little to no benefit towards the ultimate goal of the game. This paper proposes a framework and experimental evaluation for when to restart levels in Angry Birds. We demonstrate that restarting is a viable strategy to improve agent performance in many cases.

GPS-based services (e.g. Google Maps) are very popular in our daily life, while there are still many GPS-denied environments (e.g. indoor and underground scenarios) in which they cannot be used. In these situations, localization and navigation are still important, for example in emergency evacuation or indoor navigation. In this paper we aim to solve the problem of localizing and navigating humans or robots in GPS-denied environments based on landmarks. Our work is inspired by human daily communications about localization and navigation, for example someone who has been to a shopping mall many times can localize and guide another person to get to a certain shop via conversations over the cellphone. Our goal is to build a system with the same capability. We propose a system that relies on qualitative information of places (e.g. the direction relations between landmarks involved in route descriptions), where localization can be achieved in an interactive manner and by analyzing observations provided by users. Our system decides the "best" route from one place to another by three factors: the number of landmarks; the number of ambiguous turns; and the qualitative distance (e.g. near and far). According to the experimental results, the number of requeries in the interactive localization process is acceptable and our route planning algorithm outperforms previous methods in several cases.

This paper presents an overview of the second AIBIRDS level generation competition, held jointly at the 2017 IEEE Conference on Computational Intelligence and Games and the 26th International Joint Conference on Artificial Intelligence. This competition tasked entrants with developing a level generator for the physics-based puzzle game Angry Birds. Submitted generators were required to deal with many physical reasoning constraints caused by the realistic nature of the game's environment, in addition to ensuring that the created levels were fun, challenging, and solvable. This year's competition was a significant improvement over the previous year, with a greater number of participants and more advanced generators. In this paper, we describe the framework, rules, submitted generators, and results for this competition. We also provide some background information on related research and other video game AI competitions and discuss what can be learned from this year's competition. There are several game and real-world applications for this type of research, and we provide some examples of the types of levels we would like future competition entries to generate.

Over the past few years the Angry Birds AI competition has been held in an attempt to develop intelligent agents that can successfully and efficiently solve levels for the video game Angry Birds. Many different agents and strategies have been proposed to solve the complex and challenging physical reasoning problems associated with such a game. The performance of these agents has increased significantly over the competition's lifetime thanks to the different approaches and improved techniques employed. However, there still exist key flaws within the designs of these agents that can often lead them to make illogical or very poor choices. Most of the current approaches try to identify the best or a good next shot, but do not attempt to plan an effective sequence of shots. While this might be due to the difficulty in predicting the exact outcome of a shot, this capability is precisely what is needed to succeed, both in games like Angry Birds, but also in the real world where physical reasoning capabilities are essential. In order to encourage development of such techniques, we can create levels where selecting a seemingly good next shot will lead to a worse outcome. In this paper we present several categories of deception to fool the current state-of-the-art agents. By evaluating the performance of the most recent Angry Birds agents on specific level examples that contain these deceptive elements, we can show how certain AI techniques can be tricked or exploited. We also propose some ways that future agents could help deal with these deceptive levels to increase their overall performance and generality.

The Angry Birds AI Competition (aibirds.org) has been held annually since 2012 in conjunction with some of the major AI conferences, most recently with IJCAI 2015. The goal of the competition is to build AI agents that can play new Angry Birds levels as good as or better than the best human players. Successful agents should be able to quickly analyze new levels and to predict physical consequences of possible actions in order to select actions that solve a given level with a high score. Agents have no access to the game internal physics, but only receive screenshots of the live game. In this paper we describe why this problem is a challenge for AI, and why it is an important step towards building AI that can successfully interact with the real world. We also summarise some highlights of past competitions, including a new competition track we introduced recently.

The capability of determining the right sequence of physical actions to achieve a given task is essential for AI that interacts with the physical world. The great difficulty in developing this capability has two main causes: (1) the world is continuous and therefore the action space is infinite, (2) due to noisy perception, we do not know the exact physical properties of our environment and therefore cannot precisely simulate the consequences of a physical action.

Many current computer vision approaches for object detection can only detect objects that have been learned in advance. In this paper, we present a method that uses qualitative stability analysis to infer the existence of unknown objects in certain areas of the images based on gravity and stability of already detected objects. Our method recursively searches these areas for unknown objects until all detected objects form a stable structure or no new objects can be identified anymore. We evaluate our method using the popular video game Angry Birds. We only start with detecting the green pigs and are able to automatically identify and detect all essential game objects in all 400+ available levels. All objects can be accurately and reliably detected. Our method can be applied to other video games where objects obey gravity and are bound by polygons.

The nine papers in this special section focus on the development of physics-based simulation video games (PBSG). The focus is on artificial intelligence for specific PBSGs competitions such as Angry Birds and computational pool, as well as on further developments of physics simulators in order to launch the next generation of PBSGs.

The Angry Birds AI Competition (aibirds.org) has been held in conjunction with the AI 2012, IJCAI 2013 and ECAI 2014 conferences and will be held again at the IJCAI 2015 conference. The declared goal of the competition is to build an AI agent that can play Angry Birds as good or better than the best human players. In this paper we describe why this is a very difficult problem, why it is a challenge for AI, and why it is an important step towards building AI that can successfully interact with the real world. We also summarise some highlights of past competitions, describe which methods were successful, and give an outlook to proposed variants of the competition.

Increasing the expressiveness of qualitative spatial calculi is an essential step towards meeting the requirements of applications. This can be achieved by combining existing calculi in a way that we can express spatial information using relations from multiple calculi. The great challenge is to develop reasoning algorithms that are correct and complete when reasoning over the combined information. Previous work has mainly studied cases where the interaction between the combined calculi was small, or where one of the two calculi was very simple. In this paper we tackle the important combination of topological and directional information for extended spatial objects. We combine some of the best known calculi in qualitative spatial reasoning, the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. We consider two different interpretations of the RCC8 algebra, one uses a weak connectedness relation, the other uses a strong connectedness relation. In both interpretations, we show that reasoning with topological and directional information is decidable and remains in NP. Our computational complexity results unveil the significant differences between RA and CDC, and that between weak and strong RCC8 models. Take the combination of basic RCC8 and basic CDC constraints as an example: we show that the consistency problem is in P only when we use the strong RCC8 algebra and explicitly know the corresponding basic RA constraints.

Route navigation is a widely studied subject from both cognitive and practical points of view. A particular aspect is the generation of (verbal) route instructions that are robust with respect to ambiguous verbal terms. Work in this area usually builds on counting the number of ambiguous turn options along a route. Simple graph search can then be used to derive a route whose description is the most fault-tolerant according to this measure.

The generation of route descriptions is a fundamental task of navigation systems. A particular problem in this context is to identify routes that can easily be described and processed by users. In this work, we present a framework for representing route n

The next challenge in qualitative spatial and temporal reasoning is to develop calculi that deal with different aspects of space and time. One approach to achieve this is to combine existing calculi that cover the different aspects. This, however, can lead to calculi that have a very large number of relations and it is a matter of ongoing discussions within the research community whether such large calculi are too large to be useful. In this paper we develop a procedure for reasoning about some of the largest known calculi, the Rectangle Algebra and the Block Algebra with about 10661 relations. We demonstrate that reasoning over these calculi is possible and can be done efficiently in many cases. This is a clear indication that one of the main goals of the field can be achieved: highly expressive spatial and temporal representations that support efficient reasoning.

Route navigation is one of the most widely used everyday application of spatial data. In this paper we investigate how a qualitative representation of route networks can be derived from map data and how this representation can be used to reason about route descriptions. We introduce a concept of route graph that provides an abstract layer on top of metric map data and thus allows for a compact representation of route information. We present selected queries and reasoning tasks that can be expressed in this abstraction layer.

This paper proposes an efficient, decentralized algorithm for determining the topological relationship between two regions monitored by a geosensor network. Many centralized algorithms already exist for this purpose (used for example in spatial databases). However, these algorithms are not suited to decentralized spatial computing environments, like geosensor networks, which must operate without global knowledge of the system state and without centralized control. Unlike many existing decentralized spatial algorithms, the proposed algorithm is also able to operate in the absence of information about a node's coordinate location. This makes the algorithm suitable for applications of geosensor networks where GPS or other positioning systems are unavailable or unreliable. The algorithm approach is founded on the well-known 4-intersection model, using in-network data aggregation and spatial filtering (involving nodes only at some region boundaries). This ensures only a relatively small proportion of the network is involved in computation, thus increasing efficiency. Our analysis shows that while the overall communication complexity of the algorithm is O(n), the load balancing is optimal leading to a constant O(1) communication complexity for individual nodes. This expectation is confirmed with empirical investigation using simulation, which demonstrates the practical efficiency of the algorithm.

An influential model of agent trust and experience is that of Jonker and Treur [Jonker and Treur 99]. In that model an agent uses its experience of the interactions of another agent to assess that agent's trustworthiness. We showed that key properties of that model are subsumed by classical mathematical systems theory. Using the latter theory we also clarify the issue of when two experience sequences may be regarded as equivalent. An intuitive feature of the Jonker and Treur model is that experience sequence orderings are respected by functions that map such sequences to trust orderings. We raise a question about another intuitive property — that of continuity of these functions, viz. that they map experience sequences that resemble each other to trust values that also resemble each other. Using fundamental results in the relationship between partial orders and topologies we also showed that these two intutive properties are essentially equivalent.

Constraint networks in qualitative spatial and temporal reasoning are always complete graphs. When one adds an extra element to a given network, previously unknown constraints are derived by intersections and compositions of other constraints, and this may introduce inconsistency to the overall network. Likewise, when combining two consistent networks that share a common part, the combined network may become inconsistent.

The theoretical properties of qualitative spatial reasoning in the RCC8 framework have been analyzed extensively. However, no empirical investigation has been made yet. Our experiments show that the adaption of the algorithms used for qualitative temporal reasoning can solve large RCC8 instances, even if they are in the phase transition region -- provided that one uses the maximal tractable subsets of RCC8 that have been identified by us. In particular, we demonstrate that the orthogonal combination of heuristic methods is successful in solving almost all apparently hard instances in the phase transition region up to a certain size in reasonable time.