Gaspard Quenard

Abstract:

Automated planning is the reasoning process that organizes actions by anticipating their expected outcomes, based on prior knowledge of environment dynamics,
enabling autonomous systems to operate without human intervention. Among the various approaches, Hierarchical Task Network (HTN) planning is a powerful paradigm
for structuring the resolution of complex problems. By decomposing abstract tasks into executable actions, the HTN approach offers transparency and interpretability,
essential qualities for critical applications such as rescue missions, space exploration, or underwater operations.
Recently, there has been renewed interest in HTN-SAT approaches that transform the hierarchical problem into a propositional satisfiability (SAT) problem such that a 
satisfiable solution corresponds to a problem solution, thereby leveraging the considerable progress of modern SAT solvers. However, current HTN-SAT planners suffer from
brute-force breadth-first exploration that leads to exponential growth of the search space, limiting their practical efficiency compared to traditional heuristic methods. To
date, no research has explored how to combine the power of HTN-SAT planners with heuristics to better explore the search space.
The objective of this thesis is to explain how we can integrate heuristic approaches directly into the SAT framework for HTN planning. By using relaxed SAT encodings as
heuristic models, the work presented here enables anticipatory evaluation of promising decompositions and drastically reduces the search space. The presented work proposes
several approaches for finding plans quickly or optimally for hierarchical planning. Experimental evaluations demonstrate the superiority of our methods in terms of
efficiency and quality of generated plans compared to current planners.