Logic Based Planning
Situation Calculus: Situation calculus is a version of first-order-logic (FOL) that is augmented so that it can reason about actions in time.
Example: The action "agent-walks-to-location-y" could be represented by:
(Ax)(Ay)(As)(at(Agent,x,s) -> at(Agent,y,result(walk(y),s))
Frame Problem: Actions in Situation Calculus describe what they change, not what they don’t change. So, how do we know what’s still true in the new situation? To fix this problem we add a set of frame axioms that explicitly state what doesn’t change.
Example: When the agent walks to a location, the locations of most other objects in the world do not change. So for each object (i.e. a bunch of bananas), add an axiom like:
(Ax)(Ay)(As)(at(Bananas,x,s) -> at(Bananas,x,result(walk(y),s))
Solving planning problems using situation calculus: Using situation calculus a planning algorithm is represented by logical sentences that describe the three main parts of a problem. This is illustrated using the problem described in AI: A Modern Approach by Russell & Norvig.
1. Initial State: a logical sentence of a situation So. For the shopping problem it could be:
At(Home,So) /\ -Have(Milk,So) /\ -Have(Bananas,So) /\ -Have(Drill,So)
2. Goal State: a logical query asking for a suitable situation. For the shopping problem, a query is:
$ s At(Home,s) /\ Have(Milk,s) /\ Have(Bananas,s) /\ Have(Drill,s)
3. Operators: a set of descriptions of actions.
Ex. A successor-state action with the Buy(Milk) action
" a,s Have(Milk,Result(a,s)) <=> [(a = Buy(milk) /\ At(supermarket,s) \/ (Have(Milk,s) /\ a NOT= Drop(Milk))]
Result(a,s) names the situation resulting from being in s while executing action a.
It will be useful to handle action sequences than just a single action. We can use Result' (l,s) to mean the situation resulting from executing l (the sequence of actions) beginning in s. Result' is described by saying that an empty sequence of actions will not effect the situation, and a non-empty sequence of actions is the same as doing the first action and then finishing the rest of the actions from the resulting situation.
Empty sequence of actions is represented as: " s Result' ([],s) = s
Non-empty sequence of actions is represented as: " a,p,s Result' ([a|p],s) = Result' (p, Result(a,s))
p is a plan and when applied to start state So, develops a situation which satisfies the goal query.
p could be:
At(home, Result' (p,So)) /\ Have(Milk, Result' (p,So)) /\ Have(Bananas, Result' (p,So)) /\ Have(Drill,Result' (p,So))
The goal query could be:
G = [Go(Supermarket), Buy(Milk), Buy(Banana), Go(Hardware Store), Buy(Drill), Go(Home)]
In theory, there isn't much more to say. Doing planning this way doesn't guarantee a practical solution. Plan p guarantees to achieve the goal but not necessarily efficiently. This approach is representation strong, but reasoning weak because of the poor efficiency of resolution.
Practical Planning: To make planning practical we need to do 2 things:
1. Restrict the language with which we define problems. With a restrictive language, there are fewer possible solutions to search through.
Use a special-purpose algorithm called a planner rather than a general-purpose theorem prover to search for a solution.
