Introducing Explicit-Symbolic Planning
Minke Verweij

Abstract:
This thesis investigates two dominant planning approaches, heuristic based explicit search and symbolic search, and explores their limitations. While heuristics can guide explicit search effectively, they may still lead to exponential expansion in certain problem instances. Conversely, symbolic search can compactly explore large state spaces but may do exponentially worse when heuristics are applied. To address these limitations, we propose a novel hybrid search algorithm that combines the strengths of both methods. We demonstrate that this hybrid approach solves a specific class of planning problems efficiently, where the other described strategies fail. Furthermore, we initiate an analysis of the challenges in hybrid implementation, particularly the difficulty of splitting the variables into a symbolic and an explicit set. Our work strengthens some prior limitation results and extends the frontier of tractable planning problems via the newly proposed hybrid search algorithm.