@inproceedings {icaps16-4,
    track    = {​Main Track},
    title    = {Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13123},
    author   = {Daniel Höller and  Gregor Behnke and  Pascal Bercher and  Susanne Biundo},
    abstract = {From a theoretical perspective, judging the expressivity of planning formalisms helps to understand the relationship of different representations and to infer theoretical properties. From a practical point of view, it is important to be able to choose the best formalism for a problem at hand, or to ponder the consequences of introducing new representation features. Most work on the expressivity is based either on compilation approaches, or on the computational complexity of the plan existence problem. Recently, a new notion of expressivity was introduced. It is based on comparing the structural complexity of the set of solutions to a planning problem by interpreting the set as a formal language and classifying it with respect to the Chomsky hierarchy. This is a more direct measure than the plan existence problem and enables also the comparison of formalisms that can not be compiled into each other. While existing work on that last approach focused on different hierarchical problem classes, this paper investigates STRIPS with and without conditional effects; though we also tighten some existing results on hierarchical formalisms. Our second contribution is a discussion on the language-based expressivity measure with respect to the other approaches.},
    keywords = {Classical planning,HTN and knowledge-based planning,Complexity analysis}
}

{"_id":"CQn3oyg7dHQ7SSd4w","bibbaseid":"hller-behnke-bercher-biundo-assessingtheexpressivityofplanningformalismsthroughthecomparisontoformallanguages","downloads":0,"creationDate":"2016-03-09T03:04:32.919Z","title":"Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages","author_short":["Höller, D.","Behnke, G.","Bercher, P.","Biundo, S."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","track":"​Main Track","title":"Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages","url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13123","author":[{"firstnames":["Daniel"],"propositions":[],"lastnames":["Höller"],"suffixes":[]},{"firstnames":["Gregor"],"propositions":[],"lastnames":["Behnke"],"suffixes":[]},{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]},{"firstnames":["Susanne"],"propositions":[],"lastnames":["Biundo"],"suffixes":[]}],"abstract":"From a theoretical perspective, judging the expressivity of planning formalisms helps to understand the relationship of different representations and to infer theoretical properties. From a practical point of view, it is important to be able to choose the best formalism for a problem at hand, or to ponder the consequences of introducing new representation features. Most work on the expressivity is based either on compilation approaches, or on the computational complexity of the plan existence problem. Recently, a new notion of expressivity was introduced. It is based on comparing the structural complexity of the set of solutions to a planning problem by interpreting the set as a formal language and classifying it with respect to the Chomsky hierarchy. This is a more direct measure than the plan existence problem and enables also the comparison of formalisms that can not be compiled into each other. While existing work on that last approach focused on different hierarchical problem classes, this paper investigates STRIPS with and without conditional effects; though we also tighten some existing results on hierarchical formalisms. Our second contribution is a discussion on the language-based expressivity measure with respect to the other approaches.","keywords":"Classical planning,HTN and knowledge-based planning,Complexity analysis","bibtex":"@inproceedings {icaps16-4,\r\n track = {​Main Track},\r\n title = {Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13123},\r\n author = {Daniel Höller and Gregor Behnke and Pascal Bercher and Susanne Biundo},\r\n abstract = {From a theoretical perspective, judging the expressivity of planning formalisms helps to understand the relationship of different representations and to infer theoretical properties. From a practical point of view, it is important to be able to choose the best formalism for a problem at hand, or to ponder the consequences of introducing new representation features. Most work on the expressivity is based either on compilation approaches, or on the computational complexity of the plan existence problem. Recently, a new notion of expressivity was introduced. It is based on comparing the structural complexity of the set of solutions to a planning problem by interpreting the set as a formal language and classifying it with respect to the Chomsky hierarchy. This is a more direct measure than the plan existence problem and enables also the comparison of formalisms that can not be compiled into each other. While existing work on that last approach focused on different hierarchical problem classes, this paper investigates STRIPS with and without conditional effects; though we also tighten some existing results on hierarchical formalisms. Our second contribution is a discussion on the language-based expressivity measure with respect to the other approaches.},\r\n keywords = {Classical planning,HTN and knowledge-based planning,Complexity analysis}\r\n}\r\n\r\n","author_short":["Höller, D.","Behnke, G.","Bercher, P.","Biundo, S."],"key":"icaps16-4","id":"icaps16-4","bibbaseid":"hller-behnke-bercher-biundo-assessingtheexpressivityofplanningformalismsthroughthecomparisontoformallanguages","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13123"},"keyword":["Classical planning","HTN and knowledge-based planning","Complexity analysis"],"metadata":{"authorlinks":{}}},"search_terms":["assessing","expressivity","planning","formalisms","through","comparison","formal","languages","höller","behnke","bercher","biundo"],"keywords":["classical planning","htn and knowledge-based planning","complexity analysis"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}