Reversed planning graphs for relevance heuristics in AI planning

Mats Petter Pettersson

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

Abstract

Most AI planning heuristics are reachability heuristics, in the sense that they estimate the minimum plan length from the initial state to a search state. Such heuristics are best suited for use in regression state-space planners, since a progression planner would have to reconstruct the heuristic function at each new search state. However, some domains (or problem instances within a certain domain) are better suited for progression search, motivating the need for relevance heuristics that estimate the distance from a search state to the goal state. In this paper we show how to construct reversed planning graphs that can be used for computing new relevance heuristics, based on the work on extracting reachability heuristics from planning graphs, and a general framework for reversing planning domains.
Original languageEnglish
Title of host publicationPlanning, Scheduling and Constraint Satisfaction: From Theory to Practice
PublisherIOS Press
Pages29-38
Volume117
ISBN (Print)978-1-58603-484-9
Publication statusPublished - 2005
Event2nd Starting Artificial Intelligence Researchers Symposium - Valencia, Spain
Duration: 2004 Aug 232004 Aug 24

Publication series

Name
Volume117
ISSN (Print)0922-6389

Conference

Conference2nd Starting Artificial Intelligence Researchers Symposium
Country/TerritorySpain
CityValencia
Period2004/08/232004/08/24

Subject classification (UKÄ)

  • Computer Science

Fingerprint

Dive into the research topics of 'Reversed planning graphs for relevance heuristics in AI planning'. Together they form a unique fingerprint.

Cite this