|
|
|
|
|
|
|
Representing and reasoning about actions
supports |
|
Predicting the evolution of the world |
|
Planning (e.g., robots) |
|
User modeling |
|
Communication (e.g., speech acts) |
|
Diagnosis and repair |
|
|
|
There are several formalisms for reasoning about
action |
|
Some logic-based |
|
E.g., situation calculus, event calculus,
|
|
Some tailored to specific planning procedures |
|
E.g., STRIPS, ... |
|
|
|
|
|
|
Problems that plague formal representations of
action: |
|
The Ramification Problem |
|
How to characterize what changes after an action
is performed |
|
The Frame Problem |
|
How to characterize what does not change after
an action is performed |
|
The Qualification Problem |
|
How to characterize the necessary and sufficient
conditions for actions |
|
Solution criteria: |
|
Formal |
|
Parsimony |
|
Elaboration tolerance |
|
Flexibility |
|
... |
|
|
|
|
|
|
First-order predicate logic language for
representing changing worlds |
|
Classes: Action, State |
|
Functions: Do |
|
(Do ?a ?s) is the state resulting from
performing action ?a in state ?s |
|
Relations: Possible |
|
(Possible ?action ?state) is true when the
action can be performed in the state |
|
fluents: relations whose truth value changes
from state to state |
|
E.g., (On Pump s) (Steam s)
(Abnormal boiler s) |
|
Actions usually denoted by function terms |
|
E.g., (Turn-On Pump) (Fix Pump) |
|
World dynamics specified by effect axioms |
|
E.g., (=> (Possible (Turn-On Pump) ?state) |
|
(On Pump (Do (Turn-On Pump) ?state))) |
|
Preconditions for actions specified by necessary
conditions for actions |
|
E.g., (=> (Possible (Fix Pump) ?state) (not
(On Pump ?state))) |
|
|
|
|
|
|
|
|
To represent the dynamics of a system, we
include |
|
Effect axioms for each action |
|
(=> (Possible (Turn-On Pump) ?s) (On Pump (Do (Turn-On Pump) ?s))) |
|
(=> (Possible (Turn-Off Pump) ?s) (not (On Pump (Do (Turn-Off Pump)
?s)))) |
|
(=> (Possible (Burn-Out Pump) ?s) (Broken Pump (Do (Burn-Out Pump) ?s))) |
|
(=> (Possible (Fix Pump) ?s) (not (Broken Pump (Do (Fix Pump) ?s)))) |
|
|
|
Necessary conditions for each action |
|
(=> (Possible (Fix Pump) ?s) (not (On Pump ?s))) |
|
|
|
What is known of the initial situation, S0 |
|
(On Pump S0) (not (Abnormal Boiler S0 ))
|
|
Unique names assumption for actions |
|
(Turn-Off ?x) Ή (Burn-Out ?x) Ή ... |
|
|
|
|
|
Assume (for simplicity) that S0 is
completely specified |
|
E.g., (On Pump S0) (not (Broken Pump S0 )) (On Boiler S0) (not (Broken Boiler S0)) |
|
Suppose the action (Turn-Off Pump) is
performed, transitioning the system to a new situation, (Do (Turn-Off
Pump) S0), which we will abbreviate to S1. |
|
From the effect axiom: |
|
(=> (Possible (Turn-Off Pump) ?s) (not (On
Pump (Do (Turn-Off Pump) ?s)))) |
|
we know that the pump will be not on in S1, |
|
but what is the truth value of other
fluents? |
|
Intended Model |
|
(not (On Pump S1)) (not (Broken Pump S1 )) (On Boiler S1) (not (Broken Boiler S1)) |
|
Numerous Unintended Models |
|
(not (On Pump S1)) (not (Broken Pump S1)) (On Boiler S1) (Broken Boiler S1) |
|
(not (On Pump S1)) (not (Broken Pump S1)) (not (On Boiler S1)) (Broken Boiler S1) |
|
|
|
|
|
|
|
|
Desired Convention: Inertia, i.e., minimize change |
|
Nothing changes unless our effect axioms say
that it must. |
|
Solution 1:
Frame Axioms |
|
Add frame axioms to characterize the non-effects
of actions |
|
E.g., (=>
(Possible (Turn-On Pump) ?s) (not
(On Boiler ?s)) |
|
(not (On Boiler (Do (Turn-On Pump) ?s)))) |
|
(=> (Possible (Turn-On Pump) ?s) (On Boiler ?s) |
|
(On Boiler (Do (Turn-On Pump) ?s))) |
|
(=> (Possible (Turn-On Pump) ?s) (Broken Pump ?s) |
|
(Broken Pump (Do (Turn-On Pump) ?s))) |
|
... |
|
Problem:
Not parsimonious |
|
There are many more non-effects of actions than
effects |
|
n actions and m fluents implies approximately nxm
frame axioms! |
|
|
|
|
|
|
Solution 2:
Successor State Axioms |
|
Goal: For each fluent F and each sequence of
arguments x1,
,xn for F, provide in the knowledge base an axiom of the
form: |
|
(=> (Possible ?a ?s) (<=> (F x1
xn
(Do ?a ?s))
) |
|
Step 1 Provide general effect axioms for each
fluent F and each sequence of arguments x1,
,xn for F as follows: |
|
Let ActionF[x1,
,xn]+ and ActionF[x1,
,xn]- be
subclasses of Action such that: |
|
[1]
(=> (Possible ?a ?s)
(=> (Instance-Of ?a ActionF[x1,
,xn]+) |
|
(F x1
xn
(Do ?a ?s))))) |
|
[2]
(=> (Possible ?a ?s)
(=> (Instance-Of ?a ActionF[x1,
,xn]-) |
|
(not (F x1
xn (Do ?a ?s)))) |
|
Note that axiom [2] can be rewritten as: |
|
[2]
(=> (Possible ?a ?s)
(=> (F x1
xn (Do ?a ?s)) |
|
(not
(Instance-Of ?a ActionF[x1,
,xn]-)))) |
|
|
|
|
|
|
Solution 2:
Successor State Axioms |
|
Goal: Provide in the knowledge base an axiom of
the form: |
|
(=> (Possible ?a ?s) (<=> (On Pump (Do
?a ?s))
) |
|
Step 1 Provide general effect axioms for each
fluent F and each sequence of arguments x1,
,xn for F as follows: |
|
Let ActionF[x1,
,xn]+ and ActionF[x1,
,xn]- be
subclasses of Action such that: |
|
[1]
(=> (Possible ?a ?s)
(=> (Instance-Of ?a ActionF[x1,
,xn]+) (F x1
xn (Do ?a ?s))))) |
|
[2]
(=> (Possible ?a ?s)
(=> (Instance-Of ?a ActionF[x1,
,xn]-) (not (F x1
xn (Do ?a ?s)))) |
|
(Turn-On Pump) is the only instance of
ActionOn[Pump]+ |
|
(Turn-Off Pump) is the only instance of ActionOn[Pump]- |
|
[1E] (=> (Possible ?a ?s) (=> (= ?a (Turn-On Pump)) (On Pump
(Do ?a ?s))) |
|
[2E] (=> (Possible ?a
?s) (=> (= ?a (Turn-Off Pump))
(not (On Pump (Do ?a ?s)))) |
|
Note that axiom [2E] can be rewritten as: |
|
[2E] (=> (Possible ?a
?s) (=> (On Pump (Do ?a ?s))
(not (= ?a (Turn-Off Pump))))) |
|
|
|
|
|
Step 2 Make a Completeness Assumption |
|
Assume the effect axioms characterize all the
conditions under which an action can lead to the fluent becoming true or
false in the successor state |
|
Step 3 Add Explanation Closure Axioms for each
fluent F and each sequence of arguments x1,
,xn for F as follows: |
|
[3]
(=> (Possible ?a ?s)
(=> (not (F x1
xn
?s)) (F x1
xn (Do ?a ?s)) |
|
(Instance-Of
?a ActionF[x1,
,xn]+))) |
|
[4]
(=> (Possible ?a ?s)
(=> (F x1
xn ?s) (not (F x1
xn (Do ?a ?s))) |
|
(Instance-Of
?a ActionF[x1,
,xn]-)) |
|
Note that axioms [3] and [4] can be rewritten
as: |
|
[3]
(=> (Possible ?a ?s)
(=> (F x1
xn (Do ?a
?s)) |
|
(or (Instance-Of ?a ActionF[x1,
,xn]+) (F x1
xn ?s))) |
|
[4]
(=> (Possible ?a ?s)
(=> (F x1
xn ?s) (not (Instance-Of ?a
ActionF[x1,
,xn]-)) |
|
(F x1
xn
(Do ?a ?s)))) |
|
|
|
|
|
Step 2 Make a Completeness Assumption |
|
Step 3 Add Explanation Closure Axioms for each
fluent F and each sequence of arguments x1,
,xn for F as follows: |
|
[3]
(=> (Possible ?a ?s)
(=> (not (F x1
xn
?s)) (F x1
xn (Do ?a ?s)) |
|
(Instance-Of
?a ActionF[x1,
,xn]+))) |
|
[4]
(=> (Possible ?a ?s)
(=> (F x1
xn ?s) (not (F x1
xn (Do ?a ?s))) |
|
(Instance-Of
?a ActionF[x1,
,xn]-)) |
|
[3E] (=> (Possible ?a ?s) (=>
(not (On Pump ?s)) (On Pump
(Do ?a ?s)) (= ?a (Turn-On Pump)))) |
|
[4E] (=> (Possible ?a ?s) (=>
(On Pump ?s) (not (On Pump
(Do ?a ?s))) (= ?a (Turn-Off
Pump)))) |
|
Note that axioms [3E] and [4E] can be rewritten
as: |
|
[3E]
(=> (Possible ?a ?s)
(=> (On Pump (Do ?a ?s)) |
|
(or (= ?a (Turn-On Pump)) (On Pump ?s)))) |
|
[4E]
(=> (Possible ?a ?s)
(=> (On Pump ?s) (not
(= ?a (Turn-Off Pump))) |
|
(On Pump
(Do ?a ?s)))) |
|
|
|
|
|
Step 4 Rewrite axioms as successor state
axioms |
|
Sufficient conditions for (F x1
xn (Do ?a
?s)): |
|
[1]
(=> (Possible ?a ?s)
(=> (Instance-Of ?a ActionF[x1,
,xn]+) |
|
(F x1
xn (Do
?a ?s))))) |
|
[4]
(=> (Possible ?a ?s)
(=> (F x1
xn ?s) (not (Instance-Of ?a
ActionF[x1,
,xn]-)) |
|
(F x1
xn
(Do ?a ?s)))) |
|
[5]
(=> (Possible ?a ?s) |
|
(=> (or (Instance-Of ?a ActionF[x1,
,xn]+) |
|
(and
(F x1
xn ?s) (not
(Instance-Of ?a ActionF[x1,
,xn]-))) |
|
(F x1
xn (Do ?a ?s)))) {[1],[4]} |
|
|
|
|
|
|
|
Step 4 Rewrite axioms as successor state
axioms |
|
Sufficient conditions for (On Pump (Do ?a ?s)): |
|
[1E]
(=> (Possible ?a ?s)
(=> (= ?a (Turn-On Pump)) |
|
(On Pump
(Do ?a ?s))) |
|
[4E]
(=> (Possible ?a ?s)
(=> (On Pump ?s) (not
(= ?a (Turn-Off Pump))) |
|
(On Pump
(Do ?a ?s)))) |
|
[5E]
(=> (Possible ?a ?s) |
|
(=> (or (= ?a (Turn-On Pump)) |
|
(and (On Pump ?s) (not (= ?a
(Turn-Off Pump))))) |
|
(On Pump (Do ?a ?s)))) {[1E],[4E]} |
|
|
|
|
|
|
|
Necessary conditions for (F x1
xn (Do ?a ?s)): |
|
[2] (=> (Possible ?a
?s) (=> (F x1
xn (Do ?a ?s)) |
|
(not
(Instance-Of ?a ActionF[x1,
,xn]-)))) |
|
[3] (=> (Possible ?a
?s) (=> (F x1
xn (Do ?a ?s)) |
|
(or (Instance-Of ?a
ActionF[x1,
,xn]+) (F x1
xn
?s)))) |
|
[6] (=> (Possible ?a ?s) |
|
(=>
(F x1
xn (Do ?a ?s)) |
|
(and (not (Instance-Of ?a
ActionF[x1,
,xn]-)) |
|
(or (Instance-Of ?a ActionF[x1,
,xn]+) (F x1
xn ?s))))) {[2],[3]} |
|
[7] (=> (Possible ?a ?s) |
|
(=>
(F x1
xn (Do ?a ?s)) |
|
(or (and (not (Instance-Of ?a
ActionF[x1,
,xn]-)) |
|
(Instance-Of ?a
ActionF[x1,
,xn]+)) |
|
(and (not (Instance-Of ?a
ActionF[x1,
,xn]-)) (F x1
xn ?s))))) {[6]} |
|
[8] (=> (Possible ?a ?s) |
|
(=>
(F x1
xn (Do ?a ?s)) |
|
(or (Instance-Of ?a ActionF[x1,
,xn]+) |
|
(and (F x1
xn ?s) (not
(Instance-Of ?a ActionF[x1,
,xn]-)))))) {[7]} |
|
|
|
|
|
Necessary conditions for (On Pump (Do ?a ?s)): |
|
[2E] (=> (Possible ?a
?s) (=> (On Pump (Do ?a ?s))
(not (= ?a (Turn-Off Pump))))) |
|
[3E] (=> (Possible ?a
?s) (=> (On Pump (Do ?a ?s)) |
|
(or (= ?a (Turn-On
Pump)) (On Pump ?s)))) |
|
[6E] (=> (Possible ?a
?s) |
|
(=>
(On Pump (Do ?a ?s)) |
|
(and (not (= ?a (Turn-Off Pump))) |
|
(or (= ?a (Turn-On Pump)) (On Pump ?s))))) {[2E],[3E]} |
|
[7E] (=> (Possible ?a ?s) |
|
(=>
(On Pump (Do ?a ?s)) |
|
(or (and (not (= ?a (Turn-Off
Pump))) |
|
(= ?a (Turn-On
Pump))) |
|
(and (not (= ?a (Turn-Off
Pump))) (On Pump ?s))))) {[6E]} |
|
[8E] (=> (Possible ?a ?s) |
|
(=>
(On Pump (Do ?a ?s)) |
|
(or (= ?a (Turn-On Pump)) |
|
(and (On Pump ?s) (not
(= ?a (Turn-Off Pump))))))) {[7E]} |
|
|
|
|
|
[5]
(=> (Possible ?a ?s) |
|
(=> (or (Instance-Of ?a ActionF[x1,
,xn]+) |
|
(and
(F x1
xn ?s) (not
(Instance-Of ?a ActionF[x1,
,xn]-))) |
|
(F x1
xn (Do ?a ?s)))) |
|
[8]
(=> (Possible ?a ?s) |
|
(=> (F x1
xn (Do ?a
?s)) |
|
(or (Instance-Of ?a ActionF[x1,
,xn]+) |
|
(and (F x1
xn ?s) (not
(Instance-Of ?a ActionF[x1,
,xn]-)))))) |
|
[9]
(=> (Possible ?a ?s) |
|
(<=> (F x1
xn (Do ?a
?s)) |
|
(or (Instance-Of ?a ActionF[x1,
,xn]+) |
|
(and (F x1
xn ?s) (not (Instance-Of ?a
ActionF[x1,
,xn]-)))))) {5;8} |
|
(F x1
xn) is true in the state resulting from
performing action A in state S |
|
if and only if either A is a positive effect action for (F x1
xn) |
|
or it was true in the previous state |
|
and A is not a negative
effect action for (F x1
xn) |
|
|
|
|
|
[5E]
(=> (Possible ?a ?s) |
|
(=> (or (= ?a (Turn-On Pump)) |
|
(and (On Pump ?s) (not (= ?a
(Turn-Off Pump))))) |
|
(On Pump (Do ?a ?s)))) |
|
[8E]
(=> (Possible ?a ?s) |
|
(=>
(On Pump (Do ?a ?s)) |
|
(or (= ?a (Turn-On Pump)) |
|
(and (On Pump ?s) (not
(= ?a (Turn-Off Pump))))))) |
|
[9E]
(=> (Possible ?a ?s) |
|
(<=> (On Pump (Do ?a
?s)) |
|
(or (= ?a (Turn-On Pump)) |
|
(and (On Pump ?s) (not (= ?a (Turn-Off Pump))))))) {5;8} |
|
(On Pump) is true in the state resulting from
performing action A in state S |
|
if and only if either A is (Turn-On Pump) |
|
or it was true in the previous state |
|
and A is not (Turn-Off
Pump) |
|
|
|
|
|
|
The Frame Problem |
|
How to characterize what does not change after
an action is performed |
|
We examined the problem in the situation
calculus formalism |
|
Adding frame axioms to solve the frame problem
is not parsimonious |
|
Under a completeness assumption, compiling
effect axioms into successor state axioms solves the frame problem for the
provided representation |
|
Captures the non-effects of actions for the
provided representation |
|
Parsimonious: one successor state axiom per
fluent |
|
|
|
|
|
|
The Planning Domain Definition Language (PDDL) |
|
Authors: AIPS-98 Planning Competition Committee |
|
AIPS: Artificial Intelligence Planning Systems |
|
Conference held every 2 years |
|
Planning competition at each conference |
|
PDDL is the problem specification language for
the competition |
|
PDDL expresses |
|
The physics of a domain |
|
Classes, relations, possible actions, constants,
safety constraints,
|
|
Planning problems |
|
An initial situation and a goal to be achieved |
|
With respect to a domain |
|
|
|
|
|
Action description |
|
<action-def> ::= (:action <name> |
|
:parameters (<typed list (variable)>) |
|
(action-def body>) |
|
<action-def body> ::= [:vars (<typed
list (variable)>)] |
|
[:precondition <goal>]
|
|
[:effect <effect>]
|
|
Example of a typed list: |
|
(?x physob ?l location) |
|
Goal: function-free first-order predicate logic
sentence |
|
|
|
|
|
|
|
|
|
|
|
|
Action description |
|
<action-def> ::= (:action <name> |
|
:parameters (<typed list (variable)>) |
|
(action-def body>) |
|
<action-def body> ::= [:vars (<typed
list (variable)>)] |
|
[:precondition <goal>]
|
|
[:effect <effect>]
|
|
<effect> ::= (and <effect>*) | |
|
<literal> | |
|
(forall (<variable>*) <effect>) | |
|
(when <goal> <effect>) |
|
|
Effects |
|
Truth value of atomic sentences assumed to
persist forward in time unless an effect asserts its negation |
|
(when P E) is a conditional effect |
|
Means if
P is true before the action, then effect E occurs after |
|
|
|
|
|
|
|
|
|
Domain definition |
|
(define (domain briefcase-world) |
|
(:requirements :strips :equality :typing :conditional-effects) |
|
(:types
location physob) |
|
(:constants (B physob)) |
|
(:predicates (at ?x physob ?l location) |
|
(in ?x ?y physob)) |
|
|
|
Action definition |
|
Move the briefcase from location ?m to a
different location ?l |
|
(:action mov-b |
|
:parameters (?m ?l location) |
|
:precondition (and (at B ?m) (not (= ?m ?l))) |
|
:effect (and (at b ?l) (not (at B ?m)) |
|
(forall (?z) |
|
(when (and (in ?z) (not (= ?z B))) |
|
(and (at ?z ?l) (not (at ?z
?m))))))) |
|
|
|
|
|
|
|
Action definitions |
|
Put something in the briefcase |
|
(:action put-in |
|
:parameters (?x physob ?l - location) |
|
:precondition (not (= ?x B)) |
|
:effect (when (and (at ?x ?l) (at B ?l)) (in ?x))) |
|
Take something out of the briefcase |
|
(:action take-out |
|
:parameters (?x physob) |
|
:precondition (not (= ?x B)) |
|
:effect (not (in ?x))) |
|
|
|
|
|
Problem definition |
|
At home one has a dictionary and a briefcase
with a paycheck inside it. |
|
We wish to have the dictionary and briefcase at
work and the paycheck at home. |
|
(define (problem get-paid) |
|
(:domain briefcase-world) |
|
(init
(place home) (place office) (object P) (object D) (object B) |
|
(at B home) (at P home) (at D home) (in P)) |
|
(goal
(and (at B office) (at D office) (at P home)))) |
|
Solution |
|
(take-out P) (put-in D) (mov-b home office) |
|
|
|
|
|
|
Abstract plans describe how to achieve a goal |
|
E.g., Clear a paper jam in a photocopier |
|
Medical treatment protocol |
|
Planners task is to instantiate and compose
abstract plans |
|
Goals can be specified as abstract actions to
perform |
|
Rather than conditions on a state to be achieved |
|
Action description |
|
<action-def> ::= (:action <name> |
|
:parameters (<typed list (variable)>) |
|
(action-def body>) |
|
<action-def body> ::= [:vars (<typed
list (variable)>)] |
|
[:precondition <goal>] |
|
[:expansion <action spec>]
|
|
[:maintain <goal>] |
|
[:effect <effect>]
|
|
|
|
|
|
Action spec |
|
<action-spec> ::= <action-term> | |
|
(series <action spec>*) | |
|
(in-context <action spec>
<action-def body>) |
|
|
|
<action-term> ::= (<action name>
<term>*) |
|
Example |
|
Evacuate an area of friendly forces and then
shell it |
|
(series (clear ?area) |
|
(in-context (shell ?area) |
|
:precondition (not (exists (?x unit) |
|
(and (friendly ?x) |
|
(in ?x ?area)))))) |
|
|
|
|
|
|
|
Action spec |
|
<action-spec> ::= <action-term> | |
|
(series <action spec>*) | |
|
(in-context <action spec>
<action-def body>) | |
|
(constrained (<action
spec>+) |
|
<action constraint>*)
|
|
|
<action-term> ::= (<action name>
<term>*) |
|
Example |
|
Expand an action into four subactions A, B, C,
and D, such that A precedes B and D, and C precedes D, with condition P
maintained from the end of A until the end of D |
|
(constrained ((series A B) (series A D (series C
D)) |
|
(in-context (series end-A end-D) |
|
:maintain (P))) |
|
Notes