SUPR
Partial Grounding and Structure Exploitation in Planning
Dnr:

NAISS 2024/5-404

Type:

NAISS Medium Compute

Principal Investigator:

Daniel Gnad

Affiliation:

Linköpings universitet

Start Date:

2024-09-03

End Date:

2025-10-01

Primary Classification:

10201: Computer Sciences

Allocation

Abstract

The project is located in the area of sequential decision making in Artificial Intelligence (AI). Sequential decision making is one of the core challenges in AI. Developing systems that can achieve complex goals autonomously requires the capability to take a sequence of decisions that eventually lead the agent to its goal. AI planning has focused on enabling such capabilities for many years, but, in practice, existing solutions often fail to scale up to larger problems. In this project, we leverage the recent successes of data-driven approaches to overcome this limitation. The project will cover two research lines: Research line 1: This line will focus on different aspects of the usage of machine learning for partial grounding. We consider three objectives that are partly connected to each other. First, (1) we will explore different variants of data representation as input to the ML models. We plan to analyze the expressiveness of simple logic features that are used to describe task properties and whose evaluation is fed into an ML model. Furthermore, we will experiment with graph structures. The second objective (2) targets the expressive power of different ML techniques. We will start to experiment with traditional ML models, such as decision trees and support vector machines. Leveraging recent successes of deep learning architectures, we will then explore the possibilities of neural network models, including graph neural networks. Third, (3) we look into possibilities to make the overall planner more dependable. As partially grounded models come with no guarantees, e.g. might be unsolvable although the original task is not, we need a way to measure the robustness of the partial models. Research Line 2: This line consists of two parts: (1) analyzing and exploiting problem structure in planning algorithms to find solutions more efficiently, and (2) optimizing the structure of a planning problem for the algorithm used to solve it. Performing analyses as in (1) has a long tradition in the field. Most research, however, focused on studying the problem structure to obtain results on the computational complexity of planning formalisms. In this project, we build on and advance a recent shift toward directly exploiting the inherent structure of planning models. We will derive specialized variants of established techniques that exploit the identified structure for more efficient computation or improved decision-making. For part (2), we build on previous work that has identified target structures for specific algorithms, as well as novel structural properties from research line (1). The goal is automated preprocessing that optimizes a planning problem for the desired algorithm. The project team consists of the PI, the head of his research lab, and several PhD students (some are already added as members, some new group members will follow). All members will regularly conduct large-scale evaluations on the requested compute infrastructure. This will serve the purpose of assessing newly developed algorithms on a large existing benchmark set.