Partial Plan Representation: P= (A, O, L, OC, UL) where o A: set of action steps in the plan; o O: set of action ordering; o L: set of causal links; o OC: set of open conditions; o UL: set of unsafe links where p is detected by some action; Flaw: open condition OR unsafe link ------------------- POP algorithm ------------------- o Let P be an initial plan o Flaw selection: choose a flaw o Flaw resolution: o If f is an open condition, choose an action that achieves f; o If f is an unsafe link, choose promotion or demotion; o Update p; o Return NULL if no resolution exist o If there is no flaw left, return p else go to "flaw select" step. ------------------------------- Handling unsafe link flaws ------------------------------- For each unsafe link s_i -----> S_j threated by another step s_k. We have s_k between s_i and s_j, we can put s_k before s_j or s_i before s_k. In one branch we will put s_k before s_j, at another branch we put s_i before s_k. Now we have two branches and don't know which one to go. An idea is that we use disjunction as: S_k < s_j V s_i < s_k If we have disjunction, it has already resolved the problem. So we can only do open conditions, whenever there is unsafe link, we can just convert it to disjunction constraints. So we can come to a partial plan with no flaws left. No open conditions because we resolved the open conditions, no unsafe links because all unsafe links has been converted to disjunctions. Until now, is this plan correct? In the past, we may come to the point that the plan is correct. Now this plan is correct as long as the set of disjunctive constraints are consistent. The set of disjunctive ordering constraints checking whether they are consistent is NP-hard. Checking set of conjunctive ordering constraints is consistent is polynomial. If the original set of ordering is inconsistent, you will find the ordering s_1 before s_2 or s_2 before s_1. There might be an inconsistency, but for figuring out, it might take longer. For example: S_2 < S_1 V S_4 < s_3 Now we need to do case analysis. Most of the time we go all the way to the bottom, no open conditions, no flaws, to spend a lot of time to find the set of ordering constraints are inconsistent. Now we have to back track to look at different set of open conditions resolutions find consistent, back track and so on. Normally what we will do constraint propagation. Constraint propagation polynomial procedure will tell the inconsistency. If it says inconsistency, there would be inconsistency; if it doesn't say inconsistency, there could still have inconsistency. Mutex is like that. Whenever there is an disjunction, you will get opposite of one of the orderings then propagate it and simplify the ordering. Often times, you may be able to detect inconsistency much before the last minute. If detected the inconsistency, we don't need to resolve that partial plan and just back track. ------------------------------------------------------ Detecting indirect conflicts using reachability analysis ------------------------------------------------------ Generalizing unsafe link: p s_k threatens s_i ---> s_j iff p is mutually exclusive mutex with either Prec(s_k) or Eff(s_k). This is more general compared to the old definition. Once we find unsafe link, what should we do? We can check the ordering constraints. There are two ideas: One is to take open conditions and computing the cost of relaxing the plan length. The other idea is to work together, look at the conflicts using mutex and use disjunctions for unsafe links. -------------------- RePOP -------------------- RePOP was partial order planning that is like state space planning. Actions have more flexibility. RePOP is implemented in LISP. Definition: Makespan: ---------------------- Makespan is minimum completion time (number of time steps). Definition: Flexibility: ---------------------- Flexibility is the average number of actions that do not have ordering constraints with other auctions. Proving of the correctness is to tell what is relevant and what is not relevant. The idea for RePOP is Explanation-based generalization. If we know the general rule as to what makes the plan correct, if given a specific plan, trying to prove its correctness, we can actually figure out what are the other part of the plan which if remove will make the plan correct. Before RePOP there are tons of heuristics that which ordering to pick. An idea is to pick the flaw which has least number of resolutions, and pick the open condition which has the least actions that support it. Flaw selection strategy is nothing but variable ordering strategy. The above is not good. There is a better idea that values different resolvings have different cost. There is a particular condition that only have two way resolving it, but both of them, if pick either of chooses, you have to make a large amount of search to make the plan work. There is another flaw which have five ways of resolving it but they are pretty much to get done faster. The question is for each of the resolution, what is the cost of the resolution? One idea is that for every open condition; compute its cost using the reachable planning graph. Find the level which the open condition is present even with mutexes. Open conditions present at 15th level is normally hard that at 4th level, which we first pick. If we have two problems, we will try to do the hardest one first if no partial credit.