Plan verification is the task of checking whether a proposed plan correctly solves a given planning problem. In Hierarchical Task Network (HTN) planning, this verification problem is known to be NP-hard. Existing approaches to HTN plan verification range from SAT encodings to parser-based techniques. However, existing methods do not explicitly exploit the temporal structure inherent in hierarchical decomposition. In this paper, we establish a formal connection between HTN planning and temporal reasoning by showing how decomposition structures can be naturally represented using qualitative constraint networks. Building on this insight, we present a new top-down encoding that transforms the verification of partially ordered task networks into a temporal reasoning problem. We prove the correctness of this encoding and explain how it accounts for both the hierarchical and temporal aspects of HTN plans. By linking HTN plan verification with qualitative temporal reasoning, our approach introduces a principled formal framework for reasoning about complex temporal relationships in hierarchical plans. This connection offers new perspectives for knowledge representation in structured planning domains.

Abductive expansion is an AGM-style belief-change operation that accommodates new information by adding explanatory hypotheses rather than incorporating the input outright. In contrast to belief sets, belief bases are finite and non-deductively closed, allowing a distinction between explicit and implicit beliefs. We extend abductive belief-change operations to belief bases relative to a hypothesis space, treating the base as firm beliefs and maintaining a separate space of tentative hypotheses that is conditioned on new inputs. Inspired by partial meet and kernel construction from classical belief revision, we provide concrete instances of three different types of abductive change: expansion, suspension (which corresponds to contraction), and revision. In the form of representation theorems, all these operators are shown to be characterized axiomatically by intuitive postulates. Along the constructions, counterparts of the well-known Levi identity and the Harper identity are exploited.

This paper is concerned with knowledge graph embedding with background knowledge, taking the formal perspective of logics. In knowledge graph embedding, knowledge— expressed as a set of triples of the form (a R b) (“a is R-related to b”)—is embedded into a real-valued vector space. The embedding helps exploiting geometrical regularities of the space in order to tackle typical inductive tasks of machine learning such as link prediction. Recent embedding approaches also consider incorporating background knowledge, in which the intended meanings of the symbols a, R, b are further constrained via axioms of a theory. Of particular interest are theories expressed in a formal language with a neat semantics and a good balance between expressivity and feasibility. In that case, the knowledge graph together with the background can be considered to be an ontology. This paper develops a cone-based theory for embedding in order to advance the expressivity of the ontology: it works (at least) with ontologies expressed in the description logic ALC, which comprises restricted existential and universal quantifiers, as well as concept negation and concept disjunction. In order to align the classical Tarskian Style semantics for ALC with the sub-symbolic representation of triples, we use the notion of a geometric model of an ALC ontology and show, as one of our main results, that an ALC ontology is satisfiable in the classical sense iff it is satisfiable by a geometric model based on cones. The geometric model, if treated as a partial model, can even be chosen to be faithful, i.e., to reflect all and only the knowledge captured by the ontology. We introduce the class of axis-aligned cones and show that modulo simple geometric operations any distributive logic (such as ALC) interpreted over cones employs this class of cones. Cones are also attractive from a machine learning perspective on knowledge graph embeddings since they give rise to applying conic optimization techniques.

Qualitative Constraint Networks (QCNs) comprise a Symbolic AI framework for representing and reasoning about spatial and temporal information via the use of disjunctive natural relations, e.g., a constraint can be of the form "Task A is scheduled after or during Task C". In this short paper, we make a comparison and evaluation with respect to prominent QCN-tackling heuristics in the literature, and reveal that there exists a trade-off between fast and robust solving of QCNs for a dataset of Allen’s Interval Algebra instances.

Qualitative Spatial & Temporal Reasoning (QSTR) is a major field of study in Symbolic AI that deals with the representation and reasoning of spatio- temporal information in an abstract, human-like manner. We survey the current status of QSTR from a viewpoint of reasoning approaches, and identify certain future challenges that we think that, once overcome, will allow the field to meet the demands of and adapt to real-world, dynamic, and time-critical applications of highly active areas such as machine learning and data mining.

This paper presents an embedding of ontologies expressed in the ALC description logic into a real-valued vector space, comprising restricted existential and universal quantifiers, as well as concept negation and concept disjunction. Our main result states that an ALC ontology is satisfiable in the classical sense iff it is satisfiable by a partial faithful geometric model based on cones. The line of work to which we contribute aims to integrate knowledge representation techniques and machine learning. The new cone-model of ALC proposed in this work gives rise to conic optimization techniques for machine learning, extending previous approaches by its ability to model full ALC.

We introduce and evaluate dynamic branching strategies for solving Qualitative Constraint Networks (QCNs), which are networks that are mostly used to represent and reason about spatial and temporal information via the use of simple qualitative relations, e.g., a constraint can be "Task A is scheduled after or during Task C". In qualitative constraint-based reasoning, the state-of-the-art approach to tackle a given QCN consists in employing a backtracking algorithm, where the branching decisions during search are governed by the restrictiveness of the possible relations for a given constraint (e.g., after can be more restrictive than during). In the literature, that restrictiveness is defined a priori by means of static weights that are precomputed and associated with the relations of a given calculus, without any regard to the particulars of a given network instance of that calculus, such as its structure. In this paper, we address this limitation by proposing heuristics that dynamically associate a weight with a relation, based on the count of local models (or local scenarios) that the relation is involved with in a given QCN; these models are local in that they focus on triples of variables instead of the entire QCN. Therefore, our approach is adaptive and seeks to make branching decisions that preserve most of the solutions by determining what proportion of local solutions agree with that decision. Experimental results with a random and a structured dataset of QCNs of Interval Algebra show that it is possible to achieve up to 5 times better performance for structured instances, whilst maintaining non-negligible gains of around 20% for random ones.

This paper reviews formal approaches to representing spatial knowledge about qualitative direction. Unlike geometric direction information, qualitative information does not employ numerical values but relies on comparison. The qualitative approach is often regarded as suitable for capturing commonsense concepts and thus is relevant to human-centered interfaces for spatial information systems. To establish a context for the work on qualitative direction, we preset a brief history of the development of qualitative temporal and spatial representations from different scientific perspectives. We identify main focal areas of these representations of spatial direction and propose a taxonomy. In the light of more than three decades of fruitful research, we obtain a map of formal representations that reveal interrelationships between different research strands in the field.

In this paper, we present a system for effective referential human–robot communication in the face of perceptual deviation using the Probabilistic Reference And GRounding mechanism PRAGR and vague feature models based on prototypes. PRAGR can handle descriptions of arbitrary complexity including spatial relations and uses flexible concept assignment in generation and resolution of referring expressions for bridging conceptual gaps in referential robot–robot or human–robot interaction. We evaluate the benefit of using vague as compared to crisp properties regarding referential success and robustness towards perspective alignment error in referential robot–robot and human–robot communication.

This paper explores the use of generalized linear programming techniques to tackle two long-standing problems in qualitative spatio-temporal reasoning: Using LP as a unifying basis for reasoning, one can jointly reason about relations from different qualitative calculi. Also, concrete entities (fixed points, regions fixed in shape and/or position, etc.) can be mixed with free variables. Both features are important for applications but cannot be handled by existing techniques. In this paper we discuss properties of encoding constraint problems involving spatial and temporal relations. We advocate the use of AND/OR graphs to facilitate efficient reasoning and we show feasibility of our approach.

Next to authoritative spatial representations stemming from surveying and cartography efforts, there have always been spatial representations produced by laypeople which often come in a non-georeferenced form, such as sketch maps or verbal descriptions. With the advent of volunteered geographic information the amount and accessibility of such information increased drastically. This results in issues of ambiguity (not knowing what is depicted) and trust (not knowing whether the provided information is correct). To process this kind of information, matching approaches for establishing the correct correspondences between multiple representations are needed. As typically only qualitative relations are preserved in sketched information, performing the matching on a qualitative level has been suggested, but efficient solutions that are able to handle the involved combinatorial explosion of matching hypotheses are still lacking. We address this problem by developing a matching approach that exploits qualitative spatial reasoning to prune the search space while performing a heuristic search through the tree of possible matching hypotheses. The developed approach is general in that it can be employed for different tasks and problem domains, such as data integration and retrieval. In a case-study we apply it to the task of matching a sketch map to a geo-referenced data set.

The purpose of this paper is to present a technique to create a global map of robots' surroundings by converting the raw data acquired from a scanning sensor to a compact map composed of just a few generalized polylines (polygonal curves). We propose a new approach to merging robots' maps that is composed of a local geometric process of merging similar line segments (termed discrete segment evolution) with a global statistical control process. In the case of single robot, we are able to incrementally build a map showing the environment the robot has traveled through by merging its polygonal map with actual scans. In the case of a robot team, we are able to identify common parts of their partial maps and if common parts are present construct a joint map of the explored environment.