1Lecture 11 • 16.825 Techniques in Artificial IntelligencePartial-Order Planning AlgorithmsLast time we talked about partial order planning, and we got through the basic idea and the formal description of what constituted a solution. So, our plan for today is to actually write the algorithm, and then go back and work through the example that we did, especially the last part of it and be sure we see how the algorithm would do the steps that are necessary to get the plan steps to come out in the right order, and to do another example just for practice. Then, next time, we’ll talk about a newer algorithm called GraphPlan.2Lecture 11 • 2Partially Ordered Plan•Plan•Steps• Ordering constraints• Variable binding constraints• Causal linksLet’s just briefly review the parts of a partially ordered plan. There are the steps, or actions we plan to take. There are ordering constraints that say which steps have to be before which other ones. They need to be consistent, but they don’t need to specify a total order on the steps. There are variable binding constraints that specify which variables are equal to which other variables or constants. And there are causal links to remind us which effects of actions we are using to satisfy which preconditions of other actions.3Lecture 11 • 3Partially Ordered Plan•Plan•Steps• Ordering constraints• Variable binding constraints• Causal links•POP AlgorithmNow we can specify the algorithm for partial-order planning.4Lecture 11 • 4Partially Ordered Plan•Plan•Steps• Ordering constraints• Variable binding constraints• Causal links•POP Algorithm• Make initial planstartfinishFirst, we make the initial plan. Remember, it contains two “dummy” steps called start and finish. The start step has the initial conditions as its effects and the finish step has the goal conditions as its preconditions.5Lecture 11 • 5Partially Ordered Plan•Plan•Steps• Ordering constraints• Variable binding constraints• Causal links•POP Algorithm• Make initial plan• Loop until plan is a completestartfinishThen, we iterate until the plan is complete. Remember that a plan is complete when every precondition of every step is satisfied by the effect of some other step; these are the relationships that we keep track of using causal links. So, until the plan is complete, we keep doing the following three steps. (We’ll go into the last two in much greater detail in following slides).6Lecture 11 • 6Partially Ordered Plan•Plan•Steps• Ordering constraints• Variable binding constraints• Causal links•POP Algorithm• Make initial plan• Loop until plan is a complete– Select a subgoalstartfinishFirst, we choose a subgoal; that is, a precondition that is not yet satisfied. We’ll callthat precondition c.7Lecture 11 • 7Partially Ordered Plan•Plan•Steps• Ordering constraints• Variable binding constraints• Causal links•POP Algorithm• Make initial plan• Loop until plan is a complete– Select a subgoal– Choose an operatorstartfinishNext, we choose an operator that can satisfy c for us.8Lecture 11 • 8Partially Ordered Plan•Plan•Steps• Ordering constraints• Variable binding constraints• Causal links•POP Algorithm• Make initial plan• Loop until plan is a complete– Select a subgoal– Choose an operator–Resolve threatsstartfinishFinally, we check to be sure that the work we did in the previous step doesn’t cause any of our previous causal links to be “threatened”, or possibly violated. If we have a link that is threatened, we must resolve the threat.9Lecture 11 • 9Choose Operator• Choose operator(c, Sneeds)Okay. In the previous step, we chose a condition c that was an unsatisfied precondition of some step. Let’s call the step that needs c to be true “S sub needs”. Now, we need to find a way to make c true. There are two basic ways to do it: either we find some step in the existing plan that has c as an effect, or we add a new step to the plan.10Lecture 11 • 10Choose Operator• Choose operator(c, Sneeds)Nondeterministic choiceWe’re going to describe the algorithm for choosing operators using a special kind of programming language feature called “nondeterministic choice”. It’s a very convenient and effective way to describe search algorithms without getting into the details. A few real programming languages have been built that have this feature, but most don’t. We use it to make our pseudocode short.11Lecture 11 • 11Choose Operator• Choose operator(c, Sneeds)Nondeterministic choice• Choose– pick one of the options arbitrarilyThe “choose” operator describes a set of possible things that the algorithm could do next. When the statement is encountered, one of these things is chosen for execution, and the choice of which one is essentially arbitrary.12Lecture 11 • 12Choose Operator• Choose operator(c, Sneeds)Nondeterministic choice• Choose– pick one of the options arbitrarily•Fail– go back to most recent non-deterministic choice and try a different one that has not been tried beforeThe “fail” operator says the algorithm should go back to the most recent non-deterministic choice point and choose a different option, from among those that have not yet been tried. If they’ve all been tried, then the whole “choose” operation fails, and we go back to the next most recent choose operation, and so on.13Lecture 11 • 13Choose Operator• Choose operator(c, Sneeds)• Choosea step S from the plan or a new step S by instantiating an operator that has c as an effectNondeterministic choice• Choose– pick one of the options arbitrarily•Fail– go back to most recent non-deterministic choice and try a different one that has not been tried beforeOkay. Back to the question of how to choose an operator to establish the condition c for the step S_needs. We will nondeterministically choose a step S from the plan or a new step S that is created by instantiating one of the operators.14Lecture 11 • 14Choose Operator• Choose operator(c, Sneeds)• Choosea step S from the plan or a new step S by instantiating an operator that has c as an effect• If there’s no such step, FailNondeterministic choice• Choose – pick one of the options arbitrarily•Fail– go back to most recent non-deterministic choice and try a different one that has not been tried beforeIf there is no such step, then there is no way