Learning Reliable Algorithms for AI Planning

Mission statement: We aim to automatically synthesize scalable and trustworthy AI planning algorithms by combining the theoretical guarantees of reasoning-based approaches with the efficiency of machine learning.

In today's industrial and societal landscape, many tasks require complex decisions over time. For example, logistics companies need to plan the delivery of goods to customers in an efficient manner; manufacturing plants need to schedule production processes to meet demand while minimizing costs; and governments need to plan disaster response strategies and public health interventions. Due to the ubiquity and complexity of such planning tasks, we are increasingly relying on algorithms to make sequential decisions on our behalf. For instance, we are now posing complex planning tasks to large language models such as ChatGPT, although they often yield suboptimal or infeasible plans, even for extremely simple tasks like stacking three blocks.

For reliable decision-making, we need algorithms that reason about the consequences of actions. The research field that develops reasoning-based algorithms for solving complex planning tasks reliably is AI planning. It allows users to specify tasks and to incorporate their knowledge and preferences into the planning process, making the generated plans understandable and trustworthy.

The predominant approach to solving AI planning tasks is state-space search, guided by heuristic functions that estimate goal distances. Since the vast and complex design space makes developing efficient heuristics severely challenging, many researchers, myself included, have started to learn heuristics from data. However, these learned heuristics tend to be opaque and usually struggle to compete with traditional, non-learned alternatives. Beyond these drawbacks regarding interpretability and performance, their most critical limitation is the lack of theoretical guarantees: the quality of the plans and the efficiency of the search can degrade unpredictably, making these heuristics unsuitable for optimal planning or settings where runtime bounds are required.

To address these shortcomings, we aim to develop systems that leverage the solid foundations of reasoning-based approaches while enhancing them efficiently with machine learning, all while preserving crucial theoretical guarantees for the resulting heuristics and overall search algorithms.

PI: Jendrik Seipp

Funding: This project is supported by the Knut and Alice Wallenberg Foundation through a Wallenberg Academy Fellowship.