Simon Dold

2024

• Simon Dold and Malte Helmert.
  Higher-Dimensional Potential Heuristics: Lower Bound Criterion and Connection to Correlation Complexity.
  In Proceedings of the 34th International Conference on Automated Planning and Scheduling (ICAPS 2024). 2024.
  (Show abstract) (Hide abstract)
  

  Correlation complexity is a measure of a planning task indicating how hard it is. The introducing work provides sufficient criteria to detect a correlation complexity of 2 on a planning task. It also introduced an example of a planning task with correlation complexity 3. In our work, we introduce a criterion to detect an arbitrary correlation complexity and extend the mentioned example to show with the new criterion that planning tasks with arbitrary correlation complexity exist.

• Simon Dold and Malte Helmert.
  Novelty vs. Potential Heuristics: A Comparison of Hardness Measures for Satisficing Planning.
  In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024). 2024.
  (Show abstract) (Hide abstract) (PDF) (slides; PDF) (poster; PDF)
  

  Classical planning considers a given task and searches for a plan to solve it. Some tasks are harder to solve than others. We can measure the “hardness” of a task with the novelty width and the correlation complexity. In this work, we compare these measures. Additionally, we introduce the river measure, a new measure that is based on potential heuristics and therefore similar to the correlation complexity but also comparable to the novelty width. We show that the river measure is upper bounded by the correlation complexity and by the novelty width +1. Furthermore, we show that we can convert a planning task with a polynomial blowup of the task size to ensure that a heuristic of dimension 2 exists that gives rise to backtrack-free search.