INTRO In previous classes we talked about different search methods. We discussed state space search like progression and regression, and plan space search like partial order planning. We also talked about heuristics to guide these searches. Today’s class talked about a special data structure called a planning graph, which can be used to give better heuristic estimates for each of the search techniques. PLANNING GRAPHS A planning graph consists of a sequence of levels that correspond to time steps in the plan, where level 0 is the initial state. Each level contains a set of literals and a set of actions. A simple example O1 Pre: B Eff: ~A O2 Pre: ~A Eff: ~B I = {A,B} A ----o---- A ----o---- A ----o---- A ~B ----o--- ~B __O2__/ __O2__/ / / ~A ----o--- ~A ----o--- ~A __O1__/ __O1__/ __O1__/ / / / B ---o---- B ----o---- B ----o---- B State level 0 1 2 3 Action level 0 1 2 In order to represent inaction (allowing a literal to remain true from one situation to the next) dummy actions (“----o----” in the graph) are used. These actions are better known as persistence actions or no-op actions. Persistence action requires the literal persisting is shown and return back. There are as many no-op actions as there are literals. Recall that a literal is either an atom or the negation of an atom. Total number of literal is finite, some literals never come since they are not reachable. Each succeeding level contains all the literals that could result from picking any subset of actions from the current level. When two consecutive levels are identical, we say that the graph has leveled off, in the example this will be level 3. There can be at most 2^k (read 2 power k) levels. USING PLANNING GRAPH FOR HEURISTIC ESTIMATION Planning graphs can be used to estimate the cost of single and sets of literals. For single literals it is the index of the first level in which it appears. Hence, the cost of literal i, is the level of literal I in which it first appears. Using the example above we have - h(A) = 0 - h(B) = 0 - h(~A) = 1 - h(~B) = 2, where h() represents the cost function. For sets of literals we have three cost measures: - [sum] h_sum({~A, B}) = h(~A) + h(~B) = 1 + 2 = 3 - [max] h_max({~A, B}) = max{h(~A), h(B)} = max{1, 2} = 2 - [level] h_level({~A, B}) = 2 (is the first level in which all literals in the given set appear) These cost measures are used to assign values for partial plans generated by the search methods we have discussed in class. They guide us through the search space, by pointing out the seemingly better branches. The sum-measure is an inadmissible heuristic, whereas the max- and level-measure are admissible heuristics. In planning graphs without mutex relations (will be discussed later in this summary) the cost measures max and level give equal estimates. The sum-measure is inadmissible because it ignores positive interaction. If an action has multiple effects, sum might overestimate the true cost. Sum ignores negative interaction too. If two literals are mutually exclusive, sum might underestimate the true (infinite) cost. Recall, that admissible heuristics find optimal plans whereas inadmissible heuristic might not find optimal plans. However, in often times the sum-measure is (and inadmissible heuristics in general are) much faster in generating plans than the max- and level-measure (admissible heuristics). MUTEX RELATIONS Both actions and literals can be mutually exclusive (mutex). Two actions O1 and O2 are mutex if: (1) Both of the actions are non-no-op actions. (2) O1 is a no-op action supporting A, and O2 either needs ~A or gives ~A. (3) Some precondition of O1 is marked mutex with some precondition of O2. Two literals A and B are mutex if: All actions supporting A are pair-wise mutex with all actions supporting B. In our example given above we can add the mutex relations. By default the pair of literals representing an atom and its negation are always mutex. Hence, A and ~A, B and ~B, are mutex. An example of mutex actions can be found in level 0. Here O1 is mutex with no-op(A) because of point (2). Another example of mutex actions can be found in level 1. Here O1 is mutex with O2 because of point (1). In planning graphs that include mutex relations we can use the same sum, max, and level cost functions. However, the level-measure is now represented as: - [level] h_level({~A, B}) = 2 (is the first level in which the set of literals is present without any mutex relations between them) It is important to note that although pairs of actions or literals can be feasible, triplets (or even higher order combinations) of these actions or literals may not. Termination of planning graphs is guaranteed. Literals increase monotonically (literals cannot disappear once present in the graph), actions increase monotonically (if preconditions appear at one level, they will appear at all subsequent levels), and mutexes decrease monotonically (if two actions or literals are mutex, then they will also be mutex for all previous levels at which they both appear). FF PLANNER The FF planner (today’s most competitive planner) is a progression planner and computes a planning graph at each state. This seems to be inefficient, because in a regression planner one has to compute the planning graph only once. However, in practice, FF planner (progression) wins from regression based planning graph heuristics. The culprit in regression is that you are dealing with partial states, which contain less information than the consisted states dealt with in progression. RELAXED PLANS A relaxed plan is easier to solve than the real plan. An example of a relaxed plan would be to ignore all the mutex relations (negative interactions). Unfortunately, finding the optimal plan in such a relaxed plan is still NP-complete (i.e. “hard” to solve). Another example of a relaxed plan is to ignore negative interactions. Example, cost of set S is the lenght of the relaxed plan to support S. On-A-B is plan, the lenght of the relaxed plan is 2 since there are 2 actions St-A-B & Pick-A are counted. There might be multiple relaxed plans, so choose the minimum cost for calculating the length. Question: Can the level-measure have a lesser value than the length of a relaxed plan? Answer: Yes because the planning graph allows parallel actions. Note that, in a serial planning graph where only one action can actually occur at any given level, the answer would be no. An adjusted heuristic is to combine the sum-measure with the length of the relaxed plan. More about this in next class...