Representing Action and Change by Logic Programs

@article{gelfond93representing, abstract = {We represent properties of actions in a logic programming language that uses both classical negation and negation as failure. The method is applicable to temporal projection problems with incomplete information, as well as to reasoning about the past. It is proved to be sound relative to a semantics of action based on states and transition functions. 1 Introduction This paper extends the work of Eshghi and Kowalski [6], Evans [7] and Apt and Bezem [1] on representing properties of actions in...}, author = {Gelfond, Michael and Lifschitz, Vladimir }, citeulike-article-id = {322872}, comment = {The paper introduces \$\mathcal A\$, a simple declarative propositional language for describing action theories using \emph{value propositions} and \emph{effect propositions}. The first capture the truth value of a fluent literal F after a certain action history: \[F \textbf{ after } A\_1;..;A\_n\] or \[\textbf{initially } F\] and the latter describe the effect of an action \$A\$ on a fluent literal \$F\$ when some preconditions hold: \[A \textbf{ causes } F \textbf{ if } P\_1,...,P\_m\] The semantics of \$\mathcal A\$ are based on the notion of a state \$\sigma\$ and a transition function \$\Phi\$. A state is a maximal consistent set of positive fluent literals and \$\Phi\$ maps state-action pairs to states. Truth of propositions in a structure \$(\sigma,\Phi)\$ is based on a built-in default reasoning \cite{reiter80default} \cite{mccarthy80circumscription}, mechanism according to which fluents that are not affected by some effect proposition at state \$\sigma\$ remain unaffected at state \$\Phi(A,\sigma)\$. Entailment is defined as usual: a proposition in entailed by a set of formulas \$D\$ if it is true in all models of \$D\$. Because of the definition of truth in a structure the entailment relation is nonmonotonic. \$\mathcal A\$ can represent incomplete information in the initial state only, by leaving fluent literals unspecified. There is some brief discussion about extending this to using disjunctions and also incorporating nondeterministic actions. The main result of the paper is a soundness result for implementing \$\mathcal A\$ action theories as \emph{extended logic programs} \cite{gelfond91classical} in the following sense: if program \$\pi D\$ succeeds in proving query \$\pi P\$ then \$D\$ entails \$P\$. Extended logic programs feature classical negation as well as negation as failure and their semantics is based on \emph{answer sets}. The result holds for theories that mention at most one effect proposition for each action-fluent pair and the resulting program includes one clause for each value propostition and \$2n +2\$ clauses for each effect proposition, where \$n\$ is the number of preconditions. Concluding, \$\mathcal A\$ is a limited language designed so that to capture a limited class of action theories. Some of its basic limitations include that it is propositional, allows relational fluents only and does not feature disjunction. We can say that the expressiveness of \$\mathcal A\$ can be characterised by a class of situation calculus basic action theories \cite{reiter91simple}. Value propositions are essentially specifying the initial situation and effect propositions are effect axioms. In basic action theories the solution to the frame problem is based on the completeness assumption that apart from the sufficient conditions the effect axioms also capture the necessary conditions for fluent change. In \$\mathcal A\$ a similar assumption is enforced, but in the semantics level. So, \$\mathcal A\$ is nonmonotonic in a very specific way which is equivalent to semantically simulating the situation calculus successor state axiom which corresponds to the set the effect axioms for each fluent each time.}, journal = {Journal of Logic Programming}, keywords = {ai, answer\_set, depth, frame\_problem, incomplete\_knowledge, logic, logic\_programming, nonmonotonic, reasoning\_about\_action}, number = {2/3\&4}, pages = {301--321}, posted-at = {2005-09-16 19:41:56}, priority = {0}, title = {Representing Action and Change by Logic Programs}, url = {http://citeseer.ist.psu.edu/gelfond93representing.html}, volume = {17}, year = {1993} }

TY - JOUR ID - gelfond93representing L3 - citeulike-article-id:322872 TI - Representing Action and Change by Logic Programs JF - Journal of Logic Programming VL - 17 IS - 2/3&4 SP - 301 EP - 321 N2 - We represent properties of actions in a logic programming language that uses both classical negation and negation as failure. The method is applicable to temporal projection problems with incomplete information, as well as to reasoning about the past. It is proved to be sound relative to a semantics of action based on states and transition functions. 1 Introduction This paper extends the work of Eshghi and Kowalski [6], Evans [7] and Apt and Bezem [1] on representing properties of actions in... KW - ai KW - answer_set KW - depth KW - frame_problem KW - incomplete_knowledge KW - logic KW - logic_programming KW - nonmonotonic KW - reasoning_about_action N1 - The paper introduces $\mathcal A$, a simple declarative propositional language for describing action theories using \emph{value propositions} and \emph{effect propositions}. The first capture the truth value of a fluent literal F after a certain action history: \[F \textbf{ after } A_1;..;A_n\] or \[\textbf{initially } F\] and the latter describe the effect of an action $A$ on a fluent literal $F$ when some preconditions hold: \[A \textbf{ causes } F \textbf{ if } P_1,...,P_m\] The semantics of $\mathcal A$ are based on the notion of a state $\sigma$ and a transition function $\Phi$. A state is a maximal consistent set of positive fluent literals and $\Phi$ maps state-action pairs to states. Truth of propositions in a structure $(\sigma,\Phi)$ is based on a built-in default reasoning \cite{reiter80default} \cite{mccarthy80circumscription}, mechanism according to which fluents that are not affected by some effect proposition at state $\sigma$ remain unaffected at state $\Phi(A,\sigma)$. Entailment is defined as usual: a proposition in entailed by a set of formulas $D$ if it is true in all models of $D$. Because of the definition of truth in a structure the entailment relation is nonmonotonic. $\mathcal A$ can represent incomplete information in the initial state only, by leaving fluent literals unspecified. There is some brief discussion about extending this to using disjunctions and also incorporating nondeterministic actions. The main result of the paper is a soundness result for implementing $\mathcal A$ action theories as \emph{extended logic programs} \cite{gelfond91classical} in the following sense: if program $\pi D$ succeeds in proving query $\pi P$ then $D$ entails $P$. Extended logic programs feature classical negation as well as negation as failure and their semantics is based on \emph{answer sets}. The result holds for theories that mention at most one effect proposition for each action-fluent pair and the resulting program includes one clause for each value propostition and $2n +2$ clauses for each effect proposition, where $n$ is the number of preconditions. Concluding, $\mathcal A$ is a limited language designed so that to capture a limited class of action theories. Some of its basic limitations include that it is propositional, allows relational fluents only and does not feature disjunction. We can say that the expressiveness of $\mathcal A$ can be characterised by a class of situation calculus basic action theories \cite{reiter91simple}. Value propositions are essentially specifying the initial situation and effect propositions are effect axioms. In basic action theories the solution to the frame problem is based on the completeness assumption that apart from the sufficient conditions the effect axioms also capture the necessary conditions for fluent change. In $\mathcal A$ a similar assumption is enforced, but in the semantics level. So, $\mathcal A$ is nonmonotonic in a very specific way which is equivalent to semantically simulating the situation calculus successor state axiom which corresponds to the set the effect axioms for each fluent each time. AU - Gelfond, Michael AU - Lifschitz, Vladimir PY - 1993/// UR - http://citeseer.ist.psu.edu/gelfond93representing.html ER -