6 825 Techniques in Artificial Intelligence Graph Plan Overview PO Planning human like but very slow Lecture 12 1 We ve been talking about planning We started with situation calculus which because of its basis in full first order logic is completely intractable So we moved to highly restricted operator representations and then the partial order planner which seemed like a good idea because it would let you do non linear planning to put in planned steps in whatever order you wanted to and hook them up And there s something attractive about the partial order planners They seem almost like you might imagine that a person would go about planning right You put these steps in and then try to fix up the problems and it seems kind of appealing and intuitive and so attractive to people but they re really awfully slow The structure of the search space is kind of hard to understand It s not at all clear how to apply the things that we learned say in the SAT stuff to partial order planning It s not clear how to prune the state space how to recognize failures early all those kinds of things 1 6 825 Techniques in Artificial Intelligence Graph Plan Overview PO Planning human like but very slow Graph Plan Simplified planning model Efficient algorithm Lecture 12 2 So in what appears to be a sort of a retrogressive move the planning community about maybe ten years ago kind of quit doing partial order planning and said no wait a minute maybe we can do better by looking at these planning problems in some sense in a simpler and more primitive way What we re going to do today is talk about GraphPlan which is described in the paper by Weld that we have linked into the web 2 Graph Plan Lecture 12 3 Graphplan was invented by a couple of theoreticians who said Oh these planning people they play around with algorithms but what do they know We know about algorithms so let s just try to take this planning problem they have and get at it somehow more directly 3 Graph Plan A propositional planner that is there are no variables Lecture 12 4 The first big thing about Graphplan is that it s a propositional planner So that means that there are no variables around in the course of planning When we did the partial order planning examples we were doing the blocks world and we had operator descriptions with variables that let us speak generally about moving blocks rather than naming particular ones In GraphPlan we re not going to be able to have any variables floating around during the planning process 4 Graph Plan A propositional planner that is there are no variables Simpler don t have to worry about matching Lecture 12 5 Not having any variables makes your life simpler in the sense that you don t have to worry about unification or variable matching or any of that stuff 5 Graph Plan A propositional planner that is there are no variables Simpler don t have to worry about matching Bigger if you have six blocks you need 36 propositions to represent all On x y assertions Lecture 12 6 But it may make it harder in that if you really do have six blocks and an on A B relation then you ll have to make 36 propositions one for every possible instantiation of the variables in that relationship So if you need to talk about six different blocks and how they could be on each other then that might be a lot of propositions But at least in this work it s going to turn out that it s worth having a big representation that s fairly easy to deal with that it s going to be more efficient to do that than to have a very concise but kind of complicated representation as we have when we have variables So that s the tradeoff and so in this case we re going to go for big but simple the propositional planner 6 Graph Plan A propositional planner that is there are no variables Simpler don t have to worry about matching Bigger if you have six blocks you need 36 propositions to represent all On x y assertions 1 2 3 4 5 Make a plan graph of depth k Search for a solution If succeed return a plan Else k k 1 Go to 1 Lecture 12 7 The graphplan algorithm has the following structure This isn t really going to make too much sense until we look at the pieces in detail but the idea is that you make a plan graph of depth k and then you search for a solution and if you succeed you return a plan Otherwise you increment K and try again So that s the basic scheme 7 Plan Depth A plan of depth k has k times steps may have multiple parallel actions per time step Lecture 12 8 Note that I wrote make a plan graph of depth K We re going to look for plans of depth K so if we look for a depth two plan it will have two time steps but it will be partially ordered in the sense that multiple actions might possibly take place in a single time step Maybe you can or can not actually execute them in parallel but there will be some actions where you don t care what order they occur in 8 Plan Depth A plan of depth k has k times steps may have multiple parallel actions per time step t 1 DoA t 2 t 3 DoB DoC DoD DoE Lecture 12 9 And so what you might get out of GraphPlan is a plan that looks like this and say this is a depth three five step plan All right So if you could actually execute these things in parallel then it would only take you three time steps If you have to linearize them it s OK and you could put DoA and DoB in any order and DoD and DoE in any order So the algorithm will search for a depth one plan and then a depth two plan and then a depth three plan and so on until we find the answer It s a little like iterative deepening Some of the motivations for doing that are the same 9 Planning vs Scheduling Scheduling tasks are fixed Lecture 12 10 There are really two different but highly related problems If you read the book they sometimes talk about planning versus scheduling In scheduling the tasks are fixed A scheduling problem might be that we have to figure out how to fit all your classes into your schedule or all the exams into the exam period There may be constraints on aspects of the schedule but you don t have to figure out which particular tasks you need to do Typically that s specified and all you have to do is find an ordering for them 10 Planning vs Scheduling Planning find steps and schedule Scheduling …