@inproceedings {icaps16-201,
    track    = {​Main Track},
    title    = {Traps, Invariants, and Dead-Ends},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13190},
    author   = {Nir Lipovetzky and  Christian Muise and  Hector Geffner},
    abstract = {We consider the problem of deriving formulas that capture traps, invariants, and dead-ends in classical planning through polynomial forms of preprocessing. An invariant is a formula that is true in the initial state and in all reachable states. A trap is a conditional invariant: once a state is reached that makes the trap true, all the states that are reachable from it will satisfy the trap formula as well. Finally, dead-ends are formulas that are satisfied in states that make the goal unreachable. We introduce a preprocessing algorithm that computes traps in k-DNF form that is exponential in the k parameter, and show how the algorithm can be used to precompute invariants and dead-ends. We report also preliminary tests that illustrate the effectiveness of the preprocessing algorithm for identifying dead-end states, and compare it with the identification that follows from the use of the h1 and h2 heuristics that cannot be preprocessed, and must be computed at run time.},
    keywords = {Classical planning,Model-based reasoning,Knowledge engineering for planning and scheduling}
}

{"_id":"GRTFTLfSN7z4ga88g","bibbaseid":"lipovetzky-muise-geffner-trapsinvariantsanddeadends","downloads":0,"creationDate":"2016-03-09T03:04:32.875Z","title":"Traps, Invariants, and Dead-Ends","author_short":["Lipovetzky, N.","Muise, C.","Geffner, H."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","track":"​Main Track","title":"Traps, Invariants, and Dead-Ends","url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13190","author":[{"firstnames":["Nir"],"propositions":[],"lastnames":["Lipovetzky"],"suffixes":[]},{"firstnames":["Christian"],"propositions":[],"lastnames":["Muise"],"suffixes":[]},{"firstnames":["Hector"],"propositions":[],"lastnames":["Geffner"],"suffixes":[]}],"abstract":"We consider the problem of deriving formulas that capture traps, invariants, and dead-ends in classical planning through polynomial forms of preprocessing. An invariant is a formula that is true in the initial state and in all reachable states. A trap is a conditional invariant: once a state is reached that makes the trap true, all the states that are reachable from it will satisfy the trap formula as well. Finally, dead-ends are formulas that are satisfied in states that make the goal unreachable. We introduce a preprocessing algorithm that computes traps in k-DNF form that is exponential in the k parameter, and show how the algorithm can be used to precompute invariants and dead-ends. We report also preliminary tests that illustrate the effectiveness of the preprocessing algorithm for identifying dead-end states, and compare it with the identification that follows from the use of the h1 and h2 heuristics that cannot be preprocessed, and must be computed at run time.","keywords":"Classical planning,Model-based reasoning,Knowledge engineering for planning and scheduling","bibtex":"@inproceedings {icaps16-201,\r\n track = {​Main Track},\r\n title = {Traps, Invariants, and Dead-Ends},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13190},\r\n author = {Nir Lipovetzky and Christian Muise and Hector Geffner},\r\n abstract = {We consider the problem of deriving formulas that capture traps, invariants, and dead-ends in classical planning through polynomial forms of preprocessing. An invariant is a formula that is true in the initial state and in all reachable states. A trap is a conditional invariant: once a state is reached that makes the trap true, all the states that are reachable from it will satisfy the trap formula as well. Finally, dead-ends are formulas that are satisfied in states that make the goal unreachable. We introduce a preprocessing algorithm that computes traps in k-DNF form that is exponential in the k parameter, and show how the algorithm can be used to precompute invariants and dead-ends. We report also preliminary tests that illustrate the effectiveness of the preprocessing algorithm for identifying dead-end states, and compare it with the identification that follows from the use of the h1 and h2 heuristics that cannot be preprocessed, and must be computed at run time.},\r\n keywords = {Classical planning,Model-based reasoning,Knowledge engineering for planning and scheduling}\r\n}\r\n\r\n","author_short":["Lipovetzky, N.","Muise, C.","Geffner, H."],"key":"icaps16-201","id":"icaps16-201","bibbaseid":"lipovetzky-muise-geffner-trapsinvariantsanddeadends","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13190"},"keyword":["Classical planning","Model-based reasoning","Knowledge engineering for planning and scheduling"],"metadata":{"authorlinks":{}}},"search_terms":["traps","invariants","dead","ends","lipovetzky","muise","geffner"],"keywords":["classical planning","model-based reasoning","knowledge engineering for planning and scheduling"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}