ebook img

NASA Technical Reports Server (NTRS) 20020061363: Leap Before You Look: Information Gathering In the PUCCINI Planner PDF

9 Pages·0.8 MB·English
Save to my drive
Quick download
Download
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview NASA Technical Reports Server (NTRS) 20020061363: Leap Before You Look: Information Gathering In the PUCCINI Planner

ICU 5 Leap Before You Look: Information Gathering in the PUCCINI planner Keith Golden NASA Ames Research Center M/S 269-2 Moffett Field, CA 94035-1000 kgolden _ ptolemy, arc. nasa. gov (650) 604-358.5 Abstract in failure, we know that if we search long enough, we are likely to find what we're looking for. Pinocchio's at- Most of the work in planning with incomplete informa- tempt to lift the cover from the pot is also familiar, since tion takes a "look before you leap" perspective: Ac- attempts to open locked doors or copy read-protected tions must be guaranteed to have their intended effects files result in similar frustration of our expectations. before they can be executed. We argue that this ap- What these activities have in common is some precon- proach is impossible to follow in many real-world do- dition that we assumed to be true, but later found to mains. The agent may not haw_ enough information to ensure that an action will have a given effect in advance be false. of executing it. This paper describes PUCCINI, a partial- We are interested in the problem of building agent.s order planner used to control the Internet Softbot (Et- that can solve user goals in software environments, such zioni & Weld 1994). PUCCINI takes a ditferent approach as the Unix operating system or World Wide Web, in to coping with incomplete information: "Leap before which the agent has massively incomplete (but correct) you look!" PUCCINI doesn't require actions to be known information about the world. One such agent is the to have the desired effects before execution. However, Internet Softbot (Etzioni & Weld 1994). Internet re- it still maintains soundness, by requiring the effects to sources and Unix commands are represented as planner be verified eventually. We discuss how this is achieved using a simple generalization of causal links. actions, and a planner, called PUCCINI, 2 is used to find some combination of these actions that together will achieve the user's goal. Introduction It should not be surprising to anyone who has looked A boy's appetite grows very fast, and in afew moments for something on the Web that agents in such environ- the queer, empty feeling had become ]ranger, and the ments could spend much of their time searching for files hunger grew bigger and bigger, until soon he was as ravenous as a bear. or Web pages in much the way that Pinocchio searched for something to eat. However, most planners that Poor Pinocchio ran to the fireplace where the pot was deal with incomplete information don't behave nmch boiling and stretched out his hand to take the cover off, but to his amazement the pot was only painted! Think like Pinocchio. how he felt! His long nose became at least two inches Most planners, by adopting some form of knowledge longer. preconditions (Moore 1985), require the agent to know, He ran about the room, dug in all the boxes and draw- a priori, that an action will have some desired result. As ers, and even looked under the bed in search of a piece we argued in (Golden & Weld 1996), and will briefly dis- of bread, hard though it might be, or a cookie, or per- cuss here, these knowledge preconditions are represen- haps a bit of fish. A bone left by a dog would have tational handcuffs, which make action representations tasted good to him! But he found nothing .... more awkward and limit the utility of our planners; our Suddenly, he saw, among the sweepings in a corner, action language, SADL, eliminates them. In this paper, something round and white that looked very much like we show how a simple generalization of causal links al- a hen's egg. In a jiffy he pounced upon it. It was an lows a planner to exploit the elimination of knowledge egg. preconditions, without giving up soundness. We show -- Carlo Collodi, 1 The Adventures of Pinocchio empirically that this added expressiveness does not de- Pinocchio's search for food is evocative, in part, be- grade planner performance. cause it is so familiar. Whether looking for food, a pass- The remainder of the paper is organized as follows. port, or information on the Web, we have all had the experience of searching exhaustively for something until 2puccINI stands for Planning with Universal quantifi- we find it. Even though any single action, such as open- cation, Conditional effects, Causal links, and INcomplete Intormation. PUCCINI is a partial-order planner based on ing a drawer or looking under the bed, is likely to result ucPop (Penberthy & Weld 1992). An earlier version of 1Translated from the Italian by Carol Delia Chiesa PUCCINI Was called XlI. First, we introduce the flmdamentals of the SADL lan- it. should know whether P was true when it started. guage and the PUCCINI planner. Then, in the next initlally(P) is not achievable by an action that changes section, we briefly discuss the problem with knowledge the fluent P, since such all action only obscures the ini- preconditions. Although knowledge preconditions, as tial value of P. However, changing P after determining inflexible requirenlents of the planner, are harmful, it its initial value is fine. By combining initially with is still necessary for the planner to gather information satisfy we can express "tidiness" goals: modify P at in support of planning. In the following section, we will, but restore its initial vahte by plan's end (Golden show how that is done in PUCCINI. Then we consider & Weld 1996; Weld & Etzioni 1994). Furthermore, we the option of assuming that certain preconditions hold, can express goals such as "Find the the file currently performing the action, and verifying the preconditions named paper, tex, and rename it to kr. tex," which is afterward. Finally, we evaluate the cost of this added beyond the expressive power of most planners (Golden flexibility. & Weld 1996). 'the hands-off annotation indicates a maintenance Back in the SADL goal that prohibits the agent from changing the fluent in question. PUCCINI goals and actions are described using the lan- Like ADL, SAI)L also supports universal quantification guage SADL,3which builds on UWL (Etzioni ct al. 1992) and conditional effects. Combining these features with and AOL(Penberthy 1993). Like UWL, SADL is designed observe effects yields expressive sensor models, such to represent sensing actions and information goals. To as those shown in the next section. distinguish sensory effects from causal effects and goals of information from traditional goals of satisfaction, PUCCINI overview SADC provides annotations for goals and effects. PUCCINI is a partial-order planner in the same family as Following UWL, SADL divides effects into those that SNLP (McAllester &:Rosenblitt 1991) and ucPop (Pen- change the world, annotated by cause, and those that berthy & Weld 1992). It builds plans incrementally by merely report on the state of the world, annotated by starting with an empty plan and a goal agenda of goals observe. Executing actions with observe effects as- that need to be achieved. When goals are achieved, signs values to runtime variables that appear in those they are removed from the goal agenda. When actions effects. By using a runtime variable (syntactically iden- are added to tile plan in support of goals, their pre- tified with a leading exclamation point, e.g. !tv) as a conditions are added to the goal agenda. This process parameter to a later action (or to control contingent ex- continues until the goal agenda is empty or some goal ecution), information gathered by one action can affect prowls impossible to achieve. When a goal has been the agent's subsequent behavior. For example, ping "achieved" by adding an action to the plan, we nmst twain ha.s the effect of observe (machine.alive(twain), guard against the possibility that some other action !tv), i.e. determining whether it is true or false that the added later will "clobber" the goal, forcing the planner machine named twain is alive, and wc my:file has the to re-achieve it.. To prevent this from happening, the effect observe (word.count(myfile, !word)), i.e. deter- planner adds a causal link (Tare 1977), which records its mining the number of words in myfile. The variable commitment to achieve a given goal by using the effect. !tv, above, is the truth value of the proposition ma- of a given action. If effect e of A1 is used to support chine.alive(twain). All literals have truth values ex- precondition q of A2, we represent the corresponding pressed in a three-valued logic: T, F, U (unknown), or causal link as AI_A.2. A1 is required to precede A2 so represented by a variable. If a truth value is not speci- that q will be achieved by the time it's needed. Any fied, it defaults to T. change to the plan that would violate the causal link Goals are similarly annotated. The goal satisfy(P) is called a threat to the link, and must be resolved by indicates a traditional goal (as in ADL): achieve P by the planner. For example, an action At with the effect. whatever means possible. In the presence of incom- -_qpossibly occurring between actions A1 and A2 would plete information, we make tile fllrther reqnirement that the agent knows that P is true, so satisfy(P) threaten the link AI_-_A2. This threat might be resolved means that KNOW(P) nmst be true in the final state by adding an ordering constraint to ensure that At is of the plan. Free variables are impli,:itly existentially executed before A1 or after A2. In addition to achieving quantified, and the quantifier takes the widest possible goals on the goal agenda and resolving threats, PUCCINI scope. For example, satisfy(in.dir (jr, tex), T) means must execute actions. These three procedures comprise "Ensure that there's at least one fil_,in directory tex," the top-level PUCCINI algorithm (Figure 1). This paper and satisfy(in.dir (myfile, rex), tv) means "Find out only focuses on a narrow aspect of the goal achieve- whether or not myfile is in tex." ment procedure (Figure 6). For a discussion of the The initially annotation, introduced in (Golden & other aspects of the algorithm, consult (Golden 1997; Weld 1996), is similar to satisfy, but it reh'rs to the Etzioni, Golden, & Weld 1997). time when the goal is given to the agent, not to the time Knowledge Preconditions when the goal is achieved, initially(P, tv) means that by the time the agent has finished executing the plan, Knowledge preconditions are meant to capture the in- formation needed by an agent to execute an action for 3SADL stands for Sensory Action Description Language. a given purpose. For example, an agent opening a safe PUCCIN((I.A,O,L_,C,g_),,7_,s) finds one that works. 4 While this may seem silly, Pinoc- 1. If_ = 0AE = @AV_ 6 C _ not threatened, return ohio was following an identical strategy in his hunt for food. The Internet Softbot does the same when di- Success. 2. Pick one of rected to find a particular user, file or web page, whose location is unknown. If finger and ls (Figures 2 and (a) HandleGoal(v a. O, B, C, _, 7;)) 3) included knowledge preconditions, then the actions (b) HandleThreats(O, B, C, G) would be useless for locating users and files. For ex- (c) s := HandleExecution(A, C?,13,C, F, s) an@e, ls /papers only returns information about the 3. PUCCINI({.A, O, B, C, E>, _, 7), ._) file aips. rex if aips. rex is in /papers. Yet planning to move aips. rex into/papers misses the point if the Figure 1: The PUCCINI Algorithm takes as input a plan, goal is to find aips. rex! In a broad class of domains, which we call knowledge- a goal agenda (_), a domain theory (79), and the cur- rent state of the world, s, which is onl} partially known. ]ree Markov (KFM) domains, the effects of an action The plan consists of a set of actions (.4), ordering rela- depend only on the state of tile world (and not on the tions on A ((9), variable binding constraints (B), causal agent's knowledge about the world) at the time of ex- ecution. In such domains, actions are best encoded links (C) and unexecuted actions in A (g). The planner without knowledge preconditions. Simple mechanical repeatedly fixes "flaws" in the plan (open goals, threats and unexecuted actions) until the plan is complete. The and software systems are naturally encoded as KFM, while domains involving abstract actions are typically lines of the algorithm relevant to this paper are shown in bold. not. Such actions represent complex (albeit sketchy) plans in their own right, and depend on the agent's knowledge to be executed successfully. Although knowledge preconditions are problematic, needs to know tile combination. In (Golden & Weld it is often useful for an agent to plan to obtain informa- 1996), we argued that the practice of specifying knowl- tion, such as the combination of a safe, either to reduce edge preconditions for actions was too restrictive and search or to avoid dangerous mistakes. For example, if should be abandoned. there's an alarm on the safe, then it would be a bad idea Moore (Moore 1985) identified two kinds of knowl- to try all combinations. More importantly, it is neces- edge preconditions an agent must satisfy in order to ex- sary that the agent know, by the time it is finished, ecute an action in support of some proposition P: First, that it has achieved the goal. If we don't maintain this the agent nmst know a rigid designator (i.e., an unam- constraint, our planner is not even sound! biguous, executable description) of the action. Second, the agent must know that. executing the action will in Planning to Sense fact achieve P. Subsequent work by Morgenstern (Mor- The solution is to give the planner the information genstern 1987) generalized this framework to handle needed to determine when obtaining information, such scenarios where multiple agents reasoned about each as the combination of a safe, would be useful, and then other's knowledge. leave it to the planner to decide how and when to ac- The first type of knowledge precondition doesn't quire that information. We do so quite simply by the present any problem for us, since, in our language, all use of conditional effects (see Figures 2 and 3). Follow- actions are rigid designators, dial(combination(safe)) ing (Pednault 1986), we call the precondition of a condi- is not an admissible action, but dial(31-24-15) is. tional effect a secondary precondition (the precondition Lifted action schemas, e.g. dial (x), are not rigid des- of the action itself is known as a primary precondition). ignators, but it is easy to produce one by substituting If the agent wants to know whether a conditional ef- a constant for x. fect will occur, it needs to know whether the corre- Moore's second type of knowledge precondition pre- sponding secondary precondition is true. However, we supposes that an action in a plan must provably succeed don't require the planner to achieve the secondary pre- in achieving a desired goal. This is a standard assump- conditions before executing an action, even if it wants tion in classical planning, but is overly restrictive given the corresponding effects to occur. In this sense, the incomplete information about the world; elfforcing this secondary preconditions are descriptive, not prescrip- assumption by adding knowledge preconditions to ac- tive. The planner has the option of ensuring that these tions is inappropriate. For example, if knowledge of the secondary preconditions are true before it executes the safe's combination is a precondition of the dial action, action, but it can also verify them after the fact. We then it becomes impossible for a planner to solve the consider the former case in this section. We will discuss goal "find out whether the combination is 31-24-15" by the latter in the next section. dialing that number, since before executing the dial ac- The planner can ensure that a precondition is true t.ion, it will need to satisfy that action's precondition of by either observing it to be true or making it true. For finding out whether 31-24-15 is the.' right combination! example, suppose a softbot wants to compress the file Eliminating the knowledge precondition from the dial action also allows the unhurried agent to devise 4Richard Feynman estimated that he could open a safe a plan to enumerate the possible combinations until it. using this method in four hours (Feynman 1985). actionfinger(s) ing a user with the userid map, i.e., initially(userid(p, precond: satisfy (current.shell(c*3h)) map)), but it has no knowledge about any users, includ- effect: V !p 3 fl, !f, I._t ing whatever user, if any, has the userid of map. The when lastname(ip, .'0 V softbot could plan to execute finger map, but it's less firstname(!p, s) V obvious what to do with the secondary preconditions of userid(!p, s) observe (firstname(!p, !J)) A finger. Since the softbot doesn't know anything about observe (lastname(ip, !l)) A the user in question, it can't know that user's first name observe (userid(!p, !u)) or last name. It also doesn't know what user p satisfies the relation userid(p, map). While we could try simply asserting that there's a user whose userid is map, this Figure 2: Unix action schema. A simplified version of fact is not necessarily true, and asserting it into the the PUCCINIfinger action to find informant!on about a user. This action returns information about all users whose first softbot's knowledge base would introduce a number of name, last name or userid is equal to the input string s. complications, not the least of which is that the soft- Variables like !p,beginning with an exclamation point, are bot would erroneously believe that it already knew the called run-time variables. The values of these variables are answer to the query. determined at run time as a result of sensing. Effects labeled with observe designate propositions that are sensed by the Leap before you look agent, as opposed to being affected. Impasses like the one above are all too common. For- tunately, they have a simple solution. In the case of action ls(d) precond: satisfy (current.shell(csh)) finger map, above, the softbot can just execute the effect: V if when in.dir (if, d) finger; it will know afterward what user has that 3!p, .In userid, since the action has the effect observe (in.dir(/f, d)) A when userid(!p, s) ... observe (userid(!p, !u)). 5 observe (pathname(if, !p)) A observe (name(if, !n)) In short, the softbot will know after executing finger map whether the secondary precondition was true before Figure 3: Unix action schema. A simplified version of executing it. Since the softbot can verify after the fact the PUCCINIls action (Unix ls -a) to list all files in adirec- that the precondition was true, there's no reason not to tory. The relation in.dir(ff, d) means file ifisin directory !d, go ahead and execute the action. so this action returns information about all files in a given What we want is the ability to temporarily assume directory. the secondary precondition is true, and to later verify that the assumption was valid by performing an obser- vation. Formally, a comnfitment to verify an assnmp- aips. rex, and decides to do so by executing the action tic,n is a quadruple (Ap,p, e, A_), where p is a precondi- compress /papers/*, which compresses every file in tion of some effect of Ap. p is assumed to be true, and is the directory /papers. The action will only succeed if to be verified by effect e of action Ae. Note that, unlike sips. tex is actually in directory/papers. The softbot our discussion in the previous section, it isessential that could subgoal on ensuring that aips. rex is in/papers, the verification be done by an observation, since that either by observing that sips. tex is in/papers, using is the only way to obtain information about the past. the action ls (see Figure 3), or by moving aips.tex Executing an action that caused the precondition to be into/papers. VCeuse the term observational link to de- true would be useless, since the precondition needs to note links, Ale-_A2, in which tile effect e is an observe have been true before the action was executed. Because effect. the observation will only be valid if tile condition p re- Suppose a softbot wants to find the userid of Oren m_fins unperturbed, we must protect p over the interval Etzioni, a University of Washington professor. It can between Ap and A_. do so using the finger command (Figure 2). finger There is a striking similarity between these commit- takes a single argument, a string, and will only provide ments to verify preconditions and observational links. information about Oren if that string is Oren's first In fact, they are identical to observational links, with name, last name or userid. Since the softbot doesn't the exception that the order of the producer and con- know Oren's user!d, that will be useless to subgoal on, sumer is reversed! We call these commitments verifi- but the softbot does know Oren's first and last names. cation links, and write them as Ap_Ae. Because we Suppose it adopts the subgoal of knowing Oren's last want to consider supporting these preconditions by ei- name. This can be satisfied using the softbot's prior ther prior observation or later verification, we can ac- knowledge about the world. The softt)ot's prior knowl- complish this feat quite simply by omitting the order- edge is represented in the planner as the effects of a ing constraint that would normally be placed between dummy "initial step," A0. So the planner adds a link the producer and consumer. Since the only difference from A0 to finger, representing its commitment to use between an observation link and a verification link is its knowledge of the initial state to ,_atis_" its goal of knowing Oren's last name. 5This reasoifing depends on the fact that every user has Now suppose the softbot is given the goal of find- at most one user!d, but the planner has access to this fact. in tile ordering constraint, omitting the ordering con- straint means the planner hasn't c()mmitted to which kind of link it is. Eventually, the actions will be ordered, either in the course of planning or prior to execution. Once that happens, the link will be either an observa- tion link or a verification link, depending on the action order. Relaxing the ordering constraint allows for self- links as well, as in the case of f ±nger map, above. For (a) (b) example, consider the following effect of ls: V !fwhen in.dir(!f, d) observe (in.dir(!f, d)), Figure 5: Bookkeeping for verification links: (a) Ap may follow A_, but is used to verify a precondition of an effect where in.dir(!f, d) means that file !f is in directory !d. of .4_. This effect, in turn, satisfies a primary precondition We can satisfy the in.dir precondition by linking to the of A_ (solid lines indicate links). The effects of A, are un- effect of the same action (see Figure 4). If the desired defined unless the precondition is satisfied, and it won't be file is not in the directory, the observe effect ensures known whether A_ had the desired effect until Ap has been that the agent will know that fact after executing the executed, so an ordering constraint is added to ensure that action, 6 and the assumption will be proven false. A_ is not executed before Ap (dotted lines indicate ordering constraints). (b) The secondary precondition of Ap itself One potential concern about verification links is that is supported by an action, Ap,, that may be executed later. they increase the size of the search space by giving Since Ap, is indirectly providing support for A_, it must also the planner more ordering options. In fact, this is in- be executed before A_. evitable, since more plans are admissible when verifica- tion links are allowed. However, the number of plans that are solutions also increases, and, due to the least- This bookkeeping is really quite simple. If a link commitment approach, the alternative ordering options may never be explicitly explored. Thus, it is possi- Apq_A_ may represent a verification link, as opposed ble that using verification links would actually decrease to an observational link (i.e., Ac is not constrained to the number of plans explored, at lea,st in some cases. come after Ap) all actions A_ whose primary precondi- Whether more or fewer plans are explored is an empir- tions are supported by A_ are required to follow Av (see ical question, which we investigate in the next section. Figure 5(a)). If Apq_A_ turns out to be observation link, no harm was done in adding the constraint Ap -.<As. The constraint is redundant, since A_ nmst follow Ap, .._bserve(in.dir(aips,/papers)) by transitivity of the ordering relation (Ap -< Ac _ A_). Furthermore, if the effect e of Ap itself has a pre- condition supported by a (possibly later) action Ap,, salisfy(in.dir(aips, d)) the constraint A_, -_ A, will also be added (see Fig- ure 5(b)). In general, we require an action A8 to follow Figure 4: PUCCIN[ adds ls /papers in support of the goal all other actions that provide support to one of its pri- of finding the file nips.rex. Since this relics on the con- mary preconditions, where an action provides support ditional effect of ls, the desired outcome will only occur to a given precondition if it directly supports the pre- if in.dir(aips.tex, /papers) is true when is is executed. condition or if it provides support to the precondition of Rather than trying to achieve this pre(ondition, PUCCINI an effect that directly supports the given precondition. adds a verification link from the effect of is, observe These ordering constraints are added in the AddLink (in.dir(!f, /papers)), to this precondition. The agent will procedure (Figure 7). know after executing the Is whether the precondition was When it comes time to execute an action, all causal true. effects whose preconditions are unknown, including as- sumptions, must be asserted ms unknown in the agent's knowledge base. Additionally, all effects whose assumed Bookkeeping preconditions have been verified should be asserted as While we can handle assumptions elegantly by lifting true (this is valid, since the link guarantees that the the ordering constraints imposed along with observa- agent didn't change the condition in the interim}. tional links, that doesn't free us from bookkeeping. The effects supported by assumptions are, still contingent, Evaluation and we must exercise care in what we do with them. We While the examt)les we have given in this paper show should not store them in the agent's knowledge base or the benefits of a "leap before you look" approach, the execute actions with primary precomtitions supported real test is how well this approach actually works in by them until they have been verified. a real planning domain. In fact, the evolution of the PUCCINI planner was driven by representational prob- 6Actually, it is the fact that the agent observes all files lems we encountered in trying to encode Unix and that enables the agent to conclude that other files are not Internet action schemas for the Softbot, and trying in the directory. See (Etzioni, Golden, &: \Veld 1997) for a discussion of how this inference works. to get a planner to produce reasonable plans using HandleGoal(A, (._9,L_,C, c3,T)) 7.1.1 of (Golden 1997), but, briefly, they involve find- if _ _ 0 then pop (g, Sc) from from C_and select case: ing web pages, phone numbers and files (locally and via FTP) and compiling (I-STEX), displaying, printing, 1. If g = (Context =_ cond}, and Context_cond then g is compressing and changing permissions on files. For ex- trivially satisfied. 2. If g is a hands-off goal, then call AddLink(Ao, g, nil, an@e, goal #5 is "Display all web pages referenced by s ,o,s) hyperlinks from both Dan Weld's homepage and Oren Etzioni's homepage," which requires finding the appro- 3. Else nondeterministically choose priate home pages, scamiing both pages to find links in (a) Reduce(g, G) common, and then running Netscape on each common (b) Instantiate a new action A .... from :D, such link. that Satisfies(e, g) and add it to JL Call Table 1 shows the statistics for solving these goals, Addlink(Anew, g, e, So, O, B). Add precon- using each version of PUCCINI. The three versions are ditions of Ane. to _. as follows: (c) Choose an existing action Aota from Jr, such • VL is the version of PUCCINI presented here, which that Satisfies(e, g) and Call Addlink(Sp, g, e, supports verification links and allows the producer of Aold, O, 13). a verification link to follow the consumer. 4. Propagate context labels • NO does not allow the producer to follow the con- sumer, but still allows self-links (i.e., the producer is Figure 6: Procedure HandleGoal. Tile lines of the algo- the consumer). rithm relevant to this paper are shown in bold. • -,VL disallows all verification links. Addlink(Sp, goal, eft, Sc, O, _) The statistics shown include both planning CPU time (goal = (Context =>g); eff = when (p) e) and real time for planning and execution. The real time reflects the time required to actually execute the e,goal_ • Ifgisan initially goal, add Ao :-+ b. to C. Otherwise, commands and wait for completion, and thus represents add bpe,go_al_ bc to C. the time that the user is most likely to care about.. In • Unless g is an unannotated secondary precondition the experiments we report, the Softbot easily solved the and e is an observe effect goals, using very little domain-dependent search control and executing the minimal number of actions needed to 1. Add Sp -_ Sc to O achieve the goals. 2. If e is supported (directly or indirectly) by a po- More importantly, we find that, for the goals that tential verification link, whose producer is Ap, are solvable without verification links, the use of verifi- add Ap --_S_ to O caqon links has virtually no impact on the size of the • Add MGU(e, g) to B. search space. With the exception of goal 5 (for ver- • Add ((Context _ p}, Sp) to sion -,VL) the number of plans searched does not vary with the planner configuration. However, the nmnber of Figure 7: Procedure Addlink. The lines of the algorithm solvable goals decreases significantly when verification relevant to this paper are shown in bold. links are disabled. If verification links are entirely disabled (_VL), only two of the goals are solvable. The reason for this is that these schemas. Many of these struggles are discussed the SADL encodings of actions like ls and finger are in (Golden & Weld 1996; Etzioni, Golden, & Weld ahnost impossible to plan with if the planner doesn't 1997). One of the greatest representational gains came support self-links. Due to this limitation, the compari- from the elimination of knowledge preconditions and son between VL and _VL is not entirely fair. In order to the introduction of verification links. For example, more fairly judge the impact of verification links, we ran when knowledge preconditions were used to encode ac- the same problems on Xll, the predecessor of PUCCINI. tions, we needed no fewer than six encodings of the Since xII doesn't support verification links, the action finger action (Figure 2), and even these six were not encodings for that planner don't rely on them. Three enough to fully capture the functionality of the one of the goals, which rely on actions that were not part finger action we have now. Needless to say, this prolif- of the original xll domain theory, could not be solved eration of actions presented greater search control prob- by xII and were omitted from the test suite. lems, and the addition of more search control made the Table 2 shows the results for the seven remaining entire system more brittle. goals. Since the domain theories used by PUCCINI and Despite these gains, there are some potential pitfalls, xlt are different, these performance results should be which we should be on guard for. As we mentioned ear- taken with a grain of salt, but they are suggestive. Of lier, verification links can increase the size of the search these goals, 1and 2 are impossible to solve because the space by giving the planner more ordering options. To goals require the temporal expressiveness provided by determine whether this is a prol)lem in practice, we ran the initially annotation, which Xll does not support. three versions of PUCCINI on 10 representative Softbot Goal 9 is impossible to achieve without the use of veri- goals. These goals are described in detail in Section fication links, despite the fact that the XH domain was # [ plansIexecI CPU(s) real (s) net (Lesh 1992). Like PUCCINI, SOCRATES utilized the 1 I .I *1 Softbot domain as its testbed and interleaved planning with execution. However, SOCRATES utilized knowledge 3 30[ 1 I 0.57 1.12 preconditions and supported a less expressive action 4 [ 187] 8 I 11.99 43.92 language (Etzioni et al. 1992). 7[ 3619[ 11 I 539.59 602.83 We believe that our use of w_rifieation links is unique. 9 - i * , * * However, it should be possible for a Partially Observ- i0 I 792 6 65.92 87.06 able Markov Decision Process (POMDP) (Koenig 1992; I Dean et al. 1995), or the planner C-_UmDAN (Draper, Hanks, 8cWeld 1994), to produce plans similar to those Table 2: Planner statistics for seven out of ten sam- produced by PUCCINI using verification links. However, ple goals, given to the xn planner running on a Sun they accomplish this by following a generate-and-test SPARCstation 20 "*" indicates that the goal is impos- approach: considering the addition of each possible sen- sible for xn to achieve. Row and column labels are from sot and testing the plan by checking it against a proba- Table 1 bility distribution on all possible worlds. They can also decide not to support the precondition of a conditional effect, provided the probability of that effect occurring engineered to get around their absence. This goat is anyway is sufficiently high. Using this approach, they quite simple: Produce a color printout of a document can consider all plans that achieve the goal with a given and report the status of the print job. However, it cuts to the heart of a problem that stumped tile Softbot probability, but the computational cost is daunting. team since the very beginning: Print jobs are produced Some planners represent uncertain outcomes using conditional effects, and can execute actions for their by the lpr command, but lpr tells us nothing about them. To find out whether the print, job actually ex- uncertain effects (Kushmeriek, Hanks, & Weld 1995; ists and what identifier it has, we must execute lpq. Draper, Hanks, & Weld 1994; Pryor & Collins 1996; Goldman & Boddy 1994). For example, Cassan- Thus, the effect of lpr, the creation of a print job, is contingent on the job being sent to the print queue, a dra (Pryor & Collins 1996) represents uncertain out- comes as conditional effects with ":unknown" precondi- fact that can only be verified (by lpq) after the lpr has been executed. This does not present a problem if tions, and is capable of using these actions for their un- certain effects. Cassandra plans to achieve the goal for the planner supports verification links, but it creates a representational headache without them. all possible outcomes of each action, and adds sensing actions to determine which outcome actually occurred. Conclusions However, since Cassandra doesn't know what the ac- tual preconditions of these effects are, it cannot subgoal Past work in planning required agents to know, be- on finding out whether the preconditions were true, af- fore executing an action, that the action would have ter the fact. Furt.hermore, conditional effects without its intended effect. We have shown that this restric- :unknown preconditions are treated in the usual way; tion can be harmful, and we have shown that a simple the planner is forced to achieve the precondition if it. change to a causal link planner, relaxing an ordering wants the effect to occur. constraint, gives an agent the flexibility to subgoal on PUCCINI can represent effects that are explicitly un- obtaining this knowledge when doing so wouhl be fruit- certain, by using the U truth value (Golden & Weld ful, but also allows it to a_ssume preconditions are true and later verify them to be true. We have shown that 1996), but, unlike Cassandra or C-BURIDAN, it. can't execute these actions for their (uncertain) effects. This this mechanism can be implemented without impairing limitation stems from the fact that PUCCINI was not de- tractability. signed for contingency planning. In future extensions Related Work of PUCCINI, we would like to address this linfitation. PUCCINIis all extension of xIt (Golden, Etzioni, & Weld Future Work 1994), which is based on the ucpoP algorithm (Pen- berthy & Weld 1992). PUCCINi builds on xu by sup- Whenever the planner makes a decision to verify a pre- condition after the fact, that introduces an uncertain porting a more expressive language, SADL (Golden & Weld 1996), and handling verification links, xlI builds outcome upon which the success of the plan depends. We refer to this as a source of contingency in the plan. on ucPop by dealing with information goals and ef- fects, interleaving planning with execution and reason- There is always the possibility that the precondition is false, in which ease the action won't have the desired ing with Local Closed World knowledge (LCW) (Etzioni, Golden, & Weld 1997). The algorithm currently used effect. For example, if the agent is looking for the file for interleaving planning with execution builds on the aips.tex, and the planner adds is /papers into the approach used in IPEM (Ambros-Ingerson & Steel 1988). plan, there's a chance aips. rex will turn out not to be Unlike IPEM, PUCCINI Call represent information goals in /papers, in which case the plan will fail. In SADL, as distinct from satisfaction goals. IPEM makes no al/ sources of contingency stem from possibly unsatis- such distinction, and thus cannot plan for information fied preconditions (a precondition may be as simple as goals. PUCCINI also has its roots in the SOCRATES plan- an equality constraint). The approach currently taken prob plans considered actions executed planning CPU (s) real time (s) tram VL NO -A;L VL NO -_VL VL NO _VL VL NO -_VL 1 53 53 * 3 3 * 1.31 1.19 * 2.08 2.65 * 2 40 40 * 3 3 * 0.53 0.51 * 1.14 1.08 * 3 19 19 * 1 1 * 0.44 0.46 * 1.15 1.21 * 4 721 * * 6 * * 19.72 * * 61.85 * * 5 198 198 181 8 8 8 8.93 8.40 9.60 57.29 57.28 82.03 6 190 190 * 12 12 * 5.38 5.88 * 14.24 11.97 * 7 565 565 * 10 10 * 18.43 19.91 * 24.20 29.24 * 8 70 70 70 6 6 6 1.17 1.16 1.19 5.07 5.29 5.55 9 321 * * 4 * * 5.14 * * 8.57 * * 10 797 797 * 6 6 * 14.04 15.92 * 29.24 35.06 * Table 1: Planner statistics for ten sample goals, running on a Sun SPARCstation 20. Tile results are shown for the PUCCINI planner in three configurations: with verification links and flexible ordering (VL), without flexible ordering (NO) and without any verification links (-,VL). "*" indicates that the goal is impossible for the planner in question to achieve. to deal with contingency is to interleave planning and Golden, K.; Etzioni, O.; and Weld, D. 1994. Omnipotence execution. However, some of the techniques used in without omniscience: Sensor management in planning. In Proc. 12th Nat. Conf. AI, 1048 1054. PUCCINI, such as the use of context labels, are borrowed from contingency planning. We are in the process of in- Golden, K. 1997. Planning and Knowledge Representation tegrating these techniques more completely, to produce fl)r Softbots. Ph.D. Dissertation, University of Washington. Available as UW CSE Tech Report 97-11-05. a hybrid interleaved-contingency planner. C,oldman, R. P., and Boddy, M. S. 1994. Representing Acknowledgements Uncertainty in Simple Planners. In Proc. 4th Int. Conf. Principles of Knowledge Representation and Reasoning. This research was funded by Office of Naval Research I<oenig, S. 1992. Optimal probabilistic and decision- Grants N00014-94-1-0060 and N00014-98-1-0t47, by theoretic planning using Markovian decision theory. National Science Foundation Grant IRI-9303461, and UCB/CSD 92/685, Berkeley. by ARPA / Rome Labs grant F30602-95-1-0024. Kushmerick, N.; Hanks, S.; and Weld, D. 1995. An algo- Thanks to David Smith, Ellen Spertus, Richard Wash- rithm for probabilistic planning. J. Artificial Intelligence ington, Dan Weld and the anonymous reviewers for 75:239 -286. helpful comments. kesh, N. 1992. A planner for a UNIX softbot. Internal report. References McAllester, D., and Rosenblitt, D. 1991. Systematic non- Ambros-Ingerson, J., and Steel, S. 1988. Integrating plan- linear planning. In Proc. 9th Nat. Conf. AI, 634-639. ning, execution, and monitoring. In Proc. 7th Nat. Conf. Moore, R. 1985. A Formal Theory of Knowledge and AI, 735-74O. Action. In Hobbs, J., and Moore, R., eds., Formal Theories Dean, T.; Kaelbling, L. P.; Kirman, J.; and Nicholson, of the Commonsense World. At)lex. A. 1995. Planning under time constraints in stochastic Morgenstern, L. 1987. Knowledge preconditions for actions domains. J. Artificial Intelligence 76. and plans. In Proceedings of IJCAI-SZ 867-874. Draper, D.; Hanks, S.; and Weht, D. 1994. Probabilistic Pednanlt, E. 1986. Toward a Mathematical Theory of Plan planning with information gathering and contingent exe- Synthesis. Ph.D. Dissertation, Stanford University. cution. In Proc. 2nd Intl. Conf. AI Planning Systems. F'ent)erthy, J., and 'Weld, D. 1992. UCPOP: A sound, Etzioni, O., and Weld, D. 1994. A softbot-based interface complete, partial order planner for ADL. In Proc. 3rd Int. to the Internet. C. ACM 37(7):72 6. Conf. Principles of Knowledge Representation and Reason- Etzioni, O.; Hanks, S.; Weld, D.; Draper, D.; Lesh, N.; i:'_g, 103 114. See also http://uuw.cs.uashington.edu/ and Williamson, M. 1992. An approach to planning with reseat ch/pro ject s/ai/uww/ucpop •htral. incomplete information. In Proc. 3rd Int. Conf. on Princi- l='enberthy, J. 1993. Planning with Continuous Change. ples of Knowledge Representation and Reasoning, 115-125. Ph.D. Dissertation, University of Washington. Available Etzioni, 04 Golden, K.; and Weld, D. 1997. Sound and as UW CSE Tech Report 93-12-01. efficient closed-world reasoning for planning. J. Artificial Pryor, L., and Collins, G. 1996. Planning for contingen- Intelligence 89(1-2):113 148. cies: A decision-based approach. J. Artificial Intelligence Feynman, R. P. 1985. Surely You're JoAing, Mr. Feynman. Research. New York: Bantam Books. Tate, A. 1977. Generating project networks. In Proc. 5th Golden, K., and Weld, D. 1996. Representing sensing Int. Joint Conf. AI, 888-893. actions: The middle ground revisited. In Proc. 5th Int. Weld, D., and Etzioni, O. 1994. The first law of robotics Conf. Principles of Knowledge Representation and Reason- (a call to arms). In Proc. 12th Nat. Conf. AL 1042-1047. ing, 174-185.

See more

The list of books you might like

Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.