PlanningAI lecture (Yoonsuck Choe): Material from Russel and Norvig (2nd ed.)• 7.2, 7.7: Wumpus world (an example domain)• 10.3: Situation calculus• 11: Planning1Planning• The task of coming up with a sequence of actions that will achievea goal is called planning.• Simple approaches:– Search-based– Logic-based• Representation of states and actions become important issues.2Example Domain: Wumpus WorldBreeze BreezeBreezeBreezeBreezeStenchStenchBreezePITPITPIT1 2 3 41234STARTGoldStench• Want to get to the gold and grab it.• Want to avoid pits and the “wumpus”.• Clues: breeze near pits and stench near the wumpus.• Other sensors: wall (bump), gold (glitter), kill (scream)• Actions: move, grab, or shoot.3Wumpus World (WW)Breeze BreezeBreezeBreezeBreezeStenchStenchBreezePITPITPIT1 2 3 41234STARTGoldStenchPerformance measure• +1000: picking up gold• -1000: fall in a pit, or get eaten by the wumpus• -1: each action taken• -10: each arrow used4Evolution of Knowledge in WWABGPSW = Agent = Breeze = Glitter, Gold = Pit = Stench = WumpusOK = Safe squareV = VisitedAOK 1,1 2,1 3,1 4,1 1,2 2,2 3,2 4,2 1,3 2,3 3,3 4,3 1,4 2,4 3,4 4,4OKOKBP?P?AOK OKOK 1,1 2,1 3,1 4,1 1,2 2,2 3,2 4,2 1,3 2,3 3,3 4,3 1,4 2,4 3,4 4,4V(a)(b)• Move from [1,1] to [2,1].• Based on the sensory data (breeze), we can mark [2,2] and [3,1]as potential pits, but not [1,1] since we came from there and wealready know there’s no pit there.5Evolution of Knowledge in WWBBP!AOK OKOK 1,1 2,1 3,1 4,1 1,2 2,2 3,2 4,2 1,3 2,3 3,3 4,3 1,4 2,4 3,4 4,4VOKW!VP!AOK OKOK 1,1 2,1 3,1 4,1 1,2 2,2 3,2 4,2 1,3 2,3 3,3 4,3 1,4 2,4 3,4 4,4VSOKW!VV VBS GP?P?(b)(a)SABGPSW = Agent = Breeze = Glitter, Gold = Pit = Stench = WumpusOK = Safe squareV = Visited• Move back to [1,1] and then to [1,2]. At this point, the agent caninfer that the wumpus is in [1,3]!• Then move to [2,2] and then to [2,3] where the gold can be gound(glitter).6Inference in Wumpus WorldBreeze BreezeBreezeBreezeBreezeStenchStenchBreezePITPITPIT1 2 3 41234STARTGoldStench• Knowledge Base: basic rules of the Wumpus World.• Additional knowledge is added to the KB: facts you gather as youexplore ([x,y] has stench, breeze, etc.)• We can ask if a certain statement is a logical consequence of theKB: “There is a pit in [1,2]”7Inference in Wumpus World1 2 312BreezePIT1 2 312BreezePIT1 2 312BreezePIT PITPIT1 2 312BreezePITPIT1 2 312BreezePIT1 2 312BreezePITPIT1 2 312BreezePIT PIT1 2 312BreezeKB11 2 312BreezePIT1 2 312BreezePIT1 2 312BreezePIT PITPIT1 2 312BreezePITPIT1 2 312BreezePIT1 2 312BreezePITPIT1 2 312BreezePIT PIT1 2 312BreezeKB2KB: basic rules, plus [1,1] and [2,1] explored.• α1= “There is no pit in [1,2]”• α2= “There is no pit in [2,2]”• Only α1follows from the KB.8Propositonal-logic-based Agent• Query KB: Is there a Wumpus in [x,y]? Is there a pit in [x,y]?• Add knowledge to KB (perceptual input): Breeze felt in [x,y],Stench detected in [x,y], etc.• Decide which action to take (move where, etc.): Move to [x,y],grab gold, etc.Note: here, there’s only one goal, to grab the gold. Can we specify anarbitrary goal and derive a plan?Problem: Propositions need to be explicit about location, e.g.,Breezex,y, Stenchx,y, ¬W umpusx,y.9Situation CalculusMake propositional-logic-based planner scalable.• Situations: logical terms indicating a state.Example: In situation S0taking action a leads to situation S1:S1= Result(a, S0).• Fluents: funcitons and predicates that vary from one situation tothe next.Example:¬Holding(Gol d1, S0), Age(W umpus)Other stuff: Atemporal/eternal predicates Gold(Gold1), emptyactions Result([], s) = s, sequence of actionsResult([a|seq], s) = Res ult(seq, Result(a, s)).10Situation Calculus: Tasks• Projection:Deduce the outcome of a given sequence of actions• Planning:Find a sequence of actions that achieves a desired effect.Example: Wumpus worldInitial: At(Agent, [1, 1], S0) ∧ At(G1, [1, 2], S0), ...Goal: ∃seq At(G1, [1, 1], Result(seq, S0))11Describing Actions in Situation CalculusTwo axioms:• Possibility axiom: when it is possible to execute an actionPreconditions → P oss(a, s)• Effect axiom: What happens when a possible action is takenP oss(a, s) → Changes that result12Wumpus World: Axioms• Possibility axioms: Move, grab, releaseAt(Agent, x, s)∧Adjacent(x, y) → P oss(Go(x, y(, s)Gold(g)∧At(Agent, x, s)∧At(g, x, s) → P oss(Grab(g), s)Holding(g, s) → P oss(Release(g), s )• Effect axioms: Move, Grab, ReleaseP oss(Go(x, y), s) → At(Agent, y, Result(Go(x, y), s))P oss(Grab(g), s ) → Holding(g, R esu lt(Grab(g), s))P oss(Release(g), s) → ¬Holding (g, Result(Relea se(g), s))13Frame Problem• In the previous slide, we cannot deduce if the following can beproven (G1represents a particular lump of gold):At(G1, [1, 1], Result([Go([1, 1], [1, 2]), Grab(G1), Go([1, 2], [1, 1])], S0)• It is because the effect axioms say only what should change, butnot what does not change when actions are taken.• Initial solution: Frame axiomsAt(o, x, s) ∧ (o 6= Agent) ∧ ¬Holding(o, s)→ At(o, x, Result(Go(y, z), s)).This says moving does not affect the gold when it is not held.Problem is that you need O(AF ) such axioms for all(action, fluent) pair (A: num of actions, F : num of fluentpredicates).14Two Frame Problems• Representational frame problem:Explained in the previous slide• Inferential frame problem:Projection of results of a t-step sequence of actions in timeO(Et) (E is the number of effects, typically much less than F ,the number of fluent predicates), rather than O(F t) orO(AEt).15Solving the Representational Frame Problem• Consider how each fluent predicate evolves over time:Successor-state axioms Action is possible →(Fluent is true in result state ↔ Action’s effect made it true∨It was true before and action left it alone).• Example:P oss(a, s) →(At(Agent, y, Result(a, s)) ↔ a = Go(x, y)∨(At(Agent, y, s)∧ a 6= Go(y, z))).• Remaining issues: implicit effect (moving while holding somethingmoves that something as well) – ramification problem. Can solveby using a more general succesor-state axiom.16Solving the Inferential Frame Problem• Given a t-step plan p (St= Result(p, S0)), decide whichfluents are true in St.• We need to consider each of the F frame axiom of each timestep t.• Axioms have an average size of AE/F , we have an O(AEt)inferential work. Most of the work is done