Jochen Renz

IJCAI Conference 2025 Conference Paper

NovPhy: A Physical Reasoning Benchmark for Open-World AI Systems Author Links Open Overlay Panel (Abstract Reprint)

• Vimukthini Pinto
• Chathura Gamage
• Cheng Xue
• Peng Zhang
• Ekaterina Nikonova
• Matthew Stephenson
• Jochen Renz

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

AIJ Journal 2024 Journal Article

NovPhy: A physical reasoning benchmark for open-world AI systems

• Vimukthini Pinto
• Chathura Gamage
• Cheng Xue
• Peng Zhang
• Ekaterina Nikonova
• Matthew Stephenson
• Jochen Renz

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.

AAAI Conference 2022 Conference Paper

Towards Explainable Action Recognition by Salient Qualitative Spatial Object Relation Chains

• Hua Hua
• Dongxu Li
• Ruiqi Li
• Peng Zhang
• Jochen Renz
• Anthony Cohn

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, learningbased 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 explainability.

KR Conference 2021 Conference Paper

Unsupervised Novelty Characterization in Physical Environments Using Qualitative Spatial Relations

• Ruiqi Li
• Hua Hua
• Patrik Haslum
• Jochen Renz

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.

AIJ Journal 2020 Journal Article

The computational complexity of Angry Birds

• Matthew Stephenson
• Jochen Renz
• XiaoYu Ge

The physics-based simulation game Angry Birds has been heavily researched by the AI community over the past five years, and has been the subject of a popular AI competition that is currently held annually as part of a leading AI conference. Developing intelligent agents that can play this game effectively has been an incredibly complex and challenging problem for traditional AI techniques to solve, even though the game is simple enough that any human player could learn and master it within a short time. In this paper we analyse how hard the problem really is, presenting several proofs for the computational complexity of Angry Birds. By using a combination of several gadgets within this game's environment, we are able to demonstrate that the decision problem of solving general levels for different versions of Angry Birds is either NP-hard, PSPACE-hard, PSPACE-complete or EXPTIME-hard. Proof of NP-hardness is by reduction from 3-SAT, whilst proof of PSPACE-hardness is by reduction from True Quantified Boolean Formula (TQBF). Proof of EXPTIME-hardness is by reduction from G2, a known EXPTIME-complete problem similar to that used for many previous games such as Chess, Go and Checkers. To the best of our knowledge, this is the first time that a single-player game has been proven EXPTIME-hard. This is achieved by using stochastic game engine dynamics to effectively model the real world, or in our case the physics simulator, as the opponent against which we are playing. These proofs can also be extended to other physics-based games with similar mechanics.

IJCAI Conference 2020 Conference Paper

The Computational Complexity of Angry Birds (Extended Abstract)

• Matthew Stephenson
• Jochen Renz
• XiaoYu Ge

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.

KR Conference 2018 Conference Paper

Qualitative Representation and Reasoning over Direction Relations across Different Frame of References

• Hua Hua
• Jochen Renz
• XiaoYu Ge

KR Conference 2018 Short Paper

Towards Explainable Inference about Object Motion using Qualitative Reasoning

• XiaoYu Ge
• Jochen Renz
• Hua Hua

The capability of making explainable inferences regarding physical processes has long been desired. One fundamental physical process is object motion. Inferring what causes the motion of a group of objects can even be a challenging task for experts, e. g. , in forensic science. Most of the work in the literature rely on physics simulation to draw such inferences. The simulation requires a precise model of the underlying domain to work well and is essentially a black-box from which one can hardly obtain any useful explanation. By contrast, qualitative reasoning methods have the advantage in making transparent inferences with ambiguous information, which makes it suitable for this task. However, there has been no suitable qualitative theory proposed for object motion in three-dimensional space. We take this challenge and develop a qualitative theory for the motion of rigid objects. Based on this theory, we develop a reasoning method to solve a very interesting problem: Assuming there are several objects that were initially at rest and now have started to move. We want to infer what action causes the movement of these objects.

AAAI Conference 2016 Conference Paper

Angry Birds as a Challenge for Artificial Intelligence

