Simon Dold – Publications

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), pp. 151-161. 2024.
  (Show abstract) (Hide abstract) (PDF) (slides; PDF) (poster; PDF)
  

  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.
  Planning Domain Modelling Competition.
  In Proceedings of the ICAPS-2024 Workshop on the International Planning Competition (WIPC 2024). 2024.
  (Show abstract) (Hide abstract) (PDF) (slides; PDF)
  

  The international planning competition (IPC) is a recurring event that compares the performance of planners and awards the best ones. The evaluation is based on a set of benchmark problems that describe interesting planning problems in PDDL (planning domain definition language). There is a general interest in high-quality benchmarks. Not only for the IPC but for the research of automated planning in general. We explore the possibility of a planning domain modeling competition that produces them. In this work, we discuss the desirable properties of benchmarks and how they could be evaluated.

• 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), pp. 20692-20699. 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.