11PlanningBurr H. SettlesCS-540, UW-Madisonwww.cs.wisc.edu/~cs540-1Summer 20032Announcements (7/7)Lots of homework business!– HW#3 out (due Monday, 7/14)– HW#2 due today– HW#1 almost graded, back tomorrowReminders:– Midterm review on Wednesday (7/9)– Midterm on Thursday, in class (7/10)– No class on Friday (7/11)3Announcements (7/8)Homework #1 is not quite graded!– Check my mailbox in CS 5thfloor after 5pm today– Otherwise, collect them at the review tomorrow– There is a solution for HW#1 on the webpageHomework #3 due date extended (Wed. 7/16)About the exam:– Closed book, but you may bring a 1-sided handwritten 8½×11 sheet of notes and a calculator– I threw together a midterm study guide available on the course webpage under “exam” section4PlanningProblem: Mechanically and efficiently find a sequence of actions that, when “executed,” achieve a goalGiven:– Initial state, goal state, and actionsFind:– A plan: a sequence of actions that when applied, beginning with the initial state, transforms the world into a goal state5Assumptions with PlanningGoal is a conjunction of sub-goals:– To achieve a goal, you must achieve a set of sub-goalsActions are atomic– Are not divisible into sub-actionsActions are sequential– No two actions can be executed concurrentlyActions are deterministic: – No uncertainty in performing an action6Assumptions with PlanningThe agent is the sole cause of change in the environmentWorld is accessible (i.e. the agent knows all it need to know about the environment)Closed World Assumption:– State description lists all that is true– Anything else is assumed false The planning task is very difficult, even with such a simplified framework!27Classic Planning ProblemsDressing– Initial state: socks, shoes, and pants off– Goal state: socks on, under shoes (on correct feet), under pants– Actions: PutOnPants, PutOnSock(f), PutOnShoe(f)Blocks World– Initial state: some configuration of blocks on a table– Goal State: another configuration (stacked?)– Actions: Pickup(x), Putdown(x), Stack(x,y), Unstack(x,y)Shopping– Initial state: at home, with no items– Goal state: at home, having a list of items– Actions: Go(store), Buy(item), etc…8Planning As SearchState-space search:– State representation– Operators/actions– Start state– Goal test Note: This is how we approached the “water jugs” problem back in lecture 39Planning As SearchDoesn’t allow for real reasoning about states and actions– Operators are just used to generate next state– Can’t reason about operator definition or ordering• Causes exploration of dead-end successor states(possibly even illegal ones!)– Goal test is just used to determine if goal reached– Can’t reason about goal definition• No knowledge of determining how to best achieve the goal• Note: heuristic is simply the distance from goalWeak representationWeak ability to reason about the world10Planning Using LogicBy using knowledge-based agents, we can capture reasonable information things about the agent’s actions and their effect on the world– “If I move forward, I’m in the next room”– “If I pick up a gold brick, then I am holding it”– “If I am holding something, my hand is not empty”The problem here is dealing with time:– “If I move forward again, I’m in a different room”– The results of each action are now relative to the sequence of actions before…11Situation CalculusSituation calculus extends FOL to deal with such time-sensitive dilemmas for planning (Sec. 10.3)– Situations are states that are generated from applying an action to another situation • Result(a, s) is the function that returns the situation when applying action a to situation s– Fluents are predicates/functions that vary from one situation to the next, such as the location of the agent, or what it may be holding– Atemporals/eternals are predicates/functions that do not depend on a time stamp• e.g. Dog(Lassie) or LeftLegOf(John)12Situation Calculus313Situation CalculusThere are two types of axioms (or rules) in situation calculus:– Possibility axioms: say when it is possible to perform a certain action• At(Agent, x, s) ∧ Adjacent(x, y) Poss(Go(x, y), s)• Gold(g) ∧ At(g, x, s) ∧ At(Agent, x, s) Poss(Pickup(g), s)• Holding(g, s) Poss(Putdown(g), s)– Effect axioms: defines what happens in the environment when a possible action is executed• Poss(Go(x, y), s) At(Agent, y, Result(Go(x,y), s))• Poss(Pickup(g), s) Holding(g, Result(Pickup(g), s))• Poss(Putdown(g), s) ¬Holding(g, Result(Putdown(g), s))14Situation CalculusFortunately, situation calculus allows us to express what actions are reasonable as well as what will change when an action is takenUnfortunately, it doesn’t say anything about whatstays the same!Frame axioms specify what does not change when a certain action is applied– e.g. “If I go into a room that had gold in it during the last situation, then the gold is still there”– Many axioms are required (for each action even!)15Situation CalculusSituation calculus with frame axioms is a strong representation– However, the approach is not very modular… each new predicate requires axioms to be added for each of the possible actions Inference procedures are very weak… the representation is too fine-grained16Planning SolutionCombine the two approaches:Simplify the representation language– Allow reasoning about how to achieve the goal– Inference procedure is faster than resolution“Open up” the representation of states, operators, and goal test– Rather than blindly applying operators, try to reason about which ones are most important– Reduces the number of nodes that are considered17STRIPS RepresentationSTRIPS (STandard Research Institute Problem Solver):Facts: ground literals with variablesSituations: conjunction of factsGoal: conjunction of positive literals– Variables allowed, assume all variables are existentialOperators/Actions: – Action name– Preconditions: conjunction of positive literals that defines if action is legal/applicable– Effects: conjunction of positive literals (called the add list) and negative literals (called the delete list)– Assumption: everything stays the same unless explicitly on the delete list (avoids frame problem)18Representation