• Jochen Renz
• XiaoYu Ge
• Rohan Verma
• Peng Zhang

The Angry Birds AI Competition1 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.

ECAI Conference 2016 Conference Paper

Hole in One: Using Qualitative Reasoning for Solving Hard Physical Puzzle Problems

• Xiaoyu Ge
• Jae Hee Lee 0001
• Jochen Renz
• Peng Zhang 0021

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.

IJCAI Conference 2016 Conference Paper

Trend-Based Prediction of Spatial Change

• XiaoYu Ge
• Jae Hee Lee
• Jochen Renz
• Peng Zhang

The capability to predict changes of spatial regions is important for an intelligent system that interacts with the physical world. For example, in a disaster management scenario, predicting potentially endangered areas and inferring safe zones is essential for planning evacuations and countermeasures. Existing approaches usually predict such spatial changes by simulating the physical world based on specific models. Thus, these simulation-based methods will not be able to provide reliable predictions when the scenario is not similar to any of the models in use or when the input parameters are incomplete. In this paper, we present a prediction approach that overcomes the aforementioned problem by using a more general model and by analysing the trend of the spatial changes. The method is also flexible to adopt to new observations and to adapt its prediction to new situations.

AAAI Conference 2015 Conference Paper

AIBIRDS: The Angry Birds Artificial Intelligence Competition

• Jochen Renz

IJCAI Conference 2015 Conference Paper

From Raw Sensor Data to Detailed Spatial Knowledge

• Peng Zhang
• Jae Hee Lee
• Jochen Renz

Qualitative spatial reasoning deals with relational spatial knowledge and with how this knowledge can be processed efficiently. Identifying suitable representations for spatial knowledge and checking whether the given knowledge is consistent has been the main research focus in the past two decades. However, where the spatial information comes from, what kind of information can be obtained and how it can be obtained has been largely ignored. This paper is an attempt to start filling this gap. We present a method for extracting detailed spatial information from sensor measurements of regions. We analyse how different sparse sensor measurements can be integrated and what spatial information can be extracted from sensor measurements. Different from previous approaches to qualitative spatial reasoning, our method allows us to obtain detailed information about the internal structure of regions. The result has practical implications, for example, in disaster management scenarios, which include identifying the safe zones in bushfire and flood regions.

KR Conference 2014 Conference Paper

Qualitative Spatial Representation and Reasoning in Angry Bird: the Extended Rectangle Algebra

• Peng Zhang
• Jochen Renz

AIJ Journal 2013 Journal Article

Decomposition and tractability in qualitative spatial and temporal reasoning

• Jinbo Huang
• Jason Jingshi Li
• Jochen Renz

Constraint networks in qualitative spatial and temporal reasoning (QSTR) typically feature variables defined on infinite domains. Mainstream algorithms for deciding network consistency are based on searching for network refinements whose consistency is known to be tractable, either directly or by using a SAT solver. Consequently, these algorithms treat all networks effectively as complete graphs, and are not directly amenable to complexity bounds based on network structure, such as measured by treewidth, that are well known in the finite-domain case. The present paper makes two major contributions, spanning both theory and practice. First, we identify a sufficient condition under which consistency can be decided in polynomial time for networks of bounded treewidth in QSTR, and show that this condition is satisfied by a range of calculi including the Interval Algebra, Rectangle Algebra, Block Algebra, RCC8, and RCC5. Second, we apply the techniques used in establishing these results to a SAT encoding of QSTR, and obtain a new, more compact encoding which is also guaranteed to be solvable in polynomial time for networks of bounded treewidth, and which leads to a significant advance of the state of the art in solving the hardest benchmark problems.

IJCAI Conference 2013 Conference Paper

Efficient Extraction and Representation of Spatial Information from Video Data

• Hajar Sadeghi Sokeh
• Stephen Gould
• Jochen Renz

