Reducing accidental complexity in planning problems

Patrik Haslum*

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

38 Citations (Scopus)

Abstract

Although even propositional STRIPS planning is a hard problem in general, many instances of the problem, including many of those commonly used as benchmarks, are easy. In spite of this, they are often hard to solve for domain-independent planners, because the encoding of the problem into a general problem specification formalism such as STRIPS hides structure that needs to be exploited to solve problems easily. We investigate the use of automatic problem transformations to reduce this "accidental" problem complexity. The main tool is abstraction: we identify a new, weaker, condition under which abstraction is "safe", in the sense that any solution to the abstracted problem can be refined to a concrete solution (in polynomial time, for most cases) and also show how different kinds of problem reformulations can be applied to create greater opportunities for such safe abstraction.

Original languageEnglish
Pages (from-to)1898-1903
Number of pages6
JournalIJCAI International Joint Conference on Artificial Intelligence
Publication statusPublished - 2007
Externally publishedYes
Event20th International Joint Conference on Artificial Intelligence, IJCAI 2007 - Hyderabad, India
Duration: 6 Jan 200712 Jan 2007

Fingerprint

Dive into the research topics of 'Reducing accidental complexity in planning problems'. Together they form a unique fingerprint.

Cite this