PLANNING GRAPH WITH MUTEX RELATIONS: ---------------- Question 1: ---------------- A set of subgoals {p,q,r,s} have mutual exclusion relations among them and appear together for first time at step 12 without any pair being mutex. The question is that is there guarantee to be a plan to achieve {p,q,r,s} using 12-step plan? Assume that {p,q,r,s} were not presented in earlier levels. Answer: -- Not guaranteed. If it's guaranteed, that means planning for solving a problem can be done in polynomial time. In this case, only pair is considered. There could be triples and quadruples of literals that are mutually exclusive. ----------------------------------------------------------------------- Bounded length planning means finding a plan of length k for particular problem, I'll say no, it doesn't exist a plan for length k. That is a NP-complete problem. Bounded planning is NP-complete. If you don't have bounded number of length, then the problem is PSpace-complete. PSpace-complete means the hardest problem can be solved in polynomial amount of space. In general, there are problems that can be expressed as planning problems, whose solution can be exponentially long. ------------------------------------ Example: Tower of Hanoi problem ------------------------------------ We are given a tower of n disks (initially 3 in the applet below). The objective is to transfer the entire tower to one of the other pegs (the rightmost one in the applet below), moving only one disk at a time and never a larger one onto a smaller. The question is how can you do it? _ _ ____ | | | | | | | | | | __|____|_ | | | | | | | | | | __|_________|__ | | | | | | | | | | | | | | | | -------------------------------------------------------------------- To do three, you will do two recursively multiple times. The size of the plan is 2 power the number of pegs. We can write Hanoi very easily as the planning problem, which means the solution length itself can be exponential in the size of specification. ---------------------------------------------------------------------- The class NP requires that the solution of the problem can be verified in polynomial time. Otherwise, it is not in the class NP. If the solution itself is exponentially long, you will not be able to check its correctness in polynomial time. For Hanoi problem, there do have plans, which are not exponential, but rather polynomial in the size of specification. In those cases, they will be only NP-complete. But either way computing the planning graph is a polynomial time activity. Planning graph construction is can be done in linear time. --------------- Question 2: --------------- If {p,q} appear in level 12 without being mutex, is there a guaranteed 12-step plan to achieve {p, q}? Answer: No. There is no such guarantee. There could be more than one pair mutex. Suppose A1 supports p and A2 supports q. A1 requires 100 preconditions, A2 requires 200 preconditions. So the set has 300 literals, still doing pair-wise mutexes. There might have been triples, quadruples,...,all the way up to 299. Which are mutual exclusive that we didn't consider. ----------------------------------------------------------------------- Planning problems are NP-complete, no matter how many goals there are. Suppose given a planning problem with 100 subgoals. We can make the planning problem with one goal, which would be as least as hard as the 100 goals problem. Just add a dummy operator, which requires those 100 subgoals as preconditions and output is to be "I'm done". The point is that you should not think that the number of things left to do, is all about how hard things really are. ------------------ Question 3: ------------------ If {p} appears in level 12 without being mutex, is there a guaranteed 12-step plan to achieve {p} with? Answer: No. It's all depends on the preconditions supporting p might have 100 subgoals. ---------------------------------------------------------------------- ------------------- CSP problem ------------------- CSP is better understood as Consistency Enforcement CSP problem. A CSP problem has n variables that have domains. There are certain constraints on the values these variables can take. The problem is to find an assignment of values to all the variables such that all the constraints are satisfied. A traditional CSP problem is the eight queens problem. CSP Consistency Enforcement: a particular CSP is considered k consistent. If you take a k-1 assignment, which can take k-1 values for the k-1 variables, it's legal assignment for k-1 variables. Every legal assignment for k-1 variables will be extended to a given k variables. If given assignment of k-1 variables, we pick kth variable from the remaining n-(k-1) variables. If we can do it for every kth variable and every k-1 assignment, it's called k-consistent. In CSP k consistency requires n power k time, which is only polynomial. If you fix the k, n power k is polynomial. With entire CSP problem solving requires n power n, which is exponential. So the CSP problem is a NP-complete problem. PG does approximately reachability analysis. ------------- Question 4: ------------- On the opposite, if {p,q} does not appear in level 12, are you sure it does not have a 12-step plan. Answer: Yes. Heuristic H_sum tends to do better sometimes than H_lev (and vice versa), where here "do better" means it will solve more problems give certain amount of time. Once you get out of the admissibility, you no longer have any guarantee on optimize. For some examples, Sum doing much worse in most cases. Those heuristics don't give constant approximation. ------------------------- Degree of of interaction ------------------------- Given two literals of p and q, the degree of interaction is: Lev({p,q}) - max{level(p), level(q)} If p and q don't have negative interactions, that means p and q cannot be done together at all, the degree of interaction is infinite. If p and q can get along, the degree of interaction will be zero. Given a set S which has {p, q, r, w}, we want to compute heuristic value, we take H_sum(s) + {some number based on delta values}. For the delta value, we have $\delta(p,q)$, $\delta(q,r)$, ... - One idea is to do sum of them. - the other idea is to take the maximum of all of them. The theory of admissible heuristic doesn't not exist. In the paper, they tried sum of delta(P_i, q_i), and they tried max(p_i,q_i). In this paper, the max seems to work better. Sum heuristic doesnĄ¯t count positive interactions, but Level heuristic counts both positive and negative interactions. Relaxed plan, which ignores negative interactions, basically takes positive interactions into account. ----------------------------- Adjusted Sum Heuristic ----------------------------- One idea would be in front of planning graph, ignore the mutexes, then have the planning graph with positive interactions. Given a set {p,q}, start from p and q, pick an action for p, pick an action for q, pick preconditions... do this greedy actions, try to pick actions that try to help more than one goal. That's will give the relax plan length. Adjust Sum Heuristic is to take positive and negative interactions as follows: HAdjSum(s) = Length(RelaxedPlan(s)) + max p,q $\in$ S $\delta(p,q)$ If want to keep admissibility and do better than set level, the obvious idea is you consider higher other mutexes. In planning graph, doing pair-wise mutexes is the best place to start. ----------------------------- Partitioning Heuristics ----------------------------- Partitioning Heuristic is the following: Suppose have a set S have {p_1, ..., P_100}, -- if all of them are independent, we can take H value of all them and add them. -- if known (p_1, ..., p_7) connected, (p_8 - p_57) connected, (p_59 - p_100) connected, take levels for each and add them. It's not obvious to find a good way to find good partitions. Think a CSP problem p1, and a CSP problem p2. p1 has variables x1, ..., x100 and some constraints; p2 has variables y1, ..., y200 and some constraints. There are no constraints between x's and y's at all. The worst problem solver solve p1 in 100s, and p2 in 200s. Given p1, p2 to any solver, in general it should be solved in 300 seconds. If given to best CSP solver, the time is 100*200 seconds. Checking the independency is as hard as solving the planning problem. ------------------------ AltAlt Optimization ------------------------ AltAlt is regression planner. It only has to computer the planning graph once, not more than once. Computing the planning graph takes time. It might run out of space by just computing the planning graph. Cost of computing of heuristic could be high, and the space could be also high. ------------------------------------------ Bi-level Planning Graph Representation ------------------------------------------ Planning graph has k level, but someone come in at level four and dead, and all the level afterwards. Similarly once the mutex goes out, it is gone forever. Those are two important structural properties the planning graph has. -- For proposition, we only need to know what is the fist level it appears, since after that it just repeat it every time. -- For the actions, we only need to know What the first level it came in. -- For mutex, the only we are interested in is what is the first level it went away. After that, it's just gone. Here is the idea: forget the multiple level in planning graph, all you care is action set and proposition set. For action set, each action have a number indicating that what's the first level the action is in; in proposition set, each proposition will have a number indicating that what's the first level the proposition in. We have the mutex information, for any pair of actions; remember the first level where the mutex went in. If we have those things, you have all the information we need. Those are compact information for the planning graph. It takes less time and less space. Bi-level planning graph is interesting: When action has durations, how could we have normal planning graph? How do we use those actions to make a planning graph? For general consider smallest time piece, and that's the level. But for bi-level planning we still have propositions and actions. Previous number associated with actions and propositions used to be integer, now we could have floating point number. ---------------------------- a1 ----------------------- a2 -------------- a3 -------- a4 Example: action a1 comes in at 1.7534 seconds, 3.798 second later proposition p1 come in. -------------------------- Partial Extension of PG: -------------------------- Ideas: do we need the entire planning graph? E.g., if we are only given 15 seconds to do our heuristic computation. If we missed mutex, will we lose? It might take more time, but we don't lose our completeness. Suppose if something we should put in this level, would we lose? No. We could decide how far we want to expand the planning graph. There are two ways to decide when to stop: -- stop when nothing more happens, but takes longer; -- Suppose we are interested in some particular problems which has g1 and g5 as top level goals. We might extend the planning graph until g1 and g5 come into the planning graph. Example: p, q are mutex. The cost of p,q together for the first one is for the second way, we might come to level 7 and p,q don't appear together. We can say the cost is at least 8. If the actual cost is infinite, but we thought it's 8, what do we lost? We lost informedness. If we do partial extension of PG, it will reduce the speed of search. We are not as informed as the others. If use level heuristic on partial and complete planning graph, since both are admissible both of them give the quality of plan. AltAlt uses the best heuristic, which is taking, relax plan length and add it to the degree of negative interaction, which is admissible. Using regression search, every action that is relevant will be put into search tree. Then we evaluate which branch is better using the heuristic. When construction a planning graph, we spending more time on computing the mutexes instead of drawing the graph. We could decide only a certain time on mutex if we could not find mutex in certain time just ignore it. This is a approximation in the sense that it's not incomplete since if we already missed 2 mutexes what's the matter if we missed the 3rd one. ---------------------------- Question 5: ---------------------------- If we do the entire analysis on the planning graph, is it guaranteed that we find all mutex at particular level? Answer: No. The reason is the same as the first three questions. It's partial two consistencies.