Vast amounts of video data are available on the web and are being generated daily using surveillance cameras or other sources. Being able to efficiently analyse and process this data is essential for a number of different applications. We want to be able to efficiently detect activities in these videos or be able to extract and store essential information contained in these videos for future use and easy search and access. Cohn et al. (2012) proposed a comprehensive representation of spatial features that can be efficiently extracted from video and used for these purposes. In this paper, we present a modified version of this approach that is equally efficient and allows us to extract spatial information with much higher accuracy than previously possible. We present efficient algorithms both for extracting and storing spatial information from video, as well as for processing this information in order to obtain useful spatial features. We evaluate our approach and demonstrate that the extracted spatial information is considerably more accurate than that obtained from existing approaches.

IJCAI Conference 2013 Conference Paper

Representation and Reasoning about General Solid Rectangles

• XiaoYu Ge
• Jochen Renz

Entities in two-dimensional space are often approximated using rectangles that are parallel to the two axes that define the space, so-called minimumbounding rectangles (MBRs). MBRs are popular in Computer Vision and other areas as they are easy to obtain and easy to represent. In the area of Qualitative Spatial Reasoning, many different spatial representations are based on MBRs. Surprisingly, there has been no such representation proposed for general rectangles, i. e. , rectangles that can have any angle, nor for general solid rectangles (GSRs) that cannot penetrate each other. GSRs are often used in computer graphics and computer games, such as Angry Birds, where they form the building blocks of more complicated structures. In order to represent and reason about these structures, we need a spatial representation that allows us to use GSRs as the basic spatial entities. In this paper we develop and analyze a qualitative spatial representation for GSRs. We apply our representation and the corresponding reasoning methods to solve a very interesting practical problem: Assuming we want to detect GSRs in computer games, but computer vision can only detect MBRs. How can we infer the GSRs from the given MBRs? We evaluate our solution and test its usefulness in a real gaming scenario.

IJCAI Conference 2013 Conference Paper

StarVars—Effective Reasoning about Relative Directions

• Jae Hee Lee
• Jochen Renz
• Diedrich Wolter

Relative direction information is very commonly used. Observers typically describe their environment by specifying the relative directions in which they see other objects or other people from their point of view. Or they receive navigation instructions with respect to their point of view, for example, turn left at the next intersection. However, it is surprisingly hard to integrate relative direction information obtained from different observers, and to reconstruct a model of the environment or the locations of the observers based on this information. Despite intensive research, there is currently no algorithm that can effectively integrate this information: this problem is NP-hard, but not known to be in NP, even if we only use left and right relations. In this paper we present a novel qualitative representation, StarVars, that can solve these problems. It is an extension of the STAR calculus [Renz and Mitra, 2004]) by a VARiable interpretation of the orientation of observers. We show that reasoning in StarVars is in NP and present the first algorithm that allows us to effectively integrate relative direction information from different observers.

KR Conference 2012 Conference Paper

Implicit Constraints for Qualitative Spatial and Temporal Reasoning

• Jochen Renz

Qualitative information about spatial or temporal entities is represented by specifying qualitative relations between these entities. It is then possible to apply qualitative reasoning methods for tasks such as checking consistency of the given information, deriving previously unknown information or answering queries. Depending on the kind of information that is represented, qualitative reasoning methods might lead to incorrect results, and it is a topic of ongoing research efforts to determine when and why this occurs. In this paper we present two possible explanations for this behaviour: (1) the existence of implicit entities that we do not explicitly represent; (2) the existence of implicit constraints that have to be satisfied, but which are not explicitly represented. We show that both of these can lead to undetected inconsistencies. By making these implicit entities and constraints explicit, and by including them in the qualitative representation, we are able to solve problems that could not be solved qualitatively before. We present different examples of implicit entities and implicit constraints and an algorithm for solving them. 3. We determine the converse relation of each base relation and the composition ◦ between any pair of base relations (defined as R ◦ S = {(x, z)|∃y: (x, y) ∈ R and (y, z) ∈ S}), and only accept sets of base relations for which their powerset 2B is closed under composition, intersection, union and converse of relations. Using these relations, spatial and temporal information can be represented qualitatively by specifying a set Θ of constraints of the form xRy, where x, y are variables over D and R ∈ 2B. Taking relations of 2B instead of only relations of B allows us to specify indefinite information as a union of possible base relations when it is not known which one holds. The most common reasoning problem is to determine consistency of Θ, i. e., decide whether there is an instantiation of each variable with values from D such that all constraints are satisfied. Qualitative reasoning can then be done by applying the so-called path-consistency operation (Mackworth 1977), which takes a triple of variables x, y, z and their constraints xRy, ySz, xT z ∈ Θ and replaces xT z with the new constraint x(R ◦ S) ∩ T z. This operation removes base relations that cannot hold between x and z. If we remove all base relations of a constraint, then Θ is inconsistent. Otherwise, we apply this operation to all triples of Θ repeatedly until no base relations are removed any more, in which case the resulting set Θ0 is path-consistent. The limit of the path-consistency operation is reached when all constraints consist of only one base relation. We call this an atomic set of constraints. If there are still constraints with multiple base relations left, we can try pathconsistency again by selecting each of the base relations separately. 3 This is usually done in a backtracking manner for

