Faculty of Science
Faculty of Science
UNIverse - Public Research Portal
Projects & Collaborations
31 found
Show per page
Project cover
Problem Solving with Domain-Independent Dynamic Programming: Theory and Practice (DIDP)
Research Project  | 3 Project Members

Domain-independent dynamic programming (DIDP) is a recently proposed framework for modeling combinatorial optimization problems using dynamic programming and solving them with a general purpose solver. Initial results show strong performance using a heuristic state-based search solver, thus demonstrating the success of problem solving approaches developed in Artificial Intelligence (AI) on problems traditionally studied in Operations Research (OR). This project seeks to develop the theory and practice of DIDP-based problem solving by characterizing DIDP from computational and knowledge representation perspectives; by understanding its relationship to the problem solving paradigms embodied in constraint programming, satisfiability, and AI planning; and by developing novel domain-independent heuristics for DIDP through the adaptation and extension of techniques from AI planning, state abstraction in OR, and decision diagram-based optimization.

Project cover
Unifying the Theory and Algorithms of Factored State-Space Search (UTA)
Research Project  | 6 Project Members

Automated planning, also known as factored state-space search, is a fundamental problem in AI with numerous applications in computer science and elsewhere. There are three dominant algorithmic paradigms: heuristic search, symbolic search, and SAT planning. While important theoretical results exist to explain and improve the performance of some of these algorithms, almost nothing is known about the connections between them.

We build a unified theory of factored state-space search that identifies a common reasoning core encompassing all three algorithmic paradigms that allows us to directly relate these algorithms to each other in theory and build hybridized algorithms combining their individual strengths in practice. Identifying such a core also allows us to better understand the trade-off involved between representational expressiveness and efficiency of reasoning and design better algorithms to address this trade-off.

Project cover
Inhomogeneous and compressible fluids: statistical solutions and dissipative anomalies
Research Project  | 1 Project Members

This project addresses several physically motivated questions on the analysis of equations of fluid dynamics. The project has a foundational character and aims at providing a rigorous analytical understanding which will expand our knowledge in the following two directions:

  • From homogeneous incompressible fluids to inhomogeneous and compressible fluids.
  • From classical notions of weak solutions to generalized notions of weak solutions.

In the last ten years, major progress has been achieved on several long-standing questions rooted in the Kolmogorov-Onsager theory of turbulence, most notably the proof via convex integration of the existence of nonconservative solutions of the Euler equations with regularity below 1/3, in which energy is dissipated through creation of small spatial scales. The transport structure of the vorticity equation in two spatial dimensions and the presence of an inverse cascade have been exploited to prove energy conservation and further properties in some Onsager-supercritical regimes. Refined numerical simulations and the manifested insufficiency of the entropy conditions to select a unique solution in many hyperbolic problems led the way to generalized notions of weak solutions, including statistical and measure-valued solutions, with an extended effort in their analysis and computation. 


In spite of all this exciting recent progress, most of the theory is presently limited to homogeneous incompressible fluids and to classical weak solutions. In this project, we aim to go significantly beyond the state of the art, addressing in particular the following topics:

  1. Energy conservation and further properties of Onsager-supercritical statistical solutions for homogeneous incompressible fluids originating from vanishing viscosity or from numerical approximation schemes.
  2. Statistical solutions for inhomogeneous and compressible fluids: foundations.
  3. Energy conservation and further properties of Onsager-supercritical weak solutions for inhomogeneous incompressible fluids.
  4. Conservation anomalies in statistical solutions and for inhomogeneous incompressible fluids.
  5. The same topics as in (C)-(D) for inhomogeneous compressible fluids.


Project cover
FLUTURA: Fluids, Turbulence, Advection
Research Project  | 1 Project Members

The Euler and the Navier-Stokes equations are basic mathematical models for the dynamics of incompressible fluids. Despite being among the first partial differential equations (PDEs) ever written, to a very large extent their mathematical theory remains a riddle. One of the main reasons is the intrinsic lack of regularity of solutions of problems in fluid dynamics. The theory of turbulence advances quantitative predictions for the "typical" properties of "chaotic" fluids, in particular with regard to universal behaviors at small spatial scales. These predictions are well supported by experimental observations, but very few is understood from the point of view of rigorous analysis. Understanding the correct framework validating and predicting the experimental evidence is an exciting and ambitious mathematical question.

In this project we address several challenging open problems in mathematical fluid dynamics. The common feature of all these problems is the appearance of irregular behaviors and the cascade of information to small spatial scales. The irregularity is the main source of difficulty in the mathematical analysis of these questions, since it precludes the use of most classical PDE methods, from energy estimates to the theory of characteristics.

We aim to derive a quantitative analysis and to provide detailed insight of the properties of solutions in physically relevant regimes. This project will significantly expand our theoretical understanding of several phenomena involving irregular flows, addressing in particular the following topics:

  • Selection and nonselection by vanishing viscosity.
  • Anomalous dissipation in the Obukhov-Corrsin theory of scalar turbulence.
  • Conservation and dissipation of the kinetic energy and of the enstrophy in fluid flows.
  • Mixing, regularity, and irregularity for fluid flows.
  • Existence, uniqueness, and structure of solutions for nonlinear problems with diffuse/singular vorticity.

The unity of the project stems from the concepts and the methods in the background, all related to the theory of advection (both deterministic and stochastic) in a nonsmooth setting and relying in an essential way on techniques of geometric measure theory as a crucial tool in the analysis of the fine properties of irregular flows.

Project cover
Lifted and Generalized Representations for Classical Planning (LGR-Plan)
Research Project  | 4 Project Members

Classical planning is the problem of finding a sequence of actions transforming a given initial state into a state satisfying a given goal. Today’s state of the art in classical planning almost universally operates on factored representations inspired by propositional logic: for example, a state space with 2^100 states can be represented with 100 propositional state variables.

Recently, the limitations of such representations have become increasingly apparent, and there is rapidly growing interest in algorithms that directly operate on lifted representations based on first-order predicate logic or similar formalisms. Moreover, several recent works suggested lifted representations that distill information across multiple tasks in the same planning domain (infinite family of planning tasks) into a single generalized representation that applies to all tasks in the domain. A typical approach is to learn or synthesize generalized representations from small example tasks in the domain and then use them to solve more challenging tasks.

We believe that the time is right for lifted and generalized representations to challenge propositional representations as the leading representation paradigm in classical planning. We suggest two research directions in pursuit of this goal:

Lifted algorithms for classical planning: we conceive and implement planning algorithms completely based on lifted representations that outperform state-of-the-art algorithms (based on non-lifted representations). We consider both the setting of satisficing planning (finding plans with no optimality guarantees) and optimal planning (finding plans of minimum cost). This involves devising efficient lifted algorithms for all building blocks of a state-of-the-art planning system and combining them into a well-engineered whole. One major goal for this work package is a “Lifted LAMA” planner outperforming Richter and Westphal’s highly influential LAMA system on the standard benchmark suite in classical planning.

Generalized representations for classical planning: several innovative generalized representations for classical planning have been suggested in the past few years, including action schema networks, generalized potential heuristics, STRIPS hypergraph networks, and sketches. They all come with the hope of significantly improving scalability of classical planning, but so far very little is known about their strengths and weaknesses, both in absolute terms and in relation to each other. We develop an encompassing theory that provides the formal underpinnings to put these disjointed results into a coherent whole. We formally clarify the notion of “planning domain” to be able to express the problems that these approaches attempt to solve in a rigorous way. We analyze the decidability and complexity properties of these problems, and we provide expressivity and compilation results demonstrating the strengths, weaknesses and relationships of these approaches. This includes relating representations used in planning to ones developed in other areas of AI such as (hyper-) graph neural networks and neural logic machines.

Project cover
Polypheny-DDI
Research Project  | 3 Project Members
In recent years, data-driven research has established itself as the fourth pillar in the spectrum of scientific methods, alongside theory, empiric research, and computer-based simulation. In various scientific disciplines, increasingly large amounts of -both structured and unstructured- data are being generated or existing data collections that have originally been isolated from each other are being linked in order to gain new insights. he process of generating knowledge from raw data is called Data Science or Data Analytics. The entire data analytics pipeline is quite complex, and most work focuses on the actual data analysis (using machine learning or statistical methods), while largely neglecting the other elements of the pipeline. This is particularly the case for all aspects related to data management, storage, processing, and retrieval - even though these challenges actually play an essential role. A Distributed Data Infrastructure (DDI) supports a large variety of data management features as demanded by the data analytics pipeline. However, DDIs are usually very heterogeneous in terms of data models, access characteristics, and performance expectations. In addition, DDIs for integrating, continuously updating, and querying data from various heterogeneous applications need to overcome the inherent structural heterogeneity and fragmentation. Recently, polystore databases have gained attention because they help overcome these limitations by allowing data to be stored in one system, yet in different formats and data models and by offering one joint query language. In past work, we have developed Polypheny-DB, a distributed polystore that integrates several different data models and heterogeneous data stores. Polypheny-DB goes beyond most existing polystores and even supports data accesses with mixed workloads (e.g., OLTP and OLAP). However, polystores are limited to rather simple object models, static data and exact queries. When individual data items follow a complex inherent structure and consist of several heterogeneous parts between which dedicated constraints exist, when the access goes beyond exact Boolean queries, when data is not static but continuously produced, and/or when objects need to be preserved in multiple versions, then polystores quickly reach their limits. At the same time, these are typical requirements for data management within a data analytics pipeline. Examples are scientific instruments that continuously produce new data as data streams; social network analysis that requires support for complex object models including structured and unstructured content; data produced by imaging devices that requires sophisticated similarity search support, or frequently changing objects that are subject to time-dependent analyses. The objective of the Polypheny-DDI project is to seamlessly combine the functionality of a polystore database with that of a distributed data infrastructure to meet the requirements of data science applications. It will focus on i.) supporting complex composite object models and enforcing constraints between the constituent parts; ii.) supporting similarity search in multimedia content, and iii.) supporting continuous data streams and temporal/multiversion data.
Project cover
Shape optimization under uncertainty
Research Project  | 2 Project Members
Shape optimization is indispensable for designing and constructing industrial components. Many problems that arise in application, particularly in structural mechanics and in the optimal control of distributed parameter systems, can be formulated as the minimization of functionals which are defined over a class of admissible domains. Shape optimization problems can be solved by means of gradient based minimization algorithms, which involve the shape functionals' derivative with respect to the domain under consideration. The computation of the shape gradient and the implementation of appropriate numerical optimization algorithms is meanwhile well understood, provided that the state equation's input data are given exactly. In practice, however, input data for numerical simulations in engineering are often not exactly known. One must thus address how to account for uncertain input data in the state equation. This project is concered with shape optimization under uncertainty. The uncertainty might be caused by different sources like uncertain geometric entities, uncertain loads, or uncertain material parameters.