Automated Planning using Property-Directed Reachability with Seed Heuristics

Abstract

Planning is the process of finding a path in a planning task from the initial state to a goal state. Multiple algorithms have been implemented to solve such planning tasks, one of them being the Property-Directed Reachability algorithm. Property-Directed Reachability utilizes a series of propositional formulas called layers to represent a super-set of states with a goal distance of at most the layer index. The algorithm iteratively improves the layers such that they represent a minimum number of states. This happens by strengthening the layer formulas and therefore excluding states with a goal distance higher than the layer index. The goal of this thesis is to implement a pre-processing step to seed the layers with a formula that already excludes as many states as possible, to potentially improve the run-time performance. We use the pattern database heuristic and its associated pattern generators to make use of the planning task structure for the seeding algorithm. We found that seeding does not consistently improve the performance of the Property-Directed Reachability algorithm. Although we observed a significant reduction in planning time for some tasks, it significantly increased for others.

Download PDF

Cite

@phdthesis{bachmann2023,
    author = {Bachmann, Tim},
    year = {2023},
    month = {05},
    title = {Automated Planning using Property-Directed Reachability with Seed Heuristics},
    doi = {10.13140/RG.2.2.11456.30727},
    type = {Master's Thesis},
    school = {University of Basel}
}