@article{Nguyen:2002:PGB:506694.506697,
 author = {Nguyen, XuanLong and Kambhampati, Subbarao and Nigenda, Romeo S.},
 title = {Planning graph as the basis for deriving heuristics for plan synthesis by state space and CSP search},
 journal = {Artificial Intelligence},
 volume = {135},
 issue = {1-2},
 month = {February},
 year = {2002},
 issn = {0004-3702},
 pages = {73--124},
 numpages = {52},
 url = {http://portal.acm.org/citation.cfm?id=506694.506697},
 doi = {10.1016/S0004-3702(01)00158-8},
 acmid = {506697},
 publisher = {Elsevier Science Publishers Ltd.},
 address = {Essex, UK},
 abstract = {Most recent strides in scaling up planning have centered around two competing themes—
disjunctive planners, exemplified by Graphplan, and heuristic state search planners, exemplified by
UNPOP, HSP and HSP-r. In this paper, we present a novel approach for successfully harnessing
the advantages of the two competing paradigms to develop planners that are significantly more
powerful than either of the approaches. Specifically, we show that the polynomial-time planning
graph structure that the Graphplan builds provides a rich substrate for deriving a family of highly
effective heuristics for guiding state space search as well as CSP style search. The main leverage
provided by the planning graph structure is a systematic and graded way to take subgoal interactions
into account in designing state space heuristics. For state space search, we develop several families
of heuristics, some aimed at search speed and others at optimality of solutions, and analyze many
approaches for improving the cost-quality tradeoffs offered by these heuristics. Our normalized
empirical comparisons show that our heuristics handily outperform the existing state space heuristics.
For CSP style search, we describe a novel way of using the planning graph structure to derive highly
effective variable and value ordering heuristics. We show that these heuristics can be used to improve
Graphplan’s own backward search significantly. To demonstrate the effectiveness of our approach vis
a vis the state-of-the-art in plan synthesis, we present AltAlt, a planner literally cobbled together from
the implementations of Graphplan and state search style planners using our theory.We evaluate AltAlt
on the suite of problems used in the recent AIPS-2000 planning competition. The results place AltAlt
in the top tier of the competition planners—outperforming both Graphplan based and heuristic search
based planners.}, 
 url = {altalt-aij-pub.pdf},
 keywords = {CSP, graphplan, heuristics, planning, planning graph}
}

{"_id":{"_str":"51f6bdd759ced8df4400104c"},"__v":39,"authorIDs":["545846792abc8e9f37000b77","54945ae3d2d96cd677001102"],"author_short":["Nguyen, X.","Kambhampati, S.","Nigenda, R. S."],"bibbaseid":"nguyen-kambhampati-nigenda-planninggraphasthebasisforderivingheuristicsforplansynthesisbystatespaceandcspsearch-2002","bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Nguyen"],"firstnames":["XuanLong"],"suffixes":[]},{"propositions":[],"lastnames":["Kambhampati"],"firstnames":["Subbarao"],"suffixes":[]},{"propositions":[],"lastnames":["Nigenda"],"firstnames":["Romeo","S."],"suffixes":[]}],"title":"Planning graph as the basis for deriving heuristics for plan synthesis by state space and CSP search","journal":"Artificial Intelligence","volume":"135","issue":"1-2","month":"February","year":"2002","issn":"0004-3702","pages":"73–124","numpages":"52","url":"altalt-aij-pub.pdf","doi":"10.1016/S0004-3702(01)00158-8","acmid":"506697","publisher":"Elsevier Science Publishers Ltd.","address":"Essex, UK","abstract":"Most recent strides in scaling up planning have centered around two competing themes— disjunctive planners, exemplified by Graphplan, and heuristic state search planners, exemplified by UNPOP, HSP and HSP-r. In this paper, we present a novel approach for successfully harnessing the advantages of the two competing paradigms to develop planners that are significantly more powerful than either of the approaches. Specifically, we show that the polynomial-time planning graph structure that the Graphplan builds provides a rich substrate for deriving a family of highly effective heuristics for guiding state space search as well as CSP style search. The main leverage provided by the planning graph structure is a systematic and graded way to take subgoal interactions into account in designing state space heuristics. For state space search, we develop several families of heuristics, some aimed at search speed and others at optimality of solutions, and analyze many approaches for improving the cost-quality tradeoffs offered by these heuristics. Our normalized empirical comparisons show that our heuristics handily outperform the existing state space heuristics. For CSP style search, we describe a novel way of using the planning graph structure to derive highly effective variable and value ordering heuristics. We show that these heuristics can be used to improve Graphplan’s own backward search significantly. To demonstrate the effectiveness of our approach vis a vis the state-of-the-art in plan synthesis, we present AltAlt, a planner literally cobbled together from the implementations of Graphplan and state search style planners using our theory.We evaluate AltAlt on the suite of problems used in the recent AIPS-2000 planning competition. The results place AltAlt in the top tier of the competition planners—outperforming both Graphplan based and heuristic search based planners.","keywords":"CSP, graphplan, heuristics, planning, planning graph","bibtex":"@article{Nguyen:2002:PGB:506694.506697,\n author = {Nguyen, XuanLong and Kambhampati, Subbarao and Nigenda, Romeo S.},\n title = {Planning graph as the basis for deriving heuristics for plan synthesis by state space and CSP search},\n journal = {Artificial Intelligence},\n volume = {135},\n issue = {1-2},\n month = {February},\n year = {2002},\n issn = {0004-3702},\n pages = {73--124},\n numpages = {52},\n url = {http://portal.acm.org/citation.cfm?id=506694.506697},\n doi = {10.1016/S0004-3702(01)00158-8},\n acmid = {506697},\n publisher = {Elsevier Science Publishers Ltd.},\n address = {Essex, UK},\n abstract = {Most recent strides in scaling up planning have centered around two competing themes—\ndisjunctive planners, exemplified by Graphplan, and heuristic state search planners, exemplified by\nUNPOP, HSP and HSP-r. In this paper, we present a novel approach for successfully harnessing\nthe advantages of the two competing paradigms to develop planners that are significantly more\npowerful than either of the approaches. Specifically, we show that the polynomial-time planning\ngraph structure that the Graphplan builds provides a rich substrate for deriving a family of highly\neffective heuristics for guiding state space search as well as CSP style search. The main leverage\nprovided by the planning graph structure is a systematic and graded way to take subgoal interactions\ninto account in designing state space heuristics. For state space search, we develop several families\nof heuristics, some aimed at search speed and others at optimality of solutions, and analyze many\napproaches for improving the cost-quality tradeoffs offered by these heuristics. Our normalized\nempirical comparisons show that our heuristics handily outperform the existing state space heuristics.\nFor CSP style search, we describe a novel way of using the planning graph structure to derive highly\neffective variable and value ordering heuristics. We show that these heuristics can be used to improve\nGraphplan’s own backward search significantly. To demonstrate the effectiveness of our approach vis\na vis the state-of-the-art in plan synthesis, we present AltAlt, a planner literally cobbled together from\nthe implementations of Graphplan and state search style planners using our theory.We evaluate AltAlt\non the suite of problems used in the recent AIPS-2000 planning competition. The results place AltAlt\nin the top tier of the competition planners—outperforming both Graphplan based and heuristic search\nbased planners.}, \n url = {altalt-aij-pub.pdf},\n keywords = {CSP, graphplan, heuristics, planning, planning graph}\n} \n\n","author_short":["Nguyen, X.","Kambhampati, S.","Nigenda, R. S."],"key":"Nguyen:2002:PGB:506694.506697","id":"Nguyen:2002:PGB:506694.506697","bibbaseid":"nguyen-kambhampati-nigenda-planninggraphasthebasisforderivingheuristicsforplansynthesisbystatespaceandcspsearch-2002","role":"author","urls":{"Paper":"yalma.fime.uanl.mx/~romeo/publications/altalt-aij-pub.pdf"},"keyword":["CSP","graphplan","heuristics","planning","planning graph"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"yalma.fime.uanl.mx/~romeo/publications/romeo-sanchez.bib","downloads":0,"keywords":["csp","graphplan","heuristics","planning","planning graph"],"search_terms":["planning","graph","basis","deriving","heuristics","plan","synthesis","state","space","csp","search","nguyen","kambhampati","nigenda"],"title":"Planning graph as the basis for deriving heuristics for plan synthesis by state space and CSP search","title_words":["planning","graph","basis","deriving","heuristics","plan","synthesis","state","space","csp","search"],"year":2002,"dataSources":["hFEMyDFMRXsJxPXm4"]}