Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Reversed planning graphs for relevance heuristics in AI planning

Pettersson, Mats Petter LU (2005) 2nd Starting Artificial Intelligence Researchers Symposium 117. p.29-38
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Planning, Scheduling and Constraint Satisfaction: From Theory to Practice
volume
117
pages
29 - 38
publisher
IOS Press
conference name
2nd Starting Artificial Intelligence Researchers Symposium
conference location
Valencia, Spain
conference dates
2004-08-23 - 2004-08-24
external identifiers
  • wos:000228899700004
ISSN
0922-6389
ISBN
978-1-58603-484-9
language
English
LU publication?
yes
id
06b0f56c-fc94-4d97-8266-a1093005a072 (old id 1406298)
date added to LUP
2016-04-01 16:14:51
date last changed
2021-05-05 10:22:14
@inproceedings{06b0f56c-fc94-4d97-8266-a1093005a072,
  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.},
  author       = {Pettersson, Mats Petter},
  booktitle    = {Planning, Scheduling and Constraint Satisfaction: From Theory to Practice},
  isbn         = {978-1-58603-484-9},
  issn         = {0922-6389},
  language     = {eng},
  pages        = {29--38},
  publisher    = {IOS Press},
  title        = {Reversed planning graphs for relevance heuristics in AI planning},
  volume       = {117},
  year         = {2005},
}