Notes taken by Romeo Sanchez. April 3, 2000. - Puccini (next class). - Make up class. Thursday 1:45 pm. You have basically two approaches to handle Planning with incomplete information. Either you implement Contingency Planning or Interleaving Planning and Execution. The tricky part of Contingency Planning is that in the time you are doing planning you really do not know which of the 2^m initial different states you are going to find yourself. Basically you go ahead and make a plan that has to handle many different initial states. Contingency Planning is a preplanning approach. Then you start to execute and observe in which states you are. A harder approach is interleaving. Try to find a part of the plan first and then execute it, and interleave between the two phases if you find any inconsistencies. When you do this approach you have to introduce sensing. There are some variations, for example you can say for contingency planning that you can deal with all possible contingencies or most likely contingencies and forget about the rest. Then Rao talked about Puccini. He explained that basically they want to extend UCPOP planners to interleave planning and execution, and sensing. This paper is one of the latest of a series of papers by the University of Washington on this topic. In contingency planning you can always finish getting bad solutions. The reason of this is that the 2^m plans will have a huge amount of overlapping. The plans you have from different contingencies do not need to be completely disjoint from each other. So, if you want to do the contingency planning efficiently you have to exploit this overlapping. After this you can introduce uncertainty. Uncertainty can be introduced in the causal actions and in the sensing actions. If you have uncertainty only in the causal actions you get normal MDPs. If you have uncertainty also in your sensing actions then you are dealing with a partially observable MDP (POMDP). How do you know what part of the initial state is already required for solving the goals? Initial state can be specified in term of n variables; where n can be a huge number. So, if there are m variables that are missing you can assume that all of them are relevant to the goals but that is not necessary the case. So, you can finish working in all different plans because of your assumption. Then, what you want to find is which of the m missing variables are really important to the top-level goals. The only way of figuring this out is by goal reasoning. That's why goal directed reasoning becomes more important in the contingency scenarios. In the Puccini paper they introduce the notion of knowledge preconditions, which basically tells me what the value of the variable is. Finally, try to change observations, in other words try to change only sensing actions and not causal actions. The rest of the class is based on the paper: Processing disjunctions in temporal constraints networks by Eddie S. and Rina D. Then, we went into a problem in TCSP. We could not figure out in class (we got different numbers) how the composition and intersection was done (with respect to the example given in the TCSP paper). What we agree is that we stop the procedure of computing these values until all precedence relations have true or false values. When you do precedence relations you get a simple temporal problem; a simple temporal problem is easier to solve. So, you try to make the composition cheaper by calculating an upperbound on a set of intervals (see picture in 72). Then you relax all the constraints with this upperbound value. For each edge in the constraint path every pair is a disjunction search. After this computation you can compute the minimal network cost. Basically you can do path consistency or the shortest path computation to get this cost. In computing the intervals you will never get more interval of what are present. Originally, you are not guaranteed to find inconsistency all the time. The next idea is the loose path consistency (the constraint you get is the original). The idea here is to loose the intersection. Basically here you keep only the minimum and maximum interval between all those. That's why is a kind of loose intersection. You need to keep your mind that when you compute this kind of intersection the constraints you get are really a super set of the original constraints. In other words loose intersection of two constraints C1 and C2 is really a super set of the real intersection of C1 and C2. After this we tried to compute the values from the example in the paper. But, we could not get the same values. It seems that the paper had some kind of inconsistency on the values. Dr. Rao did a Lisp module to prove the compositional and intersectional procedures in those values, the module is the following, you can run this under Lisp and you will get the correct values: (defun compose (c1 c2) (simplify (loop for int1 in c1 nconc (loop for int2 in c2 collect (mapcar #'+ int1 int2))))) (defun intersect (c1 c2) (simplify (loop for int1 in c1 nconc (loop for int2 in c2 collect (list (max (first int1)(first int2)) (min (second int1)(second int2))))))) (defun loose-intersect (c1 c2) (simplify (loop for int in c1 nconc (convex (intersect (list int) c2))))) (defun convex (c) (unless (null c) (sort c #'< :key #'first) (list (list (caar c) (second (car (last c))))))) (defun simplify ( ints) ;;remove degenerate intervals (setq ints (loop for int in ints when (not (< (second int) (first int))) collect int)) ;;sort them (sort ints #'< :key #'first) (rec-simplify ints) ) (defun rec-simplify (ints &aux co) (cond ((null ints) nil) ((null (cdr ints)) ints) ;;check if the first two intervals can be collapsed ;;if not check if the second two can be (t (setq co (collesce (first ints)(second ints))) (if co (rec-simplify (cons co (cddr ints))) (cons (first ints) (rec-simplify (cdr ints)))) )) ) (defun collesce (int1 int2) (if (null int2) int1 (if (intersect (list int1) (list int2)) ;;as long as the intersection is not nil (list (min (first int1)(first int2)) (max (second int1) (second int2)))))) For example you can run: (compose '((20 40) (100 130)) '((50 70) (110 120) (130 140) (160 190))) and get ((70 110) (130 320)) Or. (intersect (compose '((20 40) (100 130)) '((50 70) (110 120) (130 140) (160 190))) (compose '((-20 -10) (-110 -100)) '((80 100) (150 160) (180 190)))) and get ((70 90) (130 150) (160 180)) Basically you want to compute the composition for each of the paths and take the intersection of them. And then finally take the intersection of that with the original constraint. I suggest to read again the paper on TCSP in trying to understand composition and intersection since we could not get the same values of the example in the class. LPC will exponentially increase as the number of constraints increases and ULT can stay linear. They assume that the final problem should contain exactly one single temporal CSP, and they depend on doing the right inferences on that, but that is not always true. One of the worries is that if you run LPC or ULT you are not necessarily guaranteed to find the minimal consistencies. They also use backtracking methods in LPC and ULT for solving disjunctive TCSPs. The way they do is basically they try to do first LPC and ULT and find if there are inconsistencies, if not they take a network constraint and split the disjunction. And then work in each of those networks using LPC methods until they basically reach the original assignment. Next class: Talk in contingency and interleaving planning.