Note taker: Terry Zimmerman (zim@asu.edu) Date: April 5, 2000 Subject: SENSING & INCOMPLETE INFORMATION IN PLANNING Papers addressed: "Planner-based Softbots" :slide presentation by Keith Golden "Leap Before You Look: Information Gathering in the PUCCINI planner" -Keith Golden There are 4 major issues that we're hoping our understanding is 'gelling' about: 1) How should we represent sensing in planning? NOTE: for the next couple lectures we assume that sensing has deterministic effects --when we make an observation, we know. 2) How do we reason about incompleteness in our knowledge? (e.g. we have an incomplete initial state) We can actually attempt to handle the 2nd issue without sensing at all... (Note that even if you have the capability to do sensing, you may not want to do it --it may be too "expensive") a) "Conformant plans" -a plan that irrespective of the initial state will take you to the goal state. (recall the "bomb in the toilet" problem) Unfortunately, not all problems/domains have conformant plans. b) "Conditional plans" -a type of disjunctional plan corresponding to various important possible states. Worst case: 1 plan for each possible init state. When you have an incomplete init state specification: What happens when you perform an action? -Incompleteness changes... in fact, you may actually REDUCE it (if you don't know which files are in a directory and do rm *, you've settled the issue!) 3) How should you use sensing as part of planning? Typically we now have sensing goals. Classical planning never had a goal such as "check if A is on B". How do you handle sensing effects and goals in, say, UCPOP? 4) How do you interleave execution with planning? This is relevant even for complete init state problems (e.g. if the world is dynamic or you have incomplete models of actions...) Example: You have the task of buying a car for someone. Possible approaches: 1) Irrespective of color we'll buy it from the same place. 2) Determine where you'll buy it based on color... color1 -get it in Phx color2 -get it in L.A. Here a conditional plan is a good idea. 3) There are 1000 colors, each requireing a different purchase plan. Here it makes sense to ask the user about color preference first. But we don't want to ping the customer for a decision on EVERY variable -some are probably not important. The real world is complex and doesn't always cooperate. Even when we want to sense we may not be able to. In such a case we're forced to do conditional (or contingency) planning. In any case, we will generally be well-advised to consider the cost of sensing and the other options. It's not wise to always insist on sensing... it may be VERY costly. For example, suppose the only way to gain information on the enemy's troops and armament is to physically go to the battlefield to observe. Contingent plans allow: pre-planning (an advantage since planning takes time) : advance preparation (if enemy's troops are in tanks instead of on horseback you may want your troops to have heavy armor --this takes prep time) In domains where there are ~infinite domains for variables we're forced to sense & query. If we don't have to worry about incompleteness and dynamic worlds (ie classical planning) there's no compelling reason to interleave execution with planning. When we have to deal with incompleteness we HAVE reasons. Concerning the 4 major issues described above: 1) We cover this today -much of this comes from Univ of Wash work (Golden, Etzioni, Weld) 2) Partially cover --only Golden, et. al. deal much with this 3) We'll consider doing one of two things: 1. develop a contingency plan 2. always do sensing when uncertain The Russel & Norvig Ch 13 handout (up to Sect 13.2) discusses ONE way to appoach this --it's not obvious that it's the best way. May read Ritalen paper for another approach. 4) This is a real problem... Execution may make finding a solution impossible! Whereas search is always revocable (we can backtrack) execution may be irrevocable. What are the minimum things we can do to avoid "painting ourselves into a corner"? Consider the preconditions of sensing actions: e.g. sensing troop status has preconds --be on the battle field, and being on the battlefield requires a huge plan of it's own. Lots of people believe that, where issue 4 is of concern, you want to build your plan in the 'backward' direction (goal regression). Contingency planning, on the other hand, is in the forward direction. Readings: Section 13.3 of Russel & Norvig, "Leap Before You Look" -Golden (understand the SADL action descripts) Rao now discussed the "Planner-based Softbots" slide presentation handout. Slide 1: the internet softbot make a nice alternative example to the typical real-world physical robot (which has non-deterministic sensing) Slide 3: Action Representation STRIPS & ADL are less general than situation calculus (must describe all side effects, etc.) UWL adds incompleteness to situation calc starting from STRIPS (Golden starts with ADL) In addition to Moore et al, there is more recent work in Hector Levitz(?) group in Toronto. Knowledge Representation OWA -Open World Assumption: unless I know a certain proposition is T/F, I can't say anything about it. Golden says that their work falls somewhere between OWA and Circumscription Slide 5: Motivation -actions we couldn't previously represent When printing all files in a directory we can use Unix lpr * . But, interestingly, after the action executes we STILL don't know the files in the directory. Renaming a file is even harder. The object referent itself is changing. Note that ADL allows us to quantify over all objects (Forall x clear(x) ) so afterwards the planner just needs to handle unquantified goals. But the approach here allows you to achieve goals w/o knowing the full domain over which those goals range. Consider Fig 3 in "Leap Before You Look" paper: action ls(d) precond: satisfy (current.shell(csh)) effect: forall !f when in.dir(!f, d) exists !p, !n observe (in.dir(!d, d)) ... The "when" clause looks like a conditional effect, but it doesn't necessarily have to be "achieved" in order to have the observe effects. Note that it's self-referent: in.dir appears in condition and observe effect. Slide 7: Shows the ancestry of the SADL action-description language. Slide 8: SADL/UWL Annotations In addition to the 2 types of goals indicated here (satisfy and hands-off) the paper adds a "initially" type: value before planning has started. Slide 9: Information Goals are Temporal Note: they don't do full temporal modeling. Time is not explicitly represented. Slide 10: Here the 'f' runtime variable is required to enable the renaming by pointing to the same object. This would be easy with explicit time representation but PUCCINI doesn't have it. Note the last clause on the slide representing a goal of deleting a core-dump file. Here it's not sufficient to just say "satisfy(deleted(f)) where f=core because then one solution would be to first create 'core' and then delete it! Slide 11: Tidiness Goals. Here we just want to leave the file in the same state it was before we acted. The tv runtime var is used here when sensing a condition, saving it, and then ensuring the condition is reset to it's original value. ------------------end of lecture ----------------------- The make-up class for April 17th will be tommorrow GWC rm 308, 1:45PM Reading: Russell & Norvig Chap 13. This is a more simple model of sensing than Puccini (top-level goal is still causitive -not observational)