Date: 4-10-00 Note Taker: Megan Conway Exchanged with: Long Topic: Omnipotence without Omniscience: Efficient Sensor Management Planning by Keith Golden, Oren Etzioni and Daniel Weld ------------------------------------------------------------------------------ To be covered in the next few classes: Paper: Decision-Theoretic Planning: Structural Assumptions and Computational Leverage by Craig Boutilier, Thomas Dean and Steve Hanks Topic Note Taker 4/12 Sections 1 and 2 Long 4/17 No Class 4/19 Section 3 Terry 4/24 Section 4 Romeo 4/26 Section 5 Ullas 5/1 & 5/3 Presentations or information not covered from 4/12-4/26. Presentation topics include: dynamic environments, learning in planning, and information gathering **Note: midterms will be returned 4/12 or 4/19 with a letter grade ------------------------------------------------------------------------------- Rao planned on covering 1) LCW 2) observational vs. verification links 3) Can disjunctive planning in incomplete domains be done in anything other than UCPOP?? 4) overloading causal links Overloading causal links: Suppose P A -----> B Normal definition of a causal link: Effects of A generates P A gives P to B B needs P A is before B In the past papers we have discussed causal encodings have become a progamatic trick used to keep track of what has been done. In many causes the normal definition of a causal link is violated. For example, in the Golden paper Look Before you Leap: A < B is a observational causal link while B < A is a verification causal link. In today's paper LCW causal links P is not threatened by not P, but it can be threatened if an action that changes the domain encompassed by the LCW is introduced. In other works the negation does not violate the LCW causal link. By the normal definition of a a causal link, only negation violates causaul links. In addition, it may be possible that the LCW causal links only holds for part of the link. Thus, violations could occur that would not introduce threats. LCW Definition closed world: facts absent from the planner's world are false Definition open world: the truth values of facts absent from the planner's world are unknown and must be sensed Classiscal planning assumes a closed world assumption. Therefore, if p is not present in the initial state then the value of p is assumed to be false. When dealing with incomplete information, the planner cannot take a closed world assumption. It must assume an open world. Therefore, if p is not in the initial staten then the value of p is unknown. (This means that values that are false must be explicitly represented.) The open world assumption creates 2 problems: 1) Satisfying Universal Quantified Goals In a closed world universal quantifiers are extended to conjunctions of all the possible domain values. For example, x = {a, b, c} and a precondition for action S is for all x p(x). In a closed world assumption this precondition would become p(a) and p(b) and p(c). However, this is not possible in an open world because the domain of x is unknown. 2) Redundant Sensing Redundant sensing in some manners relates to execution as well as planning. While planning if you do not know the value of a certain fact do you need to sense the value or does is the information already stored in the knowledge base? In some environments, like UNIX, redundant sensing is not expensive. The operating system will preform a ls -a prior to every rm *, in order to determine the files in the directory. However, for robots sensing is expensive. Suppose, a robot sensed the distance from himself to the wall in order to determine his position. Every time he takes a step does he need to resense the distance from the wall if he knows that his steps are 3 inches? No. (To see expense of resensing check out table1 in paper) In order to address these two problems Golden, Etzioni and Weld introduce the concept of LCW or local closed world information. Specifically, LCW allows planners to solve universally quantified subgoals in incomplete worlds and helps reduce redundant sensing. In order to do this, as always, UCPOP is extended. Now there is a database of all ground literals known and their values. There is also a database containing LCW's representing where the planner has closed world information. For example, suppose directory Rao has files midterm.txt and grades.txt. When the command ls -a is performed parent.dir(midterm.txt, /Rao) and parent.dir(grades.txt, /Rao) will be added to the database of ground literals. In addition, LCW(parent.dir(f, /Rao)) will be added to the database of LCWs. In general ls -a will introduce the action descriptions or ground literals for all x, x in directory d parent.dir(x, d) and LCW(parent.dir(x,d)). The effects of all actions now include the ground literals and LCWs given. This yields a significant amount of information. If the planner wants to determine the value of parent.dir(foo, /Rao) it does the follow: 1) Check the database of ground literals. If parent.dir(foo, /Rao) is there get its value if not proceed to step 2. 2) Check the database of LCWs. If LCW(parent.dir(f, /Rao)) is present then you know all the files in /Rao and foo cannot be one of them. Therefore, the value of parent.dir(foo, /Rao) is false. If LCW(parent.dir(f, /Rao)) is not present then proceed to step 3. 3) Value is still unknown. The logic of LCWs is not discussed in this paper. For instance, suppose P(A) and P(B) you can check for entailment with the state of ground literals using normal logical entailment. But if you have LCW(parent.dir(f, /Rao)) and LCW(length(f, /Rao)) can you infer LCW(parent.dir(f, /Rao) and length(f, /Rao))? That is, can you infer that you know the length of all the files in Rao? Not sure. For the purpose of this paper you should assume that the database of ground literals and the database of LCWs are only used as a lookup tables. No other inferences can be made. There are two ways to support universal quantified goals w/ LCWs 1) Introduce an action with a for all effect. for all y p(y) x=y A ---------------------> S for all x p(x) Example, rm *. 2) Try to sense the domain of the fact lcw(p(x)) A -----------------------> S for all x p(x) and lcw(p(x)) *lcw(p(x)) as precondition for S becomes a secondary precondition In normal partial order planning you can resolve any flaw at anytime, but for LCW this is not the same. If you resolve the LCW prematurely the universal base (domain) found will not have all of the appropriate values. Therefore, you want to deal with all flaws related to universally quantified goals until the LCW is achieved and then reduce the flaw. (By reduce the flaw I am expand the universally quantified goal to the universal base or conjunction of all possible domain values.) There are two ways to get an LCW 1) Some action in the planning process "promises" the LCW. This means LCWs become subgoals by establishment and protection or the same as any other goal. In addition, because the action is "promising" the LCW the LCW must be protected. At this stage threat resolution is the same as always. Threats can be resolved using promotion, demotion or confrontation. 2) Execution Perform the action that promises the LCW then extend the for all statement to support all of the necessary actions and execute them. This is done so the LCW does not get clobbered. Example, imagine you want to remove all the files in directory /Rao. You do not know what files are in /Rao, and there is not a rm * command. Thus, each file has to be removed separately. Also, suppose midterm.txt and grade.txt are in /Rao. Have partial plan: LCW(parent.dir(f, /Rao)) 0 -> A --------------> A2 remove files from Rao A = ls -a for all x parent.dir(f, /Rao) and LCW(parent.dir(f, /Rao)) Even though the causal link giving LCW(parent.dir(f, /Rao)) is present. For all x parent.dir(f, /Rao) is not supported. In fact, the for all x parent.dir(f, /Rao) precondition cannot be satisfied until A is executed. Then, like normal, UCPOP can extend the universal quantified precondition because the domain of x is known. After A1 executed LCW(parent.dir(f, /Rao)) 0 ----------------------------> A2 remove files from Rao parent.dir(midterm.txt, /Rao) and parent.dir(grades.txt, /Rao) and LCW(parent.dir(f,/Rao)) Two types of threats may be added to the plan at this point. Any action which occurs between 0 and A2 and causes one of the following is a threat: 1) domain growth In our example the action touch Rao/foo.txt would add an element to the directory Rao. Thus, A2 would not be able to remove all the files from Rao because it would not know foo.txt is present. To resolve this problem you can enlarge the LCW to include the new file. That is add parent.dir(foo.txt, /Rao) to the preconditions of A2. You can also shrink the problem by making sure the new item is not in the domain of the LCW. That is move foo.txt to another directory. 2) knowledge loss For instance, suppose I know the file size of all of the files in Rao. Then I compress midterm.txt. I no longer know its size. In order to handle this threat I would need to shrink the problem (make sure the file changed, midterm.txt, is no longer in the domain of the LCW). Like before, you could move midterm.txt to a new directory. (Rao's thoughts on shrinking: Does this method of handling the problem satisfy semantics? Suppose you want to count the number of non-text files in a directory. Why wouldn't you list all of them and then move all the text files to a different directory and then count? Is this appropriate?) During all of the interleaving of planning, execution and sensing when is the finish point determined? Say the effect of action O1 is A, the effect of action O2 is b and the goal state is A and B. While planning action O1 gets executed, thus statisfying A of the goal state. Along the way if A becomes untrue an action making A true again will be added. (The truth value of A must be ensured.) On the other hand, if action O1 and O2 get executed giving the goal state, even if A and B become not true immediately after O1 and O2 are executed the planner will believe it is done because the goal state has been reached once. Is it really done though? Overview classical planning represents the closed world assumption and all of the actions are causal LCW represents somewhere in between a closed and open world. The actions are both causal and observational information gathering represents the open world assumption and all of the actions are obeservational UCPOP or Bust Both graphplan and state based planners use good search control heuristics. However, UCPOP does not making it slow. Yet, UCPOP is extemely extendible both as far as temporal and incomplete problems go. But how can UCPOP be made scalable? What heuristics are needed to guide flaw selection and resolution. Golden himself admits that if a low cost action is executable then it is automatically executed. High cost actions will be executed later. (Golden did not tell Rao how low and high costs were assigned.) Without any heuristics UCPOP with or without additions for temporal or incomplete problems will continue to work at snails space. We must also wonder why graphplan and state-based planners have not been extended or why there isn't any easy way to extend them. (There is one state based system called POMDP that uses belief vectors. Rao said we would see more about this later.) Finally, Rao wonders if so far the technique isn't driving the theory. He isn't saying he knows of a better way, but wonders if the AI community is taking the wrong approach. Could there be a universal technique of dealing with incomplete worlds that can be used for all or most planners not just for UCPOP?