TY - GEN
T1 - Distance-based Goal-ordering heuristics for Graphplan
AU - Kambhampati, Subbarao
AU - Nigenda, Romeo Sanchez
N1 - Funding Information: Authors’ names listed alphabetically. Binh Minh Do, Jillian Nottingham, Xuan Long Nguyen, Biplav Srivastava and Terry Zim-merman have all contributed significantly to this work through discussions and feedback. This research is supported in part by NSF young investigator award (NYI) IRI-9457634, ARPA/Rome Laboratory planning initiative grant F30602-95-C-0247, Army AASERT grant DAAH04-96-1-0247, AFOSR grant F20602-98-1-0182 and NSF grant IRI-9801676. Publisher Copyright: Copyright © 2000, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2000
Y1 - 2000
N2 - We will discuss the shortcomings of known variable and value ordering strategies for Graphplan’s backward search phase, and propose a novel strategy that is based on a notion of the difficulty of achieving the corresponding subgoal. The difficulty of achievement is quantified in terms of the structure of the planning graph itself–specifically, the earliest level of the planning-graph at which that subgoal appears. We will present empirical results showing the surprising effectiveness of this simple heuristic on benchmark problems. We will end by contrasting the way distance-based heuristics are used in Graphplan and state-search planners like UNPOP, HSP and HSP-R.
AB - We will discuss the shortcomings of known variable and value ordering strategies for Graphplan’s backward search phase, and propose a novel strategy that is based on a notion of the difficulty of achieving the corresponding subgoal. The difficulty of achievement is quantified in terms of the structure of the planning graph itself–specifically, the earliest level of the planning-graph at which that subgoal appears. We will present empirical results showing the surprising effectiveness of this simple heuristic on benchmark problems. We will end by contrasting the way distance-based heuristics are used in Graphplan and state-search planners like UNPOP, HSP and HSP-R.
UR - http://www.scopus.com/inward/record.url?scp=85166243546&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85166243546&partnerID=8YFLogxK
M3 - Conference contribution
T3 - Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000
SP - 315
EP - 322
BT - Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000
PB - AAAI press
T2 - 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000
Y2 - 14 April 2000 through 17 April 2000
ER -