NAISS
SUPR
NAISS Projects
SUPR
Levin Tree Search for Automated Planning
Dnr:

NAISS 2026/4-1925

Type:

NAISS Small

Principal Investigator:

Markus Fritzsche

Affiliation:

Linköpings universitet

Start Date:

2026-10-27

End Date:

2027-11-01

Primary Classification:

10201: Computer Sciences

Webpage:

Allocation

Abstract

Levin Tree Search (LTS) combined with bootstrapping has demonstrated promising results in learning to guide search. However, its potential for automated planning remains unexplored. This project investigates how to learn search guidance on small planning instances that generalizes to substantially larger instances, while relying on LTS to find solutions. Three challenges are central to this investigation. First, planning states and goals must be represented in a way that supports learning across instances of different sizes. Second, search guidance trained on small instances must remain effective on larger instances, where increased branching factors can alter the probability distribution induced by softmax normalization and consequently affect search efficiency. Third, planning problems exhibit symmetries and feature collisions, where actions may receive identical representations despite leading to non-equivalent successor states. Handling these cases efficiently is challenging, as common architectures such as graph neural networks have limited expressive power and cannot generally distinguish all relevant structural differences. The project aims to investigate suitable state-goal representations, methods for maintaining effective search guidance across different instance sizes, and approaches for handling symmetries and indistinguishable actions. The objective is to develop and evaluate a learning-based approach to guiding LTS in automated planning, with an emphasis on generalization from small to large planning instances.