Automated Planning using Property-Directed Reachability with Seed Heuristics

Automated Planning using Property-Directed Reachability with Seed Heuristics

dev heuristic pdr planning-system

published on last updated on


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


    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}
You found an error in this post? Open a pull request.
Photo of Tim Bachmann

Hi, my name is Tim Bachmann! I'm a master graduate in computer science at University of Basel, swimmer and swim coach.

I am passionate about all things web development, swimming, personal knowledge management and much more. If you liked this or any of my posts, feel free to follow me.

0 Comments and Interactions

Leave a comment or interact with this page via WebMention

Built with SvelteKit and hosted on GitHub Pages.

View this website on GitHub!

Other pages