KR Conference 2012 Short Paper

Thinking inside the box: A comprehensive spatial representation for video analysis

• Anthony G. Cohn
• Jochen Renz
• Muralikrishna Sridhar

Y eb y4 0 B Successful analysis of video data requires an integration of techniques from KR, Computer Vision, and Machine Learning. Being able to detect and to track objects as well as extracting their changing spatial relations with other objects is one approach to describing and detecting events. Different kinds of spatial relations are important, including topology, direction, size, and distance between objects as well as changes of those relations over time. Typically these kinds of relations are treated separately, which makes it difficult to integrate all the extracted spatial information. We present a uniform and comprehensive spatial representation of moving objects that includes all the above spatial/temporal aspects, analyse different properties of this representation and demonstrate that it is suitable for video analysis. ea’ A sb’ y2 sa’ B core3, 3 A A A B B core3, 2 A 0 core1, 1 core3, 1 x1 x3 core1, 2 y1 B core1, 3 y3 X sa ea sb eb X x2 x4 Figure 1: Two rectangles A and B and their projections (left). How the projections define the 9 cores (right). tegrated calculus, and a loose combination of separate ones; however in the latter case there can be representational inefficiencies due to overlapping aspects of the calculi, which can also cause issues for inference, in particular detecting inconsistencies (Gerevini and Renz 2002). Since a common representation of objects in video analysis is to use their minimum bounding rectangles (MBR)(de Campos et al. 2011; Thirde et al. 2007), rather than a more precise shape representation (although these are also used), we focus here on an integrated spatio-temporal representation for such rectangular regions. The fact that all regions are one-piece, rectangular, and aligned to the spatial axes, allows a number of representational efficiencies to be made.

IJCAI Conference 2011 Conference Paper

On Qualitative Route Descriptions: Representation and Computational Complexity

• Matthias Westphal
• Stefan W
• ouml; lfl
• Bernhard Nebel
• Jochen Renz

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 networks with the qualitative information necessary to evaluate and optimize route descriptions with regard to ambiguities in them. We identify different agent models that differ in how agents are assumed to process route descriptions while navigating through route networks. Further, we analyze the computational complexity of matching route descriptions and paths in route networks in dependency of the agent model. Finally we empirically evaluate the influence of the agent model on the optimization and the processing of route instructions.

ECAI Conference 2010 Conference Paper

A Qualitative Representation of Route Networks

• Jochen Renz
• Stefan Wölfl 0001

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.

AAAI Conference 2010 Conference Paper

In Defense of Large Qualitative Calculi

• Jason Li
• Jochen Renz

IJCAI Conference 2009 Conference Paper

• Bernhard Nebel
• Jochen Renz

Calendar management tools assist users with coordinating their daily life. Different tasks have to be scheduled according to the user preferences. In many cases, tasks are at different locations and travel times have to be considered. Therefore, these kinds of calendar management problems can be regarded as spatio-temporal optimisation problems and are often variants of traveling salesman problems (TSP) or vehicle routing problems. While standard TSPs require a solution to include all tasks, prize-collecting TSPs are more suited for calendar management problems as they require a solution that optimises the total sum of “prizes” we assigned to tasks at different locations. If we now add time windows that limit when tasks can occur, these prize-collecting TSPs with time windows (TW-TSP) are excellent abstractions of spatio-temporal optimisation problems such as calendar management. Due to the inherent complexity of TW-TSPs, the existing literature considers mainly approximation algorithms or special cases. We present a novel algorithm for TW-TSPs that enables us to find the optimal solution to TW-TSP problems occurring in real-world calendar management applications efficiently. Our algorithm is a fixed-parameter tractable algorithm that depends on the maximal number of tasks that can be revisited from some other task, a parameter which is small in the application scenario we consider.

