Refinement Planning: Status and Prospectus

2/7: Knowledge-based Planning 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Life must be lived forward, but can only be understood backward.--Kierkegaard Lp tion a x rela 2 Should we bother with Proof-based encodings? Clearly Graphplan-based encodings are better than backward-proof based encodings Because Graphplan does Mutex propagation And mutex propagation is harder to do on direct SAT And yet, it is useful to know how to set up encodings directlysince if we dont know how to do directed consistency enforcement, then we at least know how to solve the problem Particularly useful for non-classical problems, where we havent yet found really effective mutex propagation procedures. If neural networks are often the second best way of solving

any problem, you can say that direct SAT(or other) encodings are the second best way of solving planning problems Which is better than no way at all 3 Connections to Refinement Planning Framework Disjunctive Planning Idea: Consider Partial plans with disjunctive step, ordering, and auxiliary constraints Motivation: Provides a lifted search space, avoids re-generating the same failures multiple times (also, rich connections to combinatorial problems) The solution check now involves searching through the space of all (exponentially many) minimal candidates of the plan to see if any of them is a solution Issues: Refining disjunctive plans Graphplan (Blum & Furst, 95) Solution extraction in disjunctive plans Direct combinatorial search Compilation to CSP/SAT/ILP 5 Disjunctive Representations --Allow disjunctive step, ordering and auxiliary constraints in partial plans 0

1: Load(A) 0 1: Load(B) 0 1: Fly(R) 0 1: Load(A) In(A) In(B) 1: Load(B) < 1,In(A), > V < 1 ,In(B), >

In(x)@ 0 0 1: Load(A) or 2 : Load(B) or 3 : Fly(R) In(x)@ 0 Load(A) 1: or Load(B) At(A,E)@1 V At(B,E)@1 6 Refining Disjunctive Plans (1)

0 1: Load(A) or 2 : Load(B) or 3 : Fly(R) 1: Load(A) or 2 : Load(B) or 3 : Fly(R) or 1: Load(A) 0 or 2 : Load(B) or 3 : Fly(R) Indirect unioned approach 4 : Unload(A,E)

or 5 : Unload(B,E) + Maximum pruning power - Exponential refinement cost INFEASIBLE 0 1: Load(A) 0 1: Load(B) 0 1: Fly(R) 0 1: Load(A) 2: Fly(R)

0 1: Load(B) 2: Fly(R) 0 1: Load(A) 2: Unload(A,E) 0 1: Load(B) 2: Unload(B,E) 0 1: Load(A) 2: Load(B)

0 1: Load(B) 2: Load(A) 0 1: Fly(R) 7 Refining Disjunctive plans (2) Direct naive approach Put all actions at all levels --Proposition list contains all conditions In(A) union of states In(B) + Trivial to construct - Loss of pruning power (progressivity)

At(R,M) => too many (minimal) candidates => Costlier solution extraction At(R,E) At(A,E) At(B,E) SA TP in D US E 0 1: Load(A) or 2 : Load(B) or 3 : Fly(R) LA N

At(A,M) At(B,M) 0 1: Load(A) or 2 : Load(B) or 3 : Fly(R) 1: Load(A,E) or 2 : Load(B,E) or 3 : Fly(R) or 4 : Unload(A,E) or 5 : Unload(B,E) 6 : Unload(A,M) 7 : Unload(B,M) 8 : load(A,M) 9 : load(B,M) 8 Refining Disjunctive plans (2)

Direct naive approach Put all actions at all levels --Proposition list contains all conditions In(A) union of states In(B) + Trivial to construct - Loss of pruning power (progressivity) At(R,M) => too many (minimal) candidates => Costlier solution extraction At(R,E) At(A,E) At(B,E) SA TP in D US E

0 1: Load(A) or 2 : Load(B) or 3 : Fly(R) LA N At(A,M) At(B,M) 0 1: Load(A) or 2 : Load(B) or 3 : Fly(R) 1: Load(A) or 2 : Load(B) or 3 : Fly(R) or 4 : Unload(A,E) or

5 : Unload(B,E) or 6 : Unload(A,M) or 7 : Unload(B,M) 9 Refining Disjunctive plans (3) Enforce partial 1-consistency Proposition list avoids unsupported conditions In(A) + Polynomial refinement time -- Loss of pruning power (progressivity) In(B) At(R,M) At(R,E) At(A,E) At(B,E) At(A,M) At(B,M) 0 1: Load(A)

or 2 : Load(B) or 3 : Fly(R) 0 1: Load(A) or 2 : Load(B) or 3 : Fly(R) 1: Load(A,E) or 2 : Load(B,E) or 3 : Fly(R) or 4 : Unload(A,E) or 5 : Unload(B,E) 6 : Unload(A,M) 7 : Unload(B,M) 8 : load(A,M) 9 : load(B,M)

10 Refining Disjunctive plans (4) Enforce (partial) 2-consistency Proposition list maintains interactions between pairs of conditions + Polynomial refinement time In(A) higher pruning power + Better balance between refinement cost In(B) and solution extraction cost At(R,M) At(R,E) At(A,E) At(B,E) 0 1: Load(A) or 2 : Load(B) or 3 : Fly(R) 0 1: Load(A)

or 2 : Load(B) or 3 : Fly(R) t , bu y c n iste s n o st o el c c v e e l h th her t g r i o h do

ely w r a Can r it is 1: Load(A,E) or 2 : Load(B,E) or 3 : Fly(R) or 4 : Unload(A,E) or 5 : Unload(B,E) 6 : Unload(A,M) 7 : Unload(B,M) 8 : load(A,M) 9 : load(B,M) 11 Re vi ew Digression: Domain-Independent vs.

Domain Specific vs. Domain Customized Domain independent planners only expect as input the description of the actions (in terms of their preconditions and effects), and the description of the goals to be achieved Domain dependent planners make use of additional knowledge beyond action and goal specification Domain dependent planners may either be stand alone programs written specifically for that domain OR domain independent planners customized to a specific domain In the case of domain-customized planners, the additional knowledge they exploit can come in many varieties (declarative control rules or procedural directives on which search choices to try and in what order) The additional knowledge can either be input manually or in some cases, be learned automatically Unless noted otherwise, we will be talking ab domain-independent planning 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Improving Performance through Customization

Biasing the search with control knowledge acquired from experts Non-primitive actions and reduction schemas Automated synthesis of customized planners Combine formal theory of refinement planning and domain-specific control knowledge Use of learning techniques Search control rule learning Plan reuse 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa User-Assisted Customization (using domain-specific Knowledge) Domain independent planners tend to miss the regularities in the domain Domain specific planners have to be built from scratch for every domain An Any-Expertise Solution: Try adding domain specific control knowledge to the domain-independent planners E se o

CM r p e r A u n l p lan l a p Domain Specific Knowledge 2: Recent Advances in AI Planning: A Unified View e O bl R a C- iz er A m n to an s l Cu p ld r o wo c n ks o R oc e r Bl ann Pl

co ics n t Ro gis er lo ann Pl co op n Ro bsh er jo ann Pl Subbarao Kambhampa Task Decomposition (HTN) Planning The OLDEST approach for providing domain-specific knowledge Most of the fielded applications use HTN planning Domain model contains non-primitive actions, and schemas for reducing them Reduction schemas are given by the designer Can be seen as encoding user-intent

Popularity of HTN approaches a testament of ease with which these schemas are available? Two notions of completeness: Schema completeness (Partial Hierarchicalization) Planner completeness 2: Recent Advances in AI Planning: A Unified View Travel(S,D) GobyTrain(S,D) GobyBus(S,D) BuyTickt(T) Getin(B,S) Getin(T,S) BuyTickt(B) Getout(T,D) Getout(B,D) Hitchhike(S,D) Subbarao Kambhampa

Modeling Reduction Schemas GobyBus(S,D) t1: Getin(B,S) In(B) Hv-Tkt t2: BuyTickt(B) t3: Getout(B,D) Hv-Money 2: Recent Advances in AI Planning: A Unified View At(D) Subbarao Kambhampa Stuff to add.. Domain knowledge as prescriptive vs. suggestive Recipes as HTN schemas whose correctness is not known The fact that soundness of HTN schemas can be checked but not completeness even with full domain model at the prec/effect level

2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa A concretization is a task network produced by repeate reducing a non-primitive task until all tasks are prim 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Modeling Action Reduction GobyBus(S,D) t1: Getin(B,S) In(B) Hv-Tkt

t2: BuyTickt(B) t3: Getout(B,D) At(D) At(Msn) Get(Money) GobyBus(Phx,Msn) Buy(WiscCheese) Hv-Money t1: Getin(B,Phx) 2: Recent Advances in AI Planning: A Unified View In(B) Hv-Tkt t2: BuyTickt(B) Get(Money) Af fin ity be tw pl een

an -s red pa u ce cti pl on an sc ni he ng m as an d Hv-Money Hv-Money t3: Getout(B,Msn) At(D) Buy(WiscCheese) Subbarao Kambhampa Dual views of HTN planning Capturing hierarchical structure of the domain

Motivates top-down planning Start with abstract plans, and reduce them Motivates bottom-up planning Ensure that each partial plan being considered is legal with respect to the reduction schemas Directly usable with disjunctive planning approaches Many technical headaches Respecting user-intent, maintaining systematicity and minimality [Kambhampati et. al. AAAI-98] Phantomization, filters, promiscuity, downwardunlinearizability.. Capturing expert advice about desirable solutions Connection to efficiency is not obvious

Relative advantages are still unclear... 2: Recent Advances in AI Planning: A Unified View [Barrett, 97] Subbarao Kambhampa 2: Recent Advances in AI Planning: A Unified View 2/12 Subbarao Kambhampa 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Changes to Plan-Space Refinement (in the presence of non-primitive tasks) 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa HTN vs. T-STN

Naus book talks about a special version of HTN called T-STN (Totalordering STN) T-STN schemas are HTN schemas where all the ordering relations between tasks are constrained to be contiguity constraints This means that the concretizations of different tasks cannot be interleaved Bug or feature? From the planners point of view, it can be a feature Most of the difficulties in HTN planning come from the need to do plan-space refinement in the presence of non-primitive tasks (phantomization, conflict resolution etc..); eliminating that will make HTN planning a nobrainer BUT from the domain-writers point of view it is clearly a BUG Would have to write many more schemas Same is true of Yangs unique main sub-action thing (although it is less drastic than T-STN) (few recipes are given with contiguity orderingswhich means that you cant do anything else while following the recipe) The only HTN planners that use STN schemas are those from Naus group SIPE and O-Plan use schemas with precedence orderings 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa

2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa HTN vs. STRIPS planning: Competing or Complementary? Much of the discussion till now has been done with the assumption that HTN is just a way of doing STRIPS planning 2: Recent Advances in AI Planning: A Unified View HTN can also be seen as solving a different problem Can develop plans at various levels of abstraction Can model domains with partial domain knowledge What you consider primitive action may be changeable

What you thought was a correct plan may not be.. Subbarao Kambhampa 2: Recent Advances in AI Planning: A Unified View 9/6 Subbarao Kambhampa [Nau et. al., 99] Full procedural control: The SHOP way Shop provides a high-level programming language in which the user can code his/her domain specific planner -- Similarities to HTN planning Uses T-STN schemas -- Order of use of reduction schemas can be specified The SHOP engine can be Travel by bus only if going by seen as an interpreter taxi doesnt work out for this language Cant do any other actions

Blurs the domain-specific/domain-independent between !hail and !ride divide How often does one have this level of knowledge about a domain? 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa [Kautz & Selman, AIPS- Non-HTN Declarative Guidance Invariants: A truck is at only one location at(truck, loc1, I) & loc1 != loc2 => ~at(truck, loc2, I) Optimality: Do not return a package to a location at(pkg, loc, I) & ~at(pkg,loc,I+1) & I ~at(pkg,loc,j) Simplifying: Once a truck is loaded, it should immediately move ~in(pkg,truck,I) & in(pkg,truck,I+1) & at(truck, loc, I+1) => ~at(truck, loc, I+2) Once again, additional clauses first increase the encoding size but make them easier to solve after simplification (unit-propagation etc). 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Case Study: SATPLAN with domain specific knowledge

Instantiate the domain specific rules as well, and then add them to the encoding. Solve the full encoding Wont the encoding size increase with domain spefic rules? Yes, but the new rules support a lot of simplification so that after simplification, the encoding size actually reduces!! Example in Blocks world (from Kautz & Selman, AIPS-99) BW-c: Original: 4258 vars (10% increase) / 30986 clauses (300% increase) 2: Recent Advances in AI Planning: A Unified View Final (after simplification): 3526 vars 22535 clauses Subbarao Kambhampa [Mali & Kambampati, AIPS-98] SAT encodings of HTN planning Abstract actions can be seen as disjunctive constraints Constraints from action-based

encodings 2: Recent Advances in AI Planning: A Unified View HTN-compliant Solutions HTN constraints Solutions for action based encodings K-step encoding has each of the steps mapped to a disjunction of the non-primitive tasks If a step s is mapped to a task N, then one of the reductions of N must hold (**The heart of encoding setup**) + The normal constraints of primitive action-based encoding Causal encodings seem to be a natural fit (given the causal dependencies encoded in reduction schemas) Subbarao Kambhampa Solving HTN Encodings Puzzle: How can increasing encoding sizes lead to efficient planning? Abstract actions and their reductions put restrictions on the amount of step-action disjunction at the primitive level. --Reduction in step-action disjunction propagates e.g. Fewer causal-link variables, Fewer exclusion clauses Savings wont hold if each non-primitive task has MANY reductions 2: Recent Advances in AI Planning: A Unified View

TIME # Clauses [Kambhampati & Mali, AIPS-98] Subbarao Kambhampa Rules on desirable State Sequences: TLPlan approach TLPlan [Bacchus & Kabanza, 95/98] controls a forward state-space planner Rules are written on state sequences using the linear temporal logic (LTL) LTL is an extension of prop logic with temporal modalities U until [] always O next <> eventually Example: If you achieve on(B,A), then preserve it until On(C,B) is achieved: [] ( on(B,A) => on(B,A) U on(C,B) ) 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa TLPLAN Rules can get quite boroque Good towers are those that do not violate any goal conditions Keep growing good towers, and avoid bad towers

s u vio les? b O e ru w es o H th e r a The heart of TLPlan is the ability to incrementally and effectively evaluate the truth of LTL formulas. 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Control rules for choice points UCPOP developed a language in which user can write control rules that tell the planner what to do when it faces a specific sort of choice (e.g. between open conditions; establishers for open conditions etc.).

HSTSa metric temporal planner that NASA used in its DeepSpace mission used similar control rule language. The user needs to know the innards of the planner to write these rules The rules are hard to debug Learning such rules automatically is a way out 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Srivastava & Kambhampati, JA Folding the Control Knowledge into the planner: CLAY approach Control knowledge similar to TLPlans Knowledge is folded using KIDS semi-automated software synthesis tool into a generic refinement planning template Use of program optimizations such as Finite differencing Context-dependent & independent simplification

Empirical results demonstrate that ware t f o s folding can be better than ated m o t t au n e interpreting rules r r ools u t rve C s u i : t c s a

e g e h rnin Cav synt a e l p y stee r e v a ha v e 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Many User-Customizable Planners Conjunctive planners HTN planners SIPE [Wilkins, 85-] NONLIN/O-Plan [Tate et. al., 77-] NOAH [Sacerdoti, 75] Also SHOP (Nau et. al., IJCAI-99) State-space planners

TLPlan [Bacchus & Kabanza, 95; 99] TALPlan [Kvarnstrom & Doherty, 2000] Customization frameworks CLAY [Srivastava & Kambhampati, 97] Disjunctive planners HTN SAT [Mali & Kambhampati, 98] SATPLAN+Dom [Kautz & Selman, 98] 2: Recent Advances in AI Planning: A Unified View ? ? s e ff t a eo l re rad y t e th the do re a o w at H h W Subbarao Kambhampa

With right domain knowledge any level of performance can be achieved... HTN-SAT, SATPLAN+DOM beat SATPLAN Expect reduction schemas, declarative knowledge about inoptimal plans TLPLAN beats SATPLAN, GRAPHPLAN But uses quite detailed domain knowledge SHOP beats TLPLAN(but not TALPlan) Expects user to write a program for the domain in its language Explicit instructions on the order in which schemas are considered and concatenated 2: Recent Advances in AI Planning: A Unified View o g he ets pr the e pl ovid cre an

ne er o dit? rt fd ha om ti s c ai n a p kn ab o w le le of d g us e? in g Subbarao Kambhampa Types of Guidance Declarative knowledge about desirable or undesirable solutions and partial solutions (SATPLAN+DOM; Cutting Planes) Declarative knowledge about desirable/undesirable search paths (TLPlan & TALPlan) A declarative grammar of desirable solutions (HTN)

independent of the details of the specific planner do exist between specific types of guidance and planners) Planner specific. Expert needs to understan specific details of the planners search spac Procedural knowledge about how the search for the solution should be organized (SHOP) Search control rules for guiding choice points in the planners search (NASA RAX) 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Ways of using the Domain Knowledge As search control HTN schemas, TLPlan rules, SHOP procedures Issues of Efficient Matching

To prune unpromising partial solutions HTN schemas, TLPlan rules, SHOP procedures Issues of maintaining multiple parses As declartative axioms that are used along with other knowledge SATPlan+Domain specific knowledge Cutting Planes (for ILP encodings) Issues of domain-knowledge driven simplification Folded into the domain-independent algorithm to generate a new domaincustomized planner CLAY Issues of Program synthesis 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Conundrums of user-assisted cutomization Which planners are easier to control? Conjunctive planners are better if you have search control knowledge Forward State Space (according to TLPlan) Plan-space planners (according to HTN approaches) Disjunctive planners are better if your knowledge can be posed as additional constraints on the valid plans Which SAT encoding? HTN knowledge is easier to add on top of causal encodings Which approach provides the best language for expressing domain knowledge for the lay user?

(Mine--no, no, Mine!) What type of domain knowledge is easier to validate? When does it become cheating/ wishful-thinking Foolish not to be able to use available knowledge Wishful to expect deep procedural knowledge... 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Evaluating KB-planners Since the 2nd IPC, there has been a separate track for knowledge-based planners at the competition. Basically only the TLPlan (and its variant TALPlan) and SHOP took part (in comparison close to a dozen planners take part in the domain-independent track) In 2000, TALPlan won In 2002, TLPlan won Quite controversial When SHOP does better than TLplan on Gizmo domain, what does this mean? That SHOP is a better planning algorithm than TLplan?

That Dana Nau knows Gizmo domain better than Faheim Bacchus? That the easily available control knowledge in Gizmo domain is more naturally representable as TLplan rules than SHOP schemas? 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Are we comparing Dana & Fahiem or SHOP and TLPlan? (A Critique of Knowledge-based Planning Track at ICP) Click here to download TLPlan Click here to download a Fahiem Click here to download SHOP Click here to download a Dana Subbarao Kambhampati Dept. of Computer Science & Engg. Arizona State University Tempe AZ 85287-5406

2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa The I am not an anti-dentite Disclaimers.. I think KB planning is a swell idea I started my career with HTN planning I think the KB planning track at IPC is a swell idea has done more to increase interest in KBplanning than the bi-annual polemics and laments about lack of interest in Knowledge-based planning I think Fahiem and Dana are REALLY swell (in case they dont buy that) I may already have a black-belt in Karate.. Id rather learn from one bird how to sing than teach ten thousand stars how not to dance --e.e. cummings

2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa What are the lessons of KB Track? If TLPlan did better than SHOP in ICP, then how are we supposed to interpret it? That TLPlan is a superior planning technology over SHOP? That the naturally available domain knowledge in the competition domains is easier to encode as linear temporal logic statements on state sequences than as procedures in the SHOP language? That Fahiem Bacchus and Jonas Kvarnstrom are way better at coming up with domain knowledge for blocks world (and other competition domains) than Dana Nau? are NOT asking the right questi 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Questions worth asking in KB planner comparisons (IMHO)

How easy/natural (for humans) is the language in which the planner accepts control knowledge? How easy is it to validate the control knowledge being input to the planner? Is the naturally available knowledge about a specific domain easily encoded in the language accepted by the planner? Does the planner allow any expertise behavior solving the problems even without any control knowledge, but improving performance with added control knowledge? (or is the control knowledge tightly intertwined with the domain physics?). 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa How/Why the competition is not asking the right questions The role of the knowledge-engineer is played by the same person(s) who wrote the planner. So, the question of how natural the specific language is for third-party knowledge engineers is largely unaddressed. No reasonable time limits are placed on coming up with the control knowledge. So, we dont learn much

(or anything) about whether or not naturally available knowledge about a domain is easily representable in the language accepted by the planner. 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Some suggestions for change Recruit third-party volunteers who will play the role of knowledge engineers for the KB planners. Ideally, we would like to have the same people writing the control knowledge for a given domain for all the competing approaches (so one knowledge engineer per domain rather than one knowledge engineer per planner). (Alternative to above) Specify the control knowledge that is available, so all planners encode the same general knowledge. One idea might be to ask the designers of the domains (e.g. David Smith and his cohorts for the Satellite and Rovers domain) to provide, in english, what sort of control information they would like the planner to use. Measure the time taken to write and validate the control knowledge.

Analyze the knowledge encoded by the different KB planners for the same domain Characterize it in terms of (a) whether the knowledge is procedural or declarative and (b) how hard would it be to learn the same knowledge. 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Slides from here-on about learning domain knowledge were not used 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Domain pre-processing M co o s nt t o ex f t the of C wo on r ju k h n c as ti b

ve e e R n efi d ne on m ei en n t the P la nn Automated Customization of Planners Invariant detection; Relevance detection; Choice elimination, Type analysis STAN/TIM, DISCOPLAN etc. RIFO; ONLP Abstraction ALPINE; ABSTRIPS, STAN/TIM etc. Learning Search Control rules UCPOP+EBL, PRODIGY+EBL, (Graphplan+EBL)

Case-based planning (plan reuse) DerSNLP, Prodigy/Analogy ry Zimmermans arning assisted planning: Looking back, Taking Stock and Going Forwar 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Symmetry & Invariant Detection Generate potential invariants and test them DISCOPLAN [Gerevini et. al.] Allows detection of higher-order mutexes Rintanens planner Uses model-verification techniques STAN/TIM Type analysis of the domain is used to generate invariants ONLP (Peot & Smith) Use operator graph analysis to eliminate non-viable choices 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Abstraction

Idea Abstract some details of the problem or actions. Solve the abstracted version. Extend the solution to the detailed version Precondition Abstraction Work on satisfying important preconditions first Importance judged by: Length of plans for subgoals [ABSTRIPS, PABLO] Inter-goal relations [ALPINE] Distribution-based [HighPoint] Strong abstractions (with downward refinement property) are rare Effectiveness is planner-dependent Clashes with other heuristics such as most constrained first 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Example: Abstracting Resources Most planners thrash by addressing planning and scheduling considerations together Eg. Blocks world, with

multiple robot hands Idea: Abstract resources away during planning Plan assuming infinite resources Do a post-planning resource allocation phase Re-plan if needed (with Biplav Srivastava) 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa Learning Search Control Rules with EBL Explain leaf level failures Regress the explanations to compute interior node failure explanations Use failure explanations to set up control rules Problems: -- Most branches end in depth-limits >No analytical explanation >Use preference rules? -- THE Utility problem

>Learn general rules >Keep usage statistics & prune useless rules Kambhampati, Katukam, Qu, 95) 2: Recent Advances in AI Planning: A Unified View UCPOP+EBL If Polished(x)@S & ~Initially-True(Polished(x)) Then REJECT Stepadd(Roll(x),Cylindrical(x)@s) Subbarao Kambhampa Case-based Planning Macrops, Reuse, Replay Structures being reused Opaque vs. Modifiable Solution vs. Solving process (derivation) Acquisition of structures to be reused Human given vs. Automatically acquired

Mechanics of reuse Phased vs. simultaneous Costs Storage & Retrieval costs; Solution quality 2: Recent Advances in AI Planning: A Unified View Subbarao Kambhampa ( Ihrig & Kambhampati, JAIR 97) Case-study: DerSNLP Modifiable derivational traces are reused Traces are automatically acquired during problem solving Analyze the interactions among the parts of a plan, and store plans for non-interacting subgoals separately Reduces retrieval cost Use of EBL failure analysis to detect interactions All relevant trace fragments are retrieved and replayed before the control is given to from-scratch planner

Extension failures are traced to individual replayed traces, and their storage indices are modified appropriately Improves retrieval accuracy 2: Recent Advances in AI Planning: A Unified View Old cases Subbarao Kambhampa DerSNLP: Results 0 0 5 6 2: Recent Advances in AI Planning: A Unified View 600 500 400 300 200 100 0 5

3 1 0 Librar y Size Library Size Problem size (#goals) 120 4 60 3 40 2 20 1 120 40 60

120 5000 100 10000 80 20 15000 % Solvability with increased traning 60 20000 40 25000 100 90 80 70 60 50

40 30 20 10 0 100 30000 80 35000 % Solved Performance with increased Training 40000 Cumulative CPU Time 0 20 45000 (JAIR, 97)

Subbarao Kambhampa Reuse in Disjunctive Planning Harder to make a disjunctive planner commit to extending a specific plan first Options: Support opaque macros along with primitive actions Increases the size of k-step disjunctive plan But a solution may be found at smaller k Modify the problem/domain specification so the old plans constraints will be respected in any solution (Bailotti et. al.) MAX-SAT formulations of reuse problem Constrain the encoding so that certain steps may have smaller step-action mapping and ordering choices Causal encodings provide better support 2: Recent Advances in AI Planning: A Unified View [with Amol Mali] Subbarao Kambhampa

Recently Viewed Presentations

  • Introduction to Security

    Introduction to Security

    These can be anyone from a juvenile to a doctor; these people generally use what they steal. Account for the largest number of shoplifters. ... This involves professional thieves operating as a network who steal, repackage and resell stolen goods....
  • Transport Cost

    Transport Cost

    Anything earned above the level of normal profit would be termed abnormal or supernormal profits, as these are rewards in excess of the risks of being in business. Transport classification of costs. Fixed Cost - cost that does not vary...
  • Day 1 - Japan.

    Day 1 - Japan.

    Shintoism continued... Believed in the Kami (this is like their gods/spirit) Kami - the nature spirits. They believe there are millions of different Kami's. Polytheistic - Worshiping many gods. Belief that humans, animals, plants, rocks and rivers have their own...
  • Photo Secession

    Photo Secession

    His deep interest in the photogram and the photomontage, provided a challenging option to the doctrine of straight photography, which, especially in the United States, dominated serious photography.
  • Classical Viewing Isaac Gang University of Mary Hardin-Baylor

    Classical Viewing Isaac Gang University of Mary Hardin-Baylor

    Times New Roman MS Pゴシック Arial Symbol ULA1 ClipArt Classical Viewing Objectives Classical Viewing Planar Geometric Projections Classical Projections Perspective vs Parallel Taxonomy of Planar Geometric Projections Perspective Projection Parallel Projection Orthographic Projection Multiview Orthographic Projection Advantages and ...
  • Understanding Analog Performance Specifications Agenda  ADC Operation  ADC

    Understanding Analog Performance Specifications Agenda ADC Operation ADC

    The Output equation might also have to be used in programs that use the ADC. Pay special attention to this equation. Note: Since 2N is greater than Output, the result of the division (Output/2N) will always be zero. Make sure...
  • Ny version Gasell 2008  version 8.0  Logica 2008.

    Ny version Gasell 2008 version 8.0 Logica 2008.

    Ny version Gasell 2008 - version 8.0
  • Austalk Meta Search | Home

    Austalk Meta Search | Home

    AusTalk provides a valuable and enduring digital repository of present day speech as a snapshot of For AusTalk Participants. If you were a participant in the data collection you can preview your own...