Author name cluster

Peter Schüller

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

2 author rows

IJCAI Conference 2022 Conference Paper

Abstraction for Non-Ground Answer Set Programs (Extended Abstract)

Zeynep G. Saribatur
Thomas Eiter
Peter Schüller

Abstraction is a powerful technique that has not been considered much for nonmonotonic reasoning formalisms including Answer Set Programming (ASP), apart from related simplification methods. We introduce a notion for abstracting from the domain of an ASP program that shrinks the domain size and over-approximates the set of answer sets, as well as an abstraction-&-refinement methodology that, starting from an initial abstraction, automatically yields an abstraction with an associated answer set matching an answer set of the original program if one exists. Experiments reveal the potential of the approach, by its ability to focus on the program parts that cause unsatisfiability and by achieving concrete abstract answer sets that merely reflect relevant details.

PDF Details DOI

AIJ Journal 2021 Journal Article

Abstraction for non-ground answer set programs

Zeynep G. Saribatur
Thomas Eiter
Peter Schüller

Abstraction is an important technique utilized by humans in model building and problem solving, in order to figure out key elements and relevant details of a world of interest. This naturally has led to investigations of using abstraction in AI and Computer Science to simplify problems, especially in the design of intelligent agents and automated problem solving. By omitting details, scenarios are reduced to ones that are easier to deal with and to understand, where further details are added back only when they matter. Despite the fact that abstraction is a powerful technique, it has not been considered much in the context of nonmonotonic knowledge representation and reasoning, and specifically not in Answer Set Programming (ASP), apart from some related simplification methods. In this work, we introduce a notion for abstracting from the domain of an ASP program such that the domain size shrinks while the set of answer sets (i. e. , models) of the program is over-approximated. To achieve the latter, the program is transformed into an abstract program over the abstract domain while preserving the structure of the rules. We show in elaboration how this can be also achieved for single or multiple sub-domains (sorts) of a domain, and in case of structured domains like grid environments in which structure should be preserved. Furthermore, we introduce an abstraction-&-refinement methodology that makes it possible to start with an initial abstraction and to achieve automatically an abstraction with an associated abstract answer set that matches an answer set of the original program, provided that the program is satisfiable. Experiments based on prototypical implementations reveal the potential of the approach for problem analysis, by its ability to focus on the parts of the program that cause unsatisfiability and by achieving concrete abstract answer sets that merely reflect relevant details. This makes domain abstraction an interesting topic of research whose further use in important areas like Explainable AI remains to be explored.

Details DOI

ECAI Conference 2020 Conference Paper

ASP-Based Signal Plan Adjustments for Traffic Flow Optimization

Thomas Eiter
Andreas A. Falkner
Patrik Schneider
Peter Schüller

Worldwide, many cities spend considerable effort to reduce traffic and specifically to avoid traffic congestions. Adaptive traffic control systems serve this purpose by dynamically adjusting traffic signals for optimizing the traffic flow on intersections. Systems such as SCOOT are based on an “intelligent” combination of different traffic optimization strategies. However, they miss the possibility (i) to add and change on-demand rules to implement new optimization strategies, and (ii) to simulate the outcome of new strategies on-the-fly which is similar to the capabilities of microscopic traffic simulation tools such as SUMO. In order to overcome the above limitations, we present a novel approach for calculating signal phase plans (SPPs) used for optimizations in traffic control systems. Our approach is based on Answer Set Programming (ASP) and combines ASP encodings of an abstract mesoscopic flow model and a strategy for generating possible SPPs. Experimental results shows that traffic simulation can be well approximated and that the generated SPPs improve the traffic flow effectively.

Details

IJCAI Conference 2020 Conference Paper

Overcoming the Grounding Bottleneck Due to Constraints in ASP Solving: Constraints Become Propagators

Bernardo Cuteri
Carmine Dodaro
Francesco Ricca
Peter Schüller

Answer Set Programming (ASP) is a well-known formalism for Knowledge Representation and Reasoning, successfully employed to solve many AI problems, also thanks to the availability of efficient implementations. Traditionally, ASP systems are based on the ground&solve approach, where the grounding transforms a general input program into its propositional counterpart, whose stable models are then computed by the solver using the CDCL algorithm. This approach suffers an intrinsic limitation: the grounding of one or few constraints may be unaffordable from a computational point of view; a problem known as grounding bottleneck. In this paper, we develop an innovative approach for evaluating ASP programs, where some of the constraints of the input program are not grounded but automatically translated into propagators of the CDCL algorithm that work on partial interpretations. We implemented the new approach on top of the solver WASP and carried out an experimental analysis on different benchmarks. Results show that our approach consistently outperforms state-of-the-art ASP systems by overcoming the grounding bottleneck.

PDF Details DOI

JELIA Conference 2019 Conference Paper

Abstraction for Non-ground Answer Set Programs

Zeynep G. Saribatur
Peter Schüller
Thomas Eiter

Abstract We address the issue of abstraction, a widely used notion to simplify problems, in the context of Answer Set Programming (ASP), which is a highly expressive formalism and a convenient tool for declarative problem solving. We introduce a method to automatically abstract non-ground ASP programs given an abstraction over the domain, which ensures that each original answer set is mapped to some abstract answer set. We discuss abstraction possibilities on several examples and show the use of abstraction to gain insight into problem instances, e. g. , domain details irrelevant for problem solving; this makes abstraction attractive for getting to the essence of the problem. We also provide a tool implementing automatic abstraction from an input program.

Details

JELIA Conference 2019 Conference Paper

The Hexlite Solver - Lightweight and Efficient Evaluation of HEX Programs

Peter Schüller

Abstract \(\textsc {hexlite}\) is a lightweight solver for the \(\textsc {hex}\) formalism which integrates Answer Set Programming (ASP) with external computations. The main goal of \(\textsc {hexlite}\) is efficiency and simplicity, both in implementation as well as in installation of the system. We define the Pragmatic \(\textsc {hex}\) Fragment which permits to partition external computations into two kinds: those that can be evaluated during the program instantiation phase, and those that need to be evaluated during the answer set search phase. \(\textsc {hexlite}\) is written in \(\textsc {python}\) and suitable for evaluating this fragment with external computations that are realized in \(\textsc {python}\). Most performance-critical tasks are delegated to the \(\textsc {python}\) module of \(\textsc {clingo}\). We demonstrate that the Pragmatic \(\textsc {hex}\) Fragment is sufficient for many use cases and that it permits \(\textsc {hexlite}\) to have superior performance compared to the \(\textsc {dlvhex}\) system in relevant application scenarios.

Details

AIJ Journal 2014 Journal Article

Finding explanations of inconsistency in multi-context systems

Thomas Eiter
Michael Fink
Peter Schüller
Antonius Weinzierl

Interlinking knowledge sources to enable information exchange is basic means to build enriched knowledge-based systems, which gains importance with the spread of the Internet. Inconsistency, however, arises easily in such systems, which is not least due to their heterogeneity, but also due to their independent design. This makes developing methods for consistency management of such systems a pressing issue. An important aspect is that in many relevant cases, the information at individual sources may not be amenable to change in order to resolve inconsistency, like in case of autonomous management of the sources. We thus aim at analyzing inconsistency of a system by means of the interlinking of sources and changes thereof. More concretely, we consider the powerful framework of Multi-Context Systems, in which decentralized and heterogeneous system parts interact via (possibly nonmonotonic) bridge rules for information exchange. Nonmonotonicity and potential cyclic dependencies pose additional challenges that call for suitable methods of inconsistency analysis. We thus provide two approaches for explaining inconsistency, which both characterize inconsistency in terms of bridge rules, but in different ways: by pointing out rules which need to be altered for restoring consistency, and by finding combinations of rules which cause inconsistency. We show duality and modularity properties of these notions, give precise complexity characterizations, and provide algorithms for their computation, which have been implemented in a prototype, by means of so-called hex-programs. Our results provide a basis for inconsistency management in heterogeneous knowledge systems which, different from and orthogonal to other works, explicitly addresses the knowledge interlinks in order to restore consistency.

Details DOI

KR Conference 2014 Conference Paper

Tackling Winograd Schemas by Formalizing Relevance Theory in Knowledge Graphs

Peter Schüller

We study disambiguating of pronoun references in Winograd Schemas, which are part of the Winograd Schema Challenge, a proposed replacement for the Turing test. In particular we consider sentences where the pronoun can be resolved to both antecedents without semantic violations in world knowledge, that means for both readings of the sentence there is a possible consistent world. Nevertheless humans will strongly prefer one answer, which can be explained by pragmatic effects described in Relevance Theory. We state formal optimization criteria based on principles of Relevance Theory in a simplification of Roger Schank’s graph framework for natural language understanding. We perform experiments using Answer Set Programming and report the usefulness of our criteria for disambiguation and their sensitivity to parameter variations. [Pete]p envies [Martin]m because hep, m? is very successful. [Pete]p envies [Martin]m although hep, m? is very successful. (4) In (3) the word ‘because’ indicates that ‘hep, m? is very successful’ is a plausible reason for ‘Pete envies Martin’. As a result we can rule out the coreference ‘hep ’ because Martin’s success is a more plausible cause for Pete’s envy than Pete’s success, hence the solution is ‘hem ’. Such reasoning is already challenging, however it is not always sufficient: there are WSs where both possible coreferences correspond to a world where the sentence makes sense — text structure and world knowledge are not sufficient for tackling Winograd Schemas. One example for such a schema is the following.

AAAI Conference 2013 Conference Paper

A General Formal Framework for Pathfinding Problems with Multiple Agents

Esra Erdem
Doga Kisa
Umut Oztok
Peter Schüller

Pathfinding for a single agent is the problem of planning a route from an initial location to a goal location in an environment, going around obstacles. Pathfinding for multiple agents also aims to plan such routes for each agent, subject to different constraints, such as restrictions on the length of each path or on the total length of paths, no self-intersecting paths, no intersection of paths/plans, no crossing/meeting each other. It also has variations for finding optimal solutions, e. g. , with respect to the maximum path length, or the sum of plan lengths. These problems are important for many real-life applications, such as motion planning, vehicle routing, environmental monitoring, patrolling, computer games. Motivated by such applications, we introduce a formal framework that is general enough to address all these problems: we use the expressive high-level representation formalism and efficient solvers of the declarative programming paradigm Answer Set Programming. We also introduce heuristics to improve the computational efficiency and/or solution quality. We show the applicability and usefulness of our framework by experiments, with randomly generated problem instances on a grid, on a real-world road network, and on a real computer game terrain.

PDF Details

JELIA Conference 2012 Conference Paper

Exploiting Unfounded Sets for HEX-Program Evaluation

Thomas Eiter
Michael Fink 0001
Thomas Krennwallner
Christoph Redl
Peter Schüller

Abstract HEX programs extend logic programs with external computations through external atoms, whose answer sets are the minimal models of the Faber-Leone-Pfeifer-reduct. As already reasoning from Horn programs with nonmonotonic external atoms of polynomial complexity is on the second level of the polynomial hierarchy, answer set checking needs special attention; simply computing reducts and searching for smaller models does not scale well. We thus extend an approach based on unfounded sets to HEX and integrate it in a Conflict Driven Clause Learning framework for HEX program evaluation. It reduces the check to a search for unfounded sets, which is more efficiently implemented as a SAT problem. We give a basic encoding for HEX and show optimizations by additional clauses. Experiments show that the new approach significantly decreases runtime.

Details

KR Conference 2010 Conference Paper

Finding Explanations of Inconsistency in Multi-Context Systems

Thomas Eiter
Michael Fink
Peter Schüller
Antonius Weinzierl

We provide two approaches for explaining inconsistency in multi-context systems, where decentralized and heterogeneous system parts interact via nonmonotonic bridge rules. Inconsistencies arise easily in such scenarios, and nonmonotonicity calls for speciﬁc methods of inconsistency analysis. Both our approaches characterize inconsistency in terms of involved bridge rules: either by pointing out rules which need to be altered for restoring consistency, or by ﬁnding combinations of rules which cause inconsistency. We show duality and modularity properties, give precise complexity characterizations, and provide algorithms for computation using HEXprograms. Our results form a basis for inconsistency management in heterogeneous knowledge integration systems.

JELIA Conference 2010 Conference Paper

The mcs-ie System for Explaining Inconsistency in Multi-Context Systems

Markus Bögl
Thomas Eiter
Michael Fink 0001
Peter Schüller

Abstract The Multi-Context System Inconsistency Explainer allows for evaluation of semantics and explanation of inconsistencies in systems where heterogeneous knowledge bases are linked via nonmonotonic rules. The implementation is based on the dlvhex tool, which is an extension of answer set programming with external atoms and higher order features.

Details