INTRO In previous classes we talked about constructing a plangraph (i.e. step 1, "the graph expansion step" of the graphplan algorithm) and how a plangraph could be used for heuristic estimation. Today’s class was all about how to extract a plan from the planning graph (i.e. step 2, "the extraction step" in the Graphplan algorithm) GRAPHPLAN ALGORITHM The Graphplan algorithm alternates between two steps: growing, searching, growing, searching, etc. Where "growing" stands for expanding the plangraph with one extra level of actions and propositions, and "searching" stands for trying to extract a feasible plan from the plangraph. Note that, plan extracting will never be successful if not all top-level goals are present in the plangraph or if they appear in the plangraph with mutex relations. BACKWARD SEARCH Solution extraction searches for a plan by choosing an action (or set of actions) at level i-1 that will achieve the propositions at level i. If Graphplan finds a consistent set of actions at level i-1, it will repeat the procedure over the union of all preconditions of those actions at level i-2 until it reaches level 0 or fails to support one of the propositions. As soon as one of the propositions cannot be supported backtracking will occur. In case backtracking fails on all the possible combinations, then Graphplan must expand the plangraph by (at least) one extra level. MEMOIZATION If at a certain level the supporting of propositions fails, graphplan will always fail to support these propositions whenever it enters that level again with the same propositions. Note that, even when graphplan returns to this level with a superset including these failing propositions it is guaranteed to fail too. In order to learn from the mistakes, the graphplan algorithm can be improved by using a memo that stores all the sets of propositions that fail to generate feasible plans. This memo list starts out as an empty list and becomes more and more populated along the execution of the graphplan algorithm. An example: assume the propositions (A, B, C} cannot be supported in level i. Then any set at level i that includes {A, B, C} as a subset cannot be supported either. EBL: One can either denote the whole proposition set or just the propositions that actually cause the failure. In the example, it could have been that {A, B} alone could not have been supported at level i. Finding out which propositions actually cause the failure speeds up the solution extraction time. Utility: One might argue that keeping track of memos takes up too much memory. Hence, if you remember lots of how you could save later, you might loose track of what you remember. The effects of spending extra time on determining these propositions are significantly less than the speedup gain. In general, one can conclude that backward search with short memos is better than backward search with full memos which in turn is better than backward search without memos. TUNING THE BACKWARD SEARCH Question: Are there any good ways of which propositions and actions you should choose during the backward search? Yes, from satisfiability we can adapt the following goal(variable), action(value) selection heuristic: - Pick the "hardest" to satisfy (i.e. with the least number of supporting actions) variables first. - Pick the "easiest" (i.e. with the least number of preconditions) values first. MORE ON GRAPHPLAN Recall, that actions are mutex when: 1) The effect of one action is the negation of another action’s effect (inconsistent effects) 2) One action deletes the precondition of another (interference) 3) The actions have preconditions that are mutually exclusive at level i-1 (competing needs) And propositions are mutex when: 1) One proposition is the negation of the other 2) If all ways of achieving the propositions are pairwise mutex (inconsistent support) Graphplan differentiates between static interference and mutex relations. Two actions interfere statically if the effects of one action are inconsistent with the effects or preconditions of the other action. Two actions are mutex if they statically interfere or have been marked mutex by one the mutex rules given above. Any search on a planing graph will return correct solutions as long as at least the static interference relations between actions have been marked out. In such as case, the memoization process will basically figure out the mutexes also. propagating marking 2-ary Mutex relations improve the efficiency of the backward search significantly (by making the failures happen earlier rather than latter). In contrast, leaving higher-ary mutexes are better left for discovery by memoiing [The tension here is of course the usual one--pre-processing cost vs. search cost.. Rao used the example of how long a kid should be trained before he/should be let loose on the world...] Note that, memos can also be seen as higher-order mutex relations that are learned on demand (in response to observed search failures) Optimality: The original Graphplan algorithm yields optimal plans in terms of the number of levels. It is not optimal in terms of the length (i.e. number of actions) of the plan. Also, when actions have different costs, Graphplan will not be optimal in terms of cost. Termination: When the plangraph levels off, Graphplan can still fail to find a feasible plan. There can be n-ary mutexes that where not marked during the expansion of the graph. Graphplan will really terminate when there are no more propositions introduced, no more actions introduced (actually does not matter), no more mutexes have been removed, and no more new memos have been discovered between two consecutive levesl. END Next class will cover how to convert the backward search into a CSP, SAT, IP encoding.