Thumbnail
Access Restriction
Open

Author Nebel, Bernhard
Source CiteSeerX
Content type Text
Publisher Springer-Verlag
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Formal Meaning ♦ Particular Formalism ♦ Conditional Effect ♦ Expressive Power ♦ Recent Approach ♦ Large Family ♦ Relative Expressive Power ♦ Theoretical Tool ♦ Planning Formalism ♦ Compilation Scheme ♦ Expressive Planning Formalism ♦ Propositional Planning Formalism
Description . The recent approaches of extending the graphplan algorithm to handle more expressive planning formalisms raise the question of what the formal meaning of "expressive power" is. We formalize the intuition that expressive power is a measure of how concisely planning domains and plans can be expressed in a particular formalism by introducing the notion of "compilation schemes" between planning formalisms. Using this notion, we analyze the expressive power of a large family of propositional planning formalisms and show, e.g., that Gazen and Knoblock's approach to compiling conditional effects away is optimal. 1 Introduction The recent approaches of extending the graphplan algorithm [3] to handle more expressive planning formalisms [1,9,10,12] raise the question of what the formal meaning of expressive power is. In order to address the problem of measuring the relative expressive power of planning formalisms, we start with the intuition that a formalism X is at least as expressive as an...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1999-01-01
Publisher Institution KI-99: Advances in Arti Intelligence