Title:	Improved Search Strategies for Domain Independent Planning
DNr:	NAISS 2026/4-694
Project Type:	NAISS Small
Principal Investigator:	Jordan Thayer <jordan.thayer@liu.se>
Affiliation:	Linköpings universitet
Duration:	2026-04-13 – 2027-05-01
Classification:	10210
Homepage:	https://mrlab.ai/jordan-thayer/
Keywords:

Abstract

Modern heuristic search and planning algorithms are increasingly deployed in settings where computational resources are fundamentally constrained. These constraints may arise from hard limits on available time or memory, or from requirements that solutions be generated quickly even if they are provably suboptimal. Research into anytime and bounded-suboptimal heuristic search aims to address these challenges by developing algorithms that can flexibly trade solution quality for computational effort, while still providing strong performance guarantees. This project investigates the design and empirical evaluation of advanced search strategies for solving large-scale planning problems under such resource constraints. The central goal is to better understand how core search strategies—independent of many domain-specific enhancements—affect robustness, scalability, and solution quality across a wide range of planning benchmarks. To that end, the project focuses on head-to-head empirical comparisons between modern baseline strategies (e.g., greedy best-first search, enforced hill-climbing, and variants of weighted A*) and alternative approaches in the family of anytime and bounded-suboptimal search algorithms, with particular emphasis on Triangle Search and other new algorithms for heuristic search. Beyond empirical evaluation, the project also examines why certain search strategies perform well in practice. Early evidence indicates that Triangle Search naturally exhibits behavior resembling established planning enhancements such as restarts and multi-queue control. Understanding these connections may guide the development of simpler, more principled algorithms that achieve strong performance without extensive handcrafted machinery. In the longer term, this research aims to inform the integration of learned control knowledge—such as heuristic bounding and guidance—to further improve algorithmic performance under strict resource constraints.