IJCAI Conference 2009 Conference Paper

• Weiming Liu
• Sanjiang Li
• Jochen Renz

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 both 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 (QSR), the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. Although CDC is more expressive than RA, reasoning with CDC is of the same order as reasoning with RA. We show that reasoning with basic RCC8 and basic RA relations is in P, but reasoning with basic RCC8 and basic CDC relations is NP-Complete.

IJCAI Conference 2009 Conference Paper

• Jason Jingshi Li
• Jinbo Huang
• Jochen Renz

Deciding consistency of constraint networks is a fundamental problem in qualitative spatial and temporal reasoning. In this paper we introduce a divide-and-conquer method that recursively partitions a given problem into smaller sub-problems in deciding consistency. We identify a key theoretical property of a qualitative calculus that ensures the soundness and completeness of this method, and show that it is satisfied by the Interval Algebra (IA) and the Point Algebra (PA). We develop a new encoding scheme for IA networks based on a combination of our divide-and-conquer method with an existing encoding of IA networks into SAT. We empirically show that our new encoding scheme scales to much larger problems and exhibits a consistent and significant improvement in efficiency over state-of-the-art solvers on the most difficult instances.

KR Conference 2008 Conference Paper

Automated Complexity Proofs for Qualitative Spatial and Temporal Calculi

• Jochen Renz
• Jason Jingshi Li

Identifying complexity results for qualitative spatial or temporal calculi has been an important research topic in the past 15 years. Most interesting calculi have been shown to be at least NP-complete, but if tractable fragments of the calculi can be found then efficient reasoning with these calculi is possible. In order to get the most efficient reasoning algorithms, we are interested in identifying maximal tractable fragments of a calculus (tractable fragments such that any extension of the fragment leads to NP-hardness). All required complexity proofs are usually made manually, sometimes using computer assisted enumerations. In a recent paper by Renz (2007), a procedure was presented that automatically identifies tractable fragments of a calculus. In this paper we present an efficient procedure for automatically generating NP-hardness proofs. In order to prove correctness of our procedure, we develop a novel proof method that can be checked automatically and that can be applied to arbitrary spatial and temporal calculi. Up to now, this was believed to be impossible. By combining the two procedures, it is now possible to identify maximal tractable fragments of qualitative spatial and temporal calculi fully automatically.

ECAI Conference 2008 Conference Paper

Combining binary constraint networks in qualitative reasoning

• Jason Jingshi Li
• Tomasz Kowalski
• Jochen Renz
• Sanjiang Li

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.

ECAI Conference 2008 Conference Paper

Experience and Trust - A Systems-Theoretic Approach

• Norman Foo
• Jochen Renz

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.

IJCAI Conference 2007 Conference Paper

• Jochen Renz

In the past years a lot of research effort has been put into finding tractable subsets of spatial and temporal calculi. It has been shown empirically that large tractable subsets of these calculi not only provide efficient algorithms for reasoning problems that can be expressed with relations contained in the tractable subsets, but also surprisingly efficient solutions to the general, NP-hard reasoning problems of the full calculi. An important step in this direction was the refinement algorithm which provides a heuristic for proving tractability of given subsets of relations. In this paper we extend the refinement algorithm and present a procedure which identifies large tractable subsets of spatial and temporal calculi automatically without any manual intervention and without the need for additional NP-hardness proofs. While we can only guarantee tractability of the resulting sets, our experiments show that for RCC8 and the Interval Algebra, our procedure automatically identifies all maximal tractable subsets. Using our procedure, other researchers and practitioners can automatically develop efficient reasoning algorithms for their spatial or temporal calculi without any theoretical knowledge about how to formally analyse these calculi.

ECAI Conference 2004 Conference Paper

Problems with Local Consistency for Qualitative Calculi

• Gérard Ligozat
• Jochen Renz

AIJ Journal 2002 Journal Article

Combining topological and size information for spatial reasoning

• Alfonso Gerevini
• Jochen Renz

Information about the size of spatial regions is often easily accessible and, when combined with other types of spatial information, it can be practically very useful. In this paper we introduce four classes of qualitative and metric size constraints, and we study their integration with the Region Connection Calculus RCC-8, a well-known approach to qualitative spatial reasoning with topological relations. We propose a new path-consistency algorithm for combining RCC-8 relations and qualitative size relations. The algorithm is complete for deciding satisfiability of an input set of topological constraints over one of the three maximal tractable subclasses of RCC-8 containing all the basic relations. Moreover, its time complexity is cubic and is the same as the complexity of the best-known method for deciding satisfiability when only these topological relations are considered. We also provide results on finding a consistent scenario in cubic time for these combined classes. Regarding metric size constraints, we first study their combination with RCC-8 and we show that deciding satisfiability for the combined sets of constraints is NP-hard, even when only the RCC-8 basic relations are used. Then we introduce RCC-7, a subalgebra of RCC-8 that can be used for applications where spatial regions cannot partially overlap. We show that reasoning with the seven RCC-7 basic relations and the universal relation is intractable, but that reasoning with the RCC-7 basic relations combined with metric size information is tractable. Finally, we give a polynomial algorithm for the latter case and a backtracking algorithm for the general case.

AIJ Journal 2002 Journal Article

Disjunctions, independence, refinements

• Mathias Broxvall
• Peter Jonsson
• Jochen Renz

An important question in constraint satisfaction is how to restrict the problem to ensure tractability (since the general problem is NP-hard). The use of disjunctions has proven to be a useful method for constructing tractable constraint classes from existing classes; the well-known ‘max-closed’ and ‘ORD-Horn’ constraints are examples of tractable classes that can be constructed this way. Three sufficient conditions (the guaranteed satisfaction property, 1-independence and 2-independence) that each ensure the tractability of constraints combined by disjunctions have been proposed in the literature. We show that these conditions are both necessary and sufficient for tractability in three different natural classes of disjunctive constraints. This suggests that deciding this kind of property is a very important task when dealing with disjunctive constraints. We provide a simple, automatic method for checking the 1-independence property—this method is applicable whenever the consistency of the constraints under consideration can be decided by path-consistency. Our method builds on a connection between independence and refinements (which is a way of reducing one constraint satisfaction problem to another.)

ECAI Conference 2000 Conference Paper

Qualitative Spatial Reasoning about Line Segments

• Reinhard Moratz
• Jochen Renz
• Diedrich Wolter

IJCAI Conference 1999 Conference Paper

Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis

• Jochen Renz

We present a general method for proving tractability of reasoning over disjunctions of jointly exhaustive and pairwise disjoint relations. Examples of these kinds of relations are Allen's temporal interval relations and their spatial counterpart, the R. CC8 relations by Randell, Cui, and Colin. Applying this method does not require detailed knowledge about the considered relations; instead, it is rather sufficient to have a subset of the considered set of relations for which path-consistency is known to decide consistency. Using this method, we give a complete classification of tractability of reasoning over RCC8 by identifying two large new maximal tractable subsets and show that these two subsets together with 'H8, the already known maximal tractable subset, are the only such sets for RCC8 that contain all base relations. We also apply our method to Allen's interval algebra and derive the known maximal tractable subset.

AIJ Journal 1999 Journal Article

On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus

• Jochen Renz
• Bernhard Nebel

The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question of the boundary between polynomial and NP-hard reasoning problems has not been addressed yet. In this paper we explore this boundary in the “Region Connection Calculus” RCC-8. We extend Bennett's encoding of RCC-8 in modal logic. Based on this encoding, we prove that reasoning is NP-complete in general and identify a maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we show that for this subset path-consistency is sufficient for deciding consistency.

ECAI Conference 1998 Conference Paper

Efficient Algorithms for Qualitative Spatial Reasoning

• Jochen Renz
• Bernhard Nebel