Department of Mathematics and Computer Science

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.

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.

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.

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.

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.