TY - GEN
T1 - Reversed planning graphs for relevance heuristics in AI planning
AU - Pettersson, Mats Petter
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
M3 - Paper in conference proceeding
SN - 978-1-58603-484-9
VL - 117
SP - 29
EP - 38
BT - Planning, Scheduling and Constraint Satisfaction: From Theory to Practice
PB - IOS Press
T2 - 2nd Starting Artificial Intelligence Researchers Symposium
Y2 - 23 August 2004 through 24 August 2004
ER -