Unformatted text preview:

CMSC 671 Fall 2005Today’s classPlanningPlanning problemPlanning vs. problem solvingTypical assumptionsBlocks worldMajor approachesGeneral Problem SolverSituation calculus planningSituation calculusSituation calculus IISituation calculus: Blocks worldSituation calculus planning: AnalysisBasic representations for planningOperator/action representationBlocks world operatorsBlocks world operators IISTRIPS planningTypical BW planning problemAnother BW planning problemGoal interactionSussman AnomalyState-space planningPlan-space planningPartial-order planningLeast commitmentNon-linear planThe initial planTrivial exampleSolutionPOP constraints and search heuristicsPartial-order planning exampleSlide 34Slide 35Slide 36Slide 37Slide 38Resolving threatsSlide 40Slide 411CMSC 671CMSC 671Fall 2005Fall 2005Class #14 / 16 – Tuesday, October 18 /Tuesday, October 252Today’s class•What is planning?•Approaches to planning–GPS / STRIPS–Situation calculus formalism [revisited]–Partial-order planning3PlanningPlanningChapter 11.1-11.3Some material adopted from notes by Andreas Geyer-Schulzand Chuck Dyer4Planning problem•Find a sequence of actions that achieves a given goal when executed from a given initial world state. That is, given –a set of operator descriptions (defining the possible primitive actions by the agent), –an initial state description, and –a goal state description or predicate, compute a plan, which is –a sequence of operator instances, such that executing them in the initial state will change the world to a state satisfying the goal-state description. •Goals are usually specified as a conjunction of goals to be achieved5Planning vs. problem solving•Planning and problem solving methods can often solve the same sorts of problems•Planning is more powerful because of the representations and methods used•States, goals, and actions are decomposed into sets of sentences (usually in first-order logic)•Search often proceeds through plan space rather than state space (though there are also state-space planners)•Subgoals can be planned independently, reducing the complexity of the planning problem6Typical assumptions•Atomic time: Each action is indivisible •No concurrent actions are allowed (though actions do not need to be ordered with respect to each other in the plan)•Deterministic actions: The result of actions are completely determined—there is no uncertainty in their effects •Agent is the sole cause of change in the world •Agent is omniscient: Has complete knowledge of the state of the world •Closed World Assumption: everything known to be true in the world is included in the state description. Anything not listed is false.7Blocks worldThe blocks world is a micro-world that consists of a table, a set of blocks and a robot hand.Some domain constraints:–Only one block can be on another block–Any number of blocks can be on the table–The hand can only hold one blockTypical representation:ontable(a)ontable(c)on(b,a)handemptyclear(b)clear(c)ABCTABLE8Major approaches•GPS / STRIPS•Situation calculus•Partial order planning•Hierarchical decomposition (HTN planning)•Planning with constraints (SATplan, Graphplan)•Reactive planning9General Problem Solver•The General Problem Solver (GPS) system was an early planner (Newell, Shaw, and Simon) •GPS generated actions that reduced the difference between some state and a goal state•GPS used Means-Ends Analysis–Compare what is given or known with what is desired and select a reasonable thing to do next–Use a table of differences to identify procedures to reduce types of differences•GPS was a state space planner: it operated in the domain of state space problems specified by an initial state, some goal states, and a set of operations10Situation calculus planning•Intuition: Represent the planning problem using first-order logic–Situation calculus lets us reason about changes in the world–Use theorem proving to “prove” that a particular sequence of actions, when applied to the situation characterizing the world state, will lead to a desired result11Situation calculus•Initial state: a logical sentence about (situation) S0At(Home, S0)  Have(Milk, S0)   Have(Bananas, S0)   Have(Drill, S0)•Goal state: (s) At(Home,s)  Have(Milk,s)  Have(Bananas,s)  Have(Drill,s)•Operators are descriptions of how the world changes as a result of the agent’s actions: (a,s) Have(Milk,Result(a,s))  ((a=Buy(Milk)  At(Grocery,s))  (Have(Milk, s)  a  Drop(Milk)))•Result(a,s) names the situation resulting from executing action a in situation s. •Action sequences are also useful: Result'(l,s) is the result of executing the list of actions (l) starting in s:( s) Result'([],s) = s( a,p,s) Result'([a|p]s) = Result'(p,Result(a,s))12Situation calculus II•A solution is a plan that when applied to the initial state yields a situation satisfying the goal query: At(Home, Result'(p,S0))  Have(Milk, Result'(p,S0))  Have(Bananas, Result'(p,S0))  Have(Drill, Result'(p,S0))•Thus we would expect a plan (i.e., variable assignment through unification) such as: p = [Go(Grocery), Buy(Milk), Buy(Bananas), Go(HardwareStore), Buy(Drill), Go(Home)]13Situation calculus: Blocks world•Here’s an example of a situation calculus rule for the blocks world:–Clear (X, Result(A,S))  [Clear (X, S)  ((A=Stack(Y,X)  A=Pickup(X))  (A=Stack(Y,X)  (holding(Y,S))  (A=Pickup(X)  (handempty(S)  ontable(X,S)  clear(X,S))))]  [A=Stack(X,Y)  holding(X,S)  clear(Y,S)]  [A=Unstack(Y,X)  on(Y,X,S)  clear(Y,S)  handempty(S)]  [A=Putdown(X)  holding(X,S)]•English translation: A block is clear if (a) in the previous state it was clear and we didn’t pick it up or stack something on it successfully, or (b) we stacked it on something else successfully, or (c) something was on it that we unstacked successfully, or (d) we were holding it and we put it down.•Whew!!! There’s gotta be a better way!14Situation calculus planning: Analysis•This is fine in theory, but remember that problem solving (search) is exponential in the worst case•Also, resolution theorem proving only finds a proof (plan), not necessarily a good plan•So we restrict the language and use a special-purpose algorithm (a planner) rather than general theorem prover15Basic representations for


View Full Document

UMBC CMSC 671 - LECTURE NOTES

Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?