---
title: "Local Search Topology in Planning Benchmarks: An Empirical Analysis"
authors:
  - "Jörg Hoffmann"
doi: ""
url: "https://ijcai.org/proceedings/2001/63"
pdf: "https://ijcai.org/proceedings/2001/0063.pdf"
venue: "Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence"
year: 2001
pages: "453-457"
track: ""
keywords:
---

# Local Search Topology in Planning Benchmarks: An Empirical Analysis

Jörg Hoffmann

*Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence*, pages 453-457.

## Abstract

Many state-of-the-art heuristic planners derive their heuristic function by relaxing the planning task at hand, where the relaxation is to assume that all delete lists are empty. Looking at a collection of planning benchmarks, we measure topological properties of state spaces with respect to that relaxation. The results suggest that, given the heuristic based on the relaxation, many planning benchmarks are simple in structure. This sheds light on the recent success of heuristic planners employing local search.