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.