DOC PREVIEW
A Spectrum of Plan Justi cations

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

A Spectrum of Plan JustificationsEugene Fink∗School of Computer ScienceCarnegie Mellon UniversityPittsbugrh, PA [email protected] Yang∗Department of Computer ScienceUniversity of WaterlooWaterloo, Ont., Canada [email protected] paper formalizes the notion of justified plans,which captures the intuition behind “good” plans. Aplan is called justified if it does not contain operatorsthat are not necessary for achieving a goal. We ex-plore several different types of justification, presentalgorithms for removing “useless” operators from aplan, and show that the task to remove all uselessoperators is NP-complete.1 IntroductionWhen we search for a plan to achieve certain goals,we wish to find a plan that does not contain “use-less” steps. In other words, we wish to optimize theplan by removing all operators that are not neces-sary for achieving the goals. For example, supposethat we prepare tea by following the plan: “put atea bag into a cup; boil water in a kettle; pour waterinto the cup”. If later we discover that the waterin the kettle is already hot, then the second step ofthe plan, “boil water”, is no longer necessary. Afterremoving the second step, the resulting plan, “put atea bag into a cup; pour water into the cup”, con-tains fewer steps while still achieving the same goal.The operation of removing useless operators from aplan is known as justification. The purpose of ourpaper is to formalize different ways of performingjustification.The justification algorithms described in this pa-per may be used to augment a non-optimal plannersuch as STRIPS [Nilsson, 1980]. Such an augmen-tation is especially useful for planning with macrooperators [Korf, 1985]. Another application of jus-tification algorithms is in reusing old plans. Sup-∗The first author is supported by Carnegie Mellon Uni-versity. The second author is supported in part by grantsfrom the Natural Sciences and Engineering Research Councilof Canada and ITRC.pose that we have found a plan for achieving goalsG1and G2. Later we may use the same plan toachieve the goal G1alone. In this case we wish tofind the subset of the initial plan which is “relevant”to achieving G1, by removing all unnecessary oper-ators. Planning systems that reuse old plans [Ha-mmond, 1986], [Kambhampati and Hendler, 1992],[Hanks and Weld, 1992] can benefit from justifica-tion algorithms.Different definitions of justification were presentedin [Tenenberg and Yang, 1990], [Knoblock et al.,1991], and [Bacchus and Yang, 1991], where thisnotion was used for formalizing several importantproperties of abstraction hierarchies. A further for-malization of justification was presented in [Kam-bhampati, 1992]. However, these papers did notpresent an algorithm for removing non-justified op-erators from a plan.In this paper we extend and unify the previouswork and describe two algorithms for finding justi-fied versions of nonlinear plans. First we considerthe notion of backward justified plans, which guar-antees that each operator in the plan establishes aliteral necessary for achieving the goal. Then wepresent well-justified plans. Informally, a plan iswell-justified if no single operator may be removedfrom the plan. We compare well-justified and back-ward justified plans. Finally, we consider the taskto find the “best possible” justification of a givenplan, that is, a subplan of a given plan that can-not be further optimized by removing any subset ofits operators. The task of finding such a subplan isNP-complete. To satisfy the practical need for effi-cient planning, we present a greedy algorithm thatfinds a near-perfect justification in polynomial time.Proofs of the italicized statements may be found in[Fink, 1992].12 Backward justificationTo formalize the notion of justified plans, we firstgeneralize the concept of establishment defined in[Knoblock et al., 1991] to nonlinear plans.Let α1and α2be two operators of a correct linearplan, such that α1precedes α2,andl be a precondi-tion of α2.Wesaythatα1establishes l for α2if l isan effect of α1and no operator between α1and α2either asserts or removes l.Wesaythatα1possiblyestablishes a literal l for α2in a nonlinear plan Π if itestablishes l for α2in at least one linearized versionof Π.Intuitively this means that the precondition l ofthe operator α2is satisfied, and α1is the last oper-ator that achieves it.Definition 1 Let Π be a correct plan. An operatorα of Π is called backward justified if α possibly es-tablishes some literal l either for the goal of the planor for another backward justified operator.We say that a plan Π is backward justified if all itsoperators are backward justified. This definition ofjustification was used for linear plans in [Knoblocket al., 1991]. It is slightly weaker than the justifi-cation used in the ABTWEAK planner [Tenenbergand Yang, 1990]. Intuitively, an operator is back-ward justified if it establishes some literal necessaryfor achieving the goal. We call this justification back-ward because it has been mostly used in formalizingbackward-chaining planners.However, backward justified operators are not“truly justified”. For example, if a literal is achievedtwice in a linear plan, then, by definition, the secondoperator achieving this literal is backward justified.But in this case the second operator is useless. Forexample, if the same discovery is made by two inde-pendent researches, the second one usually does notget a credit. As another example, suppose that youhave a kettle with hot water and an empty cup, andyou wish to have a cup of hot water. The followingplan achieves the goal.1. Pour water into the cup.2. Put the cup into a microwave.The second operator is backward-justified, becauseit makes the water hot, while no other operator af-ter it achieves the same goal of making the waterhot in the final state. However, this operator stillmay be skipped, because the water was already hotbefore its execution. Thus, the second operator isnot “truly justified”.The advantage of the backward justification isthat it can be computed with a small running time.BackwardJustification(Π)1. letΠ be some linearized version of Π;2. for α := (end ofΠ) downto (beginning of Π) dobegin3. Justified := False ;4. for each l ∈ Eff (α) do5. if (α establishes l for some α1or for the goal)6. then /∗ α is justified ∗/ Justified := True ;7. if Justified=False /∗ α is not justified ∗/8. then


A Spectrum of Plan Justi cations

Download A Spectrum of Plan Justi cations
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A Spectrum of Plan Justi cations and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Spectrum of Plan Justi cations 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?