Dr. Stefan Wölfl - Publications
(Show all abstracts)
(Hide all abstracts)
2020
-
Bernhard Nebel and Stefan Wölfl.
Wissensrepräsentation und -verarbeitung.
In
Günther Görz, Ute Schmid and Tanya Braun (eds.),
Handbuch der Künstlichen Intelligenz, 6. Auflage, pp. 27-56.
De Gruyter 2020.
(Online; DOI)
2016
-
Matthias Hengel, Stefan Wölfl and Bernhard Nebel.
Reasoning about general TBoxes with spatial and temporal constraints: Implementation and optimizations.
In
Proceedings of the 29th International Workshop on Description Logics (DL 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
In many applications a reasonable representation of conceptual
knowledge requires the possibility to express spatial or temporal
relations between domain entities. A feasible approach to this is to
consider spatial or temporal constraint systems on concrete domains.
Indeed, Lutz and Milicic (2007) showed that for the description logic
ALC(C) with ω-admissible constraint systems, concept satsifiability
with respect to general TBoxes can be decided by an extension of a
standard ALC tableau algorithm. In this paper we report on a study in
which this tableau method was implemented, optimized, and evaluated.
2015
-
Matthias Westphal, Stefan Wölfl, Bernhard Nebel and Jochen Renz.
On qualitative route descriptions: Representation, agent models, and computational complexity.
Journal of Philosophical Logic 44 (2), pp. 177-201. 2015.
(Show abstract)
(Hide abstract)
(Online; DOI)
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 and discuss which
agent models can be translated into PDL programs. 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.
2014
-
Julien Hué, Matthias Westphal and Stefan Wölfl.
Towards a new semantic for Possibilistic Answer Sets.
In
Proceedings of Advances in Artificial Intelligence (KI'14).
2014.
(Show abstract)
(Hide abstract)
(Springer Online; DOI)
(DBLP)
Possibilistic Answer Set Programming is an extension of the standard ASP
framework that allows for attaching degrees of certainty to the rules in
ASP programs. In the literature, several semantics for such PASP-programs
have been presented, each of them having particular strengths and
weaknesses.
In this work we present a new semantics that employs so-called
iota-answer sets, a solution concept introduced by Gebser et al.~(2009), in
order to find solutions for standard ASP programs with odd cycles or
auto-blocking rules. This is achieved by considering maximal subsets of a
given ASP program for which answer sets exist. The main idea of our work is
to integrate iota-semantics into the possibilistic framework in such a way
that degrees of certainty are not only assigned to atoms mentioned in
the answer sets, but also to the answer sets themselves.
Our approach gives more satisfactory solutions and avoids
counter-intuitive examples arising in the other approaches.
We compare our approach to existing ones and present a translation into the
standard ASP framework allowing the computation of solutions by existing
tools.
-
Matthias Westphal, Julien Hué and Stefan Wölfl.
On the scope of Qualitative Constraint Calculi.
In
Proceedings of Advances in Artificial Intelligence (KI'14).
2014.
(Show abstract)
(Hide abstract)
(Springer Online; DOI)
(DBLP)
Qualitative constraint calculi are a special kind of relation algebras
defined by Ligozat and Renz for reasoning about binary constraints.
Although this approach is known to be limited it has prevailed in the
area of qualitative spatial and temporal reasoning.
In this paper we revisit the definition of these calculi, contrast it
with alternative approaches, and analyze general properties. Our
results indicate that the concept of qualitative constraint calculi is
both too narrow and too general: it disallows different approaches, but
its setup already enables arbitrarily hard problems.
-
Bernhard Nebel and Stefan Wölfl.
Wissensrepräsentation und -verarbeitung.
In
Günther Görz, Josef Schneeberger and Ute Schmid (eds.),
Handbuch der Künstlichen Intelligenz, pp. 105-128.
Oldenbourg Verlag München 2014.
2013
-
Matthias Westphal, Julien Hué, Stefan Wölfl and Bernhard Nebel.
Transition Constraints: A Study on the Computational Complexity of Qualitative Change.
In
Proceedings of International Joint Conference on Artificial Intelligence (IJCAI'13), pp. 1169-1175.
2013.
(Show abstract)
(Hide abstract)
(Online; PDF)
(DBLP)
Many formalisms discussed in the literature on
qualitative spatial reasoning are designed for expressing static spatial constraints only. However,
dynamic situations arise in virtually all applications
of these formalisms, which makes it necessary to
study variants and extensions involving change.
This paper presents a study on the computational
complexity of qualitative change. More precisely,
we discuss the reasoning task of finding a solution to a temporal sequence of static reasoning
problems where this sequence is subject to additional transition constraints. Our focus is primarily on smoothness and continuity constraints: we
show how such transitions can be defined as relations and expressed within qualitative constraint
formalisms. Our results demonstrate that for point-based constraint formalisms the interesting fragments become NP-complete in the presence of continuity constraints, even if the satisfiability problem
of its static descriptions is tractable.
-
Matthias Westphal, Julien Hué and Stefan Wölfl.
On the Propagation Strength of SAT Encodings for Qualitative Temporal Reasoning.
In
Proceedings of International Conference on Tools for Artificial Intelligence (ICTAI'13).
2013.
(Show abstract)
(Hide abstract)
(PDF)
(DOI)
(DBLP)
(Translation Script; TAR.GZ)
Several studies in Qualitative Spatial and Temporal Reasoning
discuss translations of the satisfiability problem on qualitative
constraint languages into propositional SAT.
Most of these encodings focus on compactness, while propagation strength
is seldom discussed.
In this work, we focus on temporal reasoning with the Point Algebra and
Allen's
Interval Algebra.
We understand all encodings as a combination of propagation and
search.
We first give a systematic analysis of existing propagation approaches
for these constraint languages.
They are studied and ordered with respect to their propagation strength
and refutation completeness for classes of input instances.
Secondly, we discuss how existing encodings can be derived from
such propagation approaches.
We conclude our work with an empirical evaluation which shows that the
older
ORD-encoding by Nebel and Bürckert performs better than more recently suggested encodings.
2012
-
Julien Hué, Matthias Westphal and Stefan Wölfl.
An automatic decomposition method for qualitative spatial and temporal reasoning.
In
International Conference on Tools for Artificial Intelligence (ICTAI), pp. 588-595.
2012.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
Qualitative spatial and temporal reasoning is a
research field that studies relational, constraint-based formalisms
for representing, and reasoning about, spatial and temporal
information. The standard approach for checking consistency is
based on an exhaustive representation of possible configurations
between three entities, the so-called composition tables. These
tables, however, encode semantic background knowledge in a
redundant way, which becomes a size and efficiency issue, when
the composition table needs to be grounded as done in SAT
encodings of problem instances. In this paper, we present a
new framework that allows for decomposing composition tables
into logically simpler parts, while preserving logical equivalence,
e.g., the decomposition in start- and end-points for Allen’s
Interval Calculus. We show that finding such decompositions
is an NP-complete problem and present a SAT-based method to
generate decompositions. Finally, we discuss the impact of our
decomposition method on SAT encodings of problem instances,
and present a reasoning system built on decompositions that
compares favorably with state-of-the-art solvers.
-
Stefan Wölfl (ed.).
Poster and Demo Track of the 35th German Conference on Artificial Intelligence (KI-2012), September 24-27, 2012, Saarbrücken, Germany.
2012.
(PDF)
2011
-
Anthony G. Cohn, Jochen Renz and Stefan Wölfl (eds.).
Proceedings of the IJCAI-2011 Workshop on Benchmarks and Applications of Spatial Reasoning,
Barcelona, Spain, July 17, 2011.
2011.
(PDF)
-
Manuel Bodirsky and Stefan Wölfl.
RCC8 is Polynomial on Networks of Bounded Treewidth.
In
Proceedings of the 22nd International Joint
Conference on Artificial Intelligence
(IJCAI 2011), pp. 756-761.
AAAI Press 2011.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
We construct an homogeneous (and ω-categorical)
representation of the relation algebra RCC8, which is one of the
fundamental formalisms for spatial reasoning. As a consequence we
obtain that the network consistency problem for RCC8 can be solved
in polynomial time for networks of bounded treewidth.
-
Matthias Westphal, Stefan Wölfl, Bernhard Nebel and Jochen Renz.
On Qualitative Route Descriptions: Representation and
Computational Complexity.
In
Proceedings of the 22nd International Joint
Conference on Artificial Intelligence
(IJCAI 2011), pp. 1120-1125.
AAAI Press 2011.
(Show abstract)
(Hide abstract)
(Online; PDF)
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.
-
Mehul Bhatt, Hans Guesgen, Stefan Wölfl and Shyamanta Hazarika.
Qualitative Spatial and Temporal Reasoning: Emerging Applications, Trends, and Directions.
Spatial Cognition & Computation: An Interdisciplinary Journal 11 (1), pp. 1-14. 2011.
(DOI)
-
Matthias Westphal, Christian Dornhege, Stefan Wölfl, Marc Gissler and Bernhard Nebel.
Guiding the Generation of Manipulation Plans by Qualitative Spatial Reasoning.
Spatial Cognition & Computation: An Interdisciplinary Journal 11 (1), pp. 75-102. 2011.
(Show abstract)
(Hide abstract)
(Online; DOI)
(BIB)
Manipulation planning is a complex task for robots with a manipulator arm that need to grasp objects in the environment, specifically under narrow spatial conditions restricting the workspace of the robot. A popular approach for generating motion plans is probabilistic roadmap planning. However, the sampling strategy of such planners is usually unguided, and hence may lead to motion plans that seem counterintuitive for a human observer. In this article we present an approach that generates heuristics for the probabilistic sampling strategy from spatial plans that abstract from concrete metric data. These spatial plans describe a free trajectory in the workspace of the robot on a purely qualitative level, i.e., by employing spatial relations from formalisms considered in the domain of Qualitative Spatial and Tem- poral Reasoning. We discuss how such formalisms and constraint-based reasoning methods can be applied to approximate geometrically feasible motions. The paper is completed by an evaluation of a hybrid planning system in different spatial settings showing that run-times are notably improved when an abstract plan is considered as a guidance heuristic.
2010
-
Jochen Renz and Stefan Wölfl.
A Qualitative Representation of Route Networks.
In
Proceedings of the 19th European Conference on
Artificial Intelligence (ECAI
2010), pp. 1091-1092.
IOS Press 2010.
(DBLP)
-
Matthias Westphal, Stefan Wölfl and Jason Jingshi Li.
Restarts and Nogood Recording in Qualitative Constraint-based Reasoning.
In
Proceedings of the 19th European Conference on
Artificial Intelligence (ECAI
2010), pp. 1093-1094.
IOS Press 2010.
Also, see the follow up paper at KI 2012: Nogoods in Qualitative Constaint-based Reasoning.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
This paper introduces restart and nogood recording techniques in the
domain of qualitative spatial and temporal reasoning.
Nogoods and restarts can be applied orthogonally to usual
methods for solving qualitative constraint satisfaction problems.
In particular, we propose a more general definition of nogoods
that allows for exploiting information about nogoods and tractable
subclasses during backtracking search.
First evaluations of the proposed techniques show promising results.
2009
-
Florian Pommerening, Stefan Wölfl and Matthias Westphal.
Right-of-Way Rules as Use Case for Integrating GOLOG and Qualitative Reasoning.
In
Bärbel Mertsching, Marcus Hund and Muhammad Zaheer Aziz (eds.),
Proceedings of the 32nd Annual Conference on Artificial
Intelligence (KI 2009), pp. 468-475.
Springer-Verlag 2009.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
Agents interacting in a dynamically changing spatial environment often
need to access the same spatial resources. A typical example is
given by moving vehicles that meet at an intersection in a street
network. In such situations right-of-way rules regulate the
actions the vehicles involved may perform.
For this application scenario we show how the Golog framework for
reasoning about action and change can be enhanced by external
reasoning services that implement techniques known from the domain of
Qualitative Spatial Reasoning.
-
Matthias Westphal and Stefan Wölfl.
Qualitative CSP, finite CSP, and SAT: Comparing methods for qualitative constraint-based reasoning.
In
Proceedings of the 21th International Joint Conference
on Artificial Intelligence (IJCAI 2009).
2009.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
Qualitative Spatial and Temporal Reasoning (QSR) is concerned with
constraint-based formalisms for representing, and reasoning with,
spatial and temporal information over infinite domains. Within the
community it has been a widely accepted assumption that genuine
qualitative reasoning methods outperform other reasoning methods
that are applicable to encodings of qualitative CSP instances.
Recently this assumption has been tackled by several authors, who
proposed to encode qualitative CSP instances as finite CSP or SAT
instances. In this paper we report on the results of a broad empirical
study in which we compared the performance of several reasoners on
instances from different qualitative formalisms.
Our results show that for small-sized qualitative
calculi (e.g. Allen's interval algebra and RCC-8) a state-of-the-art
implementation of QSR methods currently gives the most efficient
performance. However, on recently suggested large-size calculi, e.g.
OPRA_4, finite CSP encodings provide a considerable performance gain.
These results confirm a conjecture by Bessière stating that
support-based constraint propagation algorithms provide better
performance for large-sized qualitative calculi.
-
Stefan Wölfl and Matthias Westphal.
On combinations of binary qualitative constraint calculi.
In
Proceedings of the 21th International Joint Conference
on Artificial Intelligence (IJCAI 2009).
2009.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
Qualitative constraint calculi are representation formalisms that
allow for efficient reasoning about spatial and temporal information.
Many of the calculi discussed in the field of Qualitative Spatial
and Temporal Reasoning can be defined as combinations of other, simpler
and more compact formalisms. On the other hand, existing calculi can
be combined to a new formalism in which one can represent, and reason
about, different aspects of a domain at the same time. For example,
Gerevini and Renz presented a loose combination of the region
connection calculus RCC-8 and the point algebra: the resulting
formalism integrates topological and qualitative size relations between
spatially extended objects. In this paper we compare the approach by
Gerevini and Renz to a method that generates a new qualitative
calculus by exploiting the semantic interdependencies between the
component calculi.
We will compare these two methods and analyze some formal
relationships between a combined calculus and its components. The
paper is completed by an empirical case study in which the reasoning
performance of the suggested methods is compared on random test
instances.
-
Bernhard Nebel and Stefan Wölfl.
Benchmarking of Qualitative Spatial and Temporal Reasoning Systems.
2009.
AAAI Technical Report SS-09-02.
(Show abstract)
(Hide abstract)
(Online; AAAI)
Over the past 25 years the domain of qualitative spatial and temporal reasoning has evolved to an established subfield of AI. Qualitative reasoning aims at the development of formalisms that are close to conceptual schematas used by humans for reasoning about their physical environment, in particular, about temporal and spatial information. Application fields of qualitative reasoning include human-machine interaction, high-level agent control, geographic information systems, spatial planning, ontological reasoning, and cognitive modeling.
To foster real-world applications, representation and reasoning methods used in qualitative reasoning need to be tested against evaluation criteria adapted from other AI fields and cognitive science. The aim of the symposium was to boost the development of well-founded and widely accepted evaluation standards and practical benchmark problems. This includes the measures to compare different qualitative formalisms in terms of cognitive adequacy, expressiveness, and computational efficiency; the development of a domain and problem specification language for benchmarking purposes; the identification of significant benchmark domains and problem instances based on natural use cases, as well as the creation of a problem repository; and the measures to evaluate the performance of implemented reasoning systems. The symposium fostered the benchmarking idea in the qualitative reasoning domain, contributed to identify a graded set of challenges for future research, and pushed the development of qualitative reasoning methods and systems towards application-relevant problems.
-
Matthias Westphal and Stefan Wölfl.
Confirming the QSR Promise.
In
AAAI Spring Symposium on Benchmarking of Qualitative Spatial and Temporal Reasoning Systems.
2009.
AAAI Technical Report SS-09-02.
(Show abstract)
(Hide abstract)
(PDF)
Within the qualitative spatial reasoning community it has been a
widely accepted commonplace that reasoning in qualitative constraint
calculi outperforms reasoning in other more general and expressive
formalisms. To check the correctness of this assumption we conducted
some empirical case studies in which we compared the performance of
a qualitative constraint solver with different automated reasoning
systems, namely first-order and description logic reasoners. We also
report on some first results from comparing the performance of
qualitative and finite constraint solvers. Our empirical tests are
based on randomly generated instances of qualitative constraint
satisfaction problems, which have been encoded as reasoning problems
for first-order reasoners, description logic reasoners, and finite
CSP solvers, respectively. Given our currently used encodings,
these studies show that first-order and description logic reasoners
are far from being feasible for problem sizes that can easily be
solved by a qualitative reasoner. In contrast, finite CSP solvers
are competitive, but still outperformed by a qualitative reasoner on
the problem instances considered here.
-
Matthias Westphal, Stefan Wölfl and Zeno Gantner.
GQR: A Fast Solver for Binary Qualitative Constraint Networks.
In
AAAI Spring Symposium on Benchmarking of Qualitative Spatial and Temporal Reasoning Systems.
2009.
AAAI Technical Report SS-09-02.
(Show abstract)
(Hide abstract)
(PDF)
Qualitative calculi are constraint-based representation formalisms
that allow for efficient reasoning about continuous aspects of the
world with inherently infinite domains, such as time and space. GQR
(Generic Qualitative Reasoner) is a tool that provides reasoning
services for arbitrary binary qualitative calculi. Given
qualitative information expressible in a qualitative calculus, GQR
checks whether this information is consistent w.r.t. the calculus
definition. GQR employs state-of-the-art techniques in both
qualitative and constraint reasoning, such as heuristic search and
usage of known tractable subclasses. In contrast to specialized
reasoners, it offers reasoning services for a variety of calculi
known in the literature, which can be defined in a simple
specification language. The main focus in the design and
implementation of GQR is to provide a generic and extensible solver
that preserves efficiency and scalability.
2008
-
Christian Freksa, Nora Newcombe, Peter Gärdenfors and Stefan Wölfl (eds.).
Spatial Cognition VI: Learning, Reasoning, and Talking
about Space, International Conference Spatial Cognition 2008 (SC '08),
Freiburg, Germany, September 15-19, 2008.
Volume 5248 of Lecture Notes in Artificial Intelligence.
Springer 2008.
(Springer)
(DBLP)
-
Diedrich Wolter, Frank Dylla, Stefan Wölfl, Jan Oliver Wallgrün, Lutz Frommberger, Bernhard Nebel and Christian Freksa.
SailAway: Spatial Cognition in Sea Navigation.
Künstliche Intelligenz 08 (1), pp. 28-30. 2008.
(Show abstract)
(Hide abstract)
(PDF)
Pedestrians, bicyclists, car drivers, boat and airplane pilots, as well as other cognitive agents participating in public traffic must respect rules in order to avoid dangerous situations and to ensure a smooth flow of traffic. The SailAway project investigates traffic and related navigational rules from a formal and computational point of view. The aim is to enable artificial cognitive agents to act in compliance with such rules. Traffic rules, which are expressed in natural language, usually subsume distinct, but similar situations and actions under more abstract spatial or temporal concepts and relations. In this paper we describe an approach to representing rules that exploits this qualitative nature of natural language descriptions used in traffic laws. Based on this approach we present methods that enable an agent to determine actions that are rule-compliant with respect to its current spatial situation. Finally we present the prototype of a control system of boats in sea navigation that implements exactly these methods.
-
Frank Dylla, Diedrich Wolter, Lutz Frommberger, Christian
Freksa, Stefan Wölfl and Bernhard Nebel.
Qualitative Methoden zur Steuerung von Agenten - SailAway:
Raumkognition zur Steuerung von Schiffen.
Industrie Management 4. 2008.
(BIB)
-
Marco Ragni and Stefan Wölfl.
Reasoning about topological
and positional information in dynamic settings.
In
Proceedings of the Twenty-First International FLAIRS Conference
(2008), pp. 606-611.
2008.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
Typical application fields of spatial and spatio-temporal
representation formalisms and reasoning techniques include
geographic information systems (GIS), mobile assistance systems
for route finding, layout descriptions, and navigation tasks of
robots interacting with humans. Often these formalisms focus on
specific spatial aspects in that they use either topological or
positional relations. In this paper we propose a formalism
which allows for representing topological and positional
relations between disks in the plane. Although this formalism
employs a rather abstract representation of objects as disks, it
provides an interesting test-bed for investigating typical
problems that arise when topological and positional information
about objects are combined, or when such combined formalisms are
used to represent continuous changes in the considered
application scenario.
-
Matthias Westphal and Stefan Wölfl.
Bipath Consistency Revisited.
In
Proceedings of the ECAI'08 Workshop on Spatial and Temporal Reasoning.
Patras, Greece 2008.
(Show abstract)
(Hide abstract)
(PDF)
In the field of qualitative spatial and temporal reasoning
combinations of constraint calculi have attracted considerable
research interest in recent years. Beside combinations of spatial
and temporal calculi, it is an important research topic to develop
generic methods for combining calculi dealing with different spatial
aspects. The prototypical example is the combination of the region
connection calculus RCC8 and the point algebra first discussed by
Gerevini and Renz, which allows to represent, and reason about,
topological and size information about spatially extended objects.
To solve constraints in this calculus, Gerevini and Renz also
proposed an algorithm, the bipath consistency algorithm, which
allows for deciding consistency of a given constraint network for
specific sets of relations combining topology and size. In this
article we will compare the "bipath consistency"-based combination
method to the standard method, which is to combine calculi by
generating a new calculus and applying the standard path
consistency method. Gerevini and Renz's calculus combining
topological and size information will serve as the running example
of such combinations and also as a test case for an empirical
analysis.
-
Zeno Gantner, Matthias Westphal and Stefan Wölfl.
GQR - A Fast Reasoner for Binary Qualitative Constraint Calculi.
In
Proceedings of the AAAI'08 Workshop on Spatial and Temporal Reasoning.
Chicago, USA 2008.
(Show abstract)
(Hide abstract)
(PDF)
GQR (Generic Qualitative Reasoner) is a solver for binary
qualitative constraint networks. GQR takes a calculus description
and one or more constraint networks as input, and tries to solve the
networks using the path consistency method and (heuristic)
backtracking. In contrast to specialized reasoners, it offers
reasoning services for different qualitative calculi, which means
that these calculi are not hard-coded into the reasoner. Currently,
GQR supports arbitrary binary constraint calculi developed for
spatial and temporal reasoning, such as calculi from the RCC family,
the intersection calculi, Allen's interval algebra, cardinal
direction calculi, and calculi from the OPRA family. New calculi
can be added to the system by specifications in a simple text format
or in an XML file format. The tool is designed and implemented with
genericity and extensibility in mind, while preserving efficiency
and scalability. The user can choose between different data
structures and heuristics, and new ones can be easily added to the
object-oriented framework. GQR is free software distributed under
the terms of the GNU General Public License.
2007
-
Stefan Wölfl, Till Mossakowski and Lutz Schröder.
Qualitative constraint calculi: Heterogeneous verification of composition tables.
In
Proceedings of the Twentieth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2007), pp. 665-670.
AAAI Press 2007.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
In the domain of qualitative constraint reasoning, a subfield
of AI which has evolved in the past 25 years, a large number of
calculi for efficient reasoning about spatial and temporal
entities has been developed. Reasoning techniques developed for
these constraint calculi typically rely on so-called composition
tables of the calculus at hand, which allow for replacing
semantic reasoning by symbolic operations. Often these
composition tables are developed in a quite informal, pictorial
manner--a method which seems to be error-prone. In view of
possible safety critical applications of qualitative calculi,
however, it is desirable to formally verify these composition
tables. In general, the verification of composition tables is a
tedious task, in particular in cases where the semantics of the
calculus depends on higher-order constructs such as sets. In
this paper we address this problem by presenting a heterogeneous
proof method that allows for combining a higher-order proof
assistance system (such as Isabelle) with an automatic (first
order) reasoner (such as SPASS or VAMPIRE). The benefit of this
method is that the number of proof obligations that is to be
proven interactively with a semi-automatic reasoner can be
minimized to an acceptable level.
-
Diedrich Wolter, Frank Dylla, Lutz Frommberger, Jan Oliver Wallgrün, Bernhard Nebel and Stefan Wölfl.
Qualitative Spatial Reasoning for Rule Compliant Agent Navigation.
In
Proceedings of the Twentieth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2007), pp. 673-674.
AAAI Press 2007.
(Show abstract)
(Hide abstract)
(PDF)
Artificial agents participating in public traffic must respect rules that regulate traffic. Rule sets are commonly formulated in natural language using purely qualitative terms. We present a case study on how to realize rule compliant agent control in the domain of sea navigation by using qualitative spatial reasoning techniques.
-
Frank Dylla, Lutz Frommberger, Jan Oliver Wallgrün, Diedrich Wolter, Bernhard Nebel and Stefan Wölfl.
SailAway: Formalizing navigation rules.
In
Proceedings of the Artificial and Ambient Intelligence Symposium
on Spatial Reasoning and Communication (AISB 2007).
2007.
(Show abstract)
(Hide abstract)
(PDF)
Agents that have to solve navigational tasks need to consider
aspects that go far beyond single-agent goal-directed
deliberation: What an agent does in a specific situation often
interferes with what other agents do at the same time. In order
to avoid conflicts or even collisions, situations in space are
governed by laws, rules, and agreements between the involved
agents. For this reason, artificial agents interacting with
humans must be able to process such rule sets, which are usually
formulated in natural language. In this paper we present a case
study on how to formalize navigation rules in the domain of sea
navigation. We present an approach that uses qualitative
representations of navigation rules. Qualitative spatial
reasoning methods can be applied to distinguish permissible
actions in the set of all possible actions. We argue that an
agent’s spatial representation can be modeled on a qualitative
level in a natural way and that this also empowers sophisticated
high-level agent control.
2006
-
Stefan Wölfl and Till Mossakowski.
Qualitative Constraint Calculi - Application and
Integration, Workshop
at KI 2006, Bremen, Germany, June 14, 2006, Workshop
Proceedings.
2006.
(PDF)
-
Till Mossakowski, Lutz Schroeder and Stefan Wölfl.
A categorical perspective on qualitative constraint calculi.
In
Qualitative Constraint Calculi - Application and Integration, Workshop at KI 2006.
2006.
(Show abstract)
(Hide abstract)
(PDF)
In the domain of qualitative constraint reasoning, a subfield
of AI which has evolved in the last 25 years, a large number of
calculi for efficient reasoning about space and time has been
developed. Reasoning problems in such calculi are usually
formulated as constraint satisfaction problems. For temporal and
spatial reasoning, these problems often have infinite domains,
which need to be abstracted to (finite) algebras in order to
become computationally feasible. Ligozat has argued that the
notion of weak representation plays a crucial role: it not only
captures the correspondence between abstract relations (in a
relation algebra or non-associative algebra) and relations in a
concrete domain, but also corresponds to algebraically closed
constraint networks. In this work, we examine properties of the
category of weak representations and treat the relations between
partition schemes, non-associative algebras and concrete domains
in a systematic way. This leads to the notion of semi-strong
representation, which captures the correspondence between
abstract and concrete relations better than the notion of weak
representation does. The slogan is that semi-strong
representations avoid unnecessary loss of
information. Furthermore, we hope that the categorical
perspective will help in the future to provide new insights on
the important problem of determining whether algebraic
closedness decides consistency of constraint networks.
-
Marco Ragni and Stefan Wölfl.
Temporalizing Cardinal Directions: From Constraint Satisfaction to Planning.
In
Proceedings of the Knowledge Representation Conference (KR 2006).
2006.
(PDF)
2005
-
Marco Ragni and Stefan Wölfl.
Temporalizing Spatial Calculi: On Generalized Neighborhood
Graphs.
In
Proceedings of the 28th Annual German Conference on AI (KI 2005), pp. 64-78.
2005.
(PDF)
-
Stefan Wölfl and Till Mossakowski.
CASL specifications of qualitative calculi.
In
Spatial Information Theory: Cognitive and Computational Foundations, Proceedings of COSIT'05, pp. 200-217.
2005.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
In AI a large number of calculi for efficient reasoning about
spatial and temporal entities have been developed. The most
prominent temporal calculi are the point algebra of linear time
and Allen's interval calculus. Examples of spatial calculi
include mereotopological calculi, Frank's cardinal direction
calculus, Freksa's double cross calculus, Egenhofer and
Franzosa's intersection calculi, and Randell, Cui, and Cohn's
region connection calculi. These calculi are designed for
modeling specific aspects of space or time, respectively, to the
effect that the class of intended models may vary widely with
the calculus at hand. But from a formal point of view these
calculi are often closely related to each other. For example,
the spatial region connection calculus RCC5 may be considered a
coarsening of Allen's (temporal) interval calculus. And vice
versa, intervals can be used to represent spatial objects that
feature an internal direction. The central question of this
paper is how these calculi as well as their mutual dependencies
can be axiomatized by algebraic specifications. This question
will be investigated within the framework of the Common
Algebraic Specification Language (CASL), a specification
language developed by the Common Framework Initiative for
algebraic specification and development (COFI). We explain
scope and expressiveness of CASL by discussing the
specifications of some of the calculi mentioned before.
-
Stefan Wölfl.
Events in branching time.
Studia Logica 79 (2), pp. 255-282. 2005.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
The concept of event is one of the key notions of many
theories dealing with causality or agency. In this paper we
study different approaches to events that share the basic
assumption that events can be analyzed fruitfully in
branching-time structures. The terminological framework
developed thereby may be helpful for further analyses in the
fields of causality and agency and also in those fields of
computational semantics, where similar concepts are considered.
2004
-
Marco Ragni and Stefan Wölfl.
Branching Allen: Reasoning with Intervals in Branching Time.
In
Spatial Cognition IV: Reasoning, Action, Interaction,
International Conference Spatial Cognition 2004, 2004.
Proceedings.
Springer-Verlag 2004.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
Allen’s interval calculus is one of the most prominent
formalisms in the domain of qualitative spatial and temporal
reasoning. Applications of this calculus, however, are
restricted to domains that deal with linear flows of time. But
how the fundamental ideas of Allen’s calculus can be extended to
other, weaker structures than linear orders has gained only
little attention in the literature. In this paper we will
investigate intervals in branching flows of time, which are of
special interest for temporal reasoning, since they allow for
representing indeterministic aspects of systems, scenarios,
planning tasks, etc. As well, branching time models, i. e.,
treelike non-linear structures, do have interesting applications
in the field of spatial reasoning, for example, for modeling
traffic networks. In a first step we discuss interval relations
for branching time, thereby comprising various sources from the
literature. Then, in a second step, we present some new
complexity results concerning constraint satisfaction problems
of interval relations in branching time.
-
Stefan Wölfl.
Qualitative action theory: A comparison of the semantics of
Alternating-time Temporal Logic and the Kutschera-Belnap approach
to agency.
In
J. J. Alferes and J. Leite (eds.),
Proceedings of the 9th European Conference on Logics in Artificial Intelligence
(JELIA 2004).
Springer-Verlag 2004.
(Show abstract)
(Hide abstract)
(PDF)
(DBLP)
Qualitative action theory deals with purely qualitative
descriptions and formal representations of agency, i.e., agents
and their possibilities for intervening in the causal flow of
events. This means that, contrary to game theory, qualitative
action theory abstains from any metric evaluation of the
outcomes of actions. In this paper we present and compare two
qualitative approaches to action theory that have been discussed
in the literature. The first one coming from philosophical
action theory is the Kutschera-Belnap approach, which is the
semantic basis of so-called Stit-logics. The second approach is
the semantics of Alur, Henzinger, and Kupferman's
Alternating-time Temporal Logic (ATL). In computer science, ATL
has been introduced as an extension of Computational Tree Logic
(CTL) to allow for modeling systems that interact with their
environment. Surprisingly, although both approaches are very
close in spirit, a systematic analysis of the mutual
dependencies between these approaches does not exist. The paper
aims at bringing together these two research streams, which seem
to have been developed independently in philosophy and computer
science. In particular, we will investigate the assumptions with
which both approaches may be considered equivalent. Finally,
further research on this topic promises interesting results that
translate between the approaches presented here.
2002
1999
-
Stefan Wölfl.
Combinations of tense and modality for predicate
logic.
Journal of Philosophical Logic 28, pp. 371-398. 1999.
(Show abstract)
(Hide abstract)
(PDF)
In recent years combinations of tense and modality have moved
into the focus of logical research. From a philosophical point
of view, logical systems combining tense and modality are of
interest because these logics have a wide field of application
in original philosophical issues, for example in the theory of
causation, of action, etc. But until now only methods yielding
completeness results for propositional languages have been
developed. In view of philosophical applications, analogous
results with respect to languages of predicate logic are
desirable, and in this paper I present two such results. The
main developments in this area can be split into two directions,
differing in the question whether the ordering of time is
world-independent or not. Semantically, this difference appears
in the discussion whether T×W-frames or Kamp-frames
(resp. Ockham-frames) provide a suitable semantics for
combinations of tense and modality. Here, two calculi are
presented, the first adequate with respect to Kamp-semantics,
the second to T×W-semantics. (Both calculi contain an
appropriate version of Gabbay's irreflexivity rule.)
Furthermore, the proposed constructions of canonical frames
simplify some of those which have hitherto been discussed.
-
Stefan Wölfl.
Kombinierte Zeit- und Modallogik: Vollständigkeitsresultate
für prädikatenlogische Sprachen.
Volume 5 of Logische Philosophie.
Logos Verlag, Berlin, Germany 1999.
Dissertation Thesis.
My Erdös number is presumably equal to 4: Stefan Wölfl, Till Mossakowski, George E. Strecker, Marcel Erne, Paul Erdös.
