Class Note for CMPSCI 683 at UMass(4)
Class Note for CMPSCI 683 at UMass(4)
Popular in Course
Popular in Department
This 13 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 20 views.
Reviews for Class Note for CMPSCI 683 at UMass(4)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Anytime A Hierarchical A Other Examples of Hierarchical Problem Solving Jiaying Shen I I I CMPSCI 683 Revrews of A and Its varatrons Fall 2004 o Ais bestfirstsearch vvith fn gn t hn gm 0 Three changes make it an anytime algorithm derma ill Use a nonadmissible evaluation function f n to select M node to expand next so that suboptimal solutions arefound quickly Tum lZl Continuethe search afterthefirst solution is found using an auxiliary admissible evaluation function my to prunethe open list 0 Ideal m lllm l qualify in quot0 lime til When the open list is empty the last solution generated is 0 Traditional qualify maximizing optimal Anytime lillvm limilingl o Hovvto chooseanonadmissible evaluation function fin Ewynyhl SlhersbrnEV usercuvscim K Ewyrlyhl SlhersbrnEV Wampum l 0 Use n 1 whgin mhn Suppose you had the lollcwing situations how 0 Higherweight on hin tends to search deeper would you adiug W39 Admissible W is admissible and W 05 the open list has gotten so largethat you are running out of memory7 you are running out of time and you have not yet 0 Otherwise the search may not be optimal but it 7 normally nds solutions much faster reamed an answer there are a number of nodes on the open list Whose h value is very small 0 An appropriate w makes possible a tradeoff between the solution quality and the computation time swim mummy swim a minim mmwm swim a For each node store real fin glnlhlnl quality in is the lower bound on the cost of the best solution path through n When nd solution node n1 ini is an upper bound oithe cost olthe optimal solution Prune all nodes n on the open list that have real in V gt ini I Lime Whal would w 75 lppklihe7 Heavierweighls lend to Create more nl an anylirne eliecl swim mummy 2mm 7 minim summon 2mm x Idea Find a highlevel structure for a May mg solution and then use to nd detail solution Bene t Potentially Reduce signi cantly the size ofthe detail search space that needs to be searched comm S krshnlvlakr 2mm v Z lmmilm lputmnall lgnoring features of the world lgnoring constraints Limiting the horizon Limiting the number of goals Comm S krshnlvlakr 2mm u mum summon 2mm u A mapping if of states from state space Operates like A exceptthat hs is computed by ltSdgt into ltS d gt is an abstraction searching at the next higher level of abstraction transformation iff quot5 q lslq lw l d39ltbls1 tIgts2 sdls1 s2 The result is combined with other estimates eg cheapest operator cost to produce the Abstraction can be used in order to nal hs automatically create admissible heuristic 7 ms gtlo cheapest operator cost functmns 39quotSlel DlSlliG lgll 39 Heur39St39c values are bang Chad t quotquotvae Searching in Abstraction Space to Compute h using performance blind search sawmiszmwmicmim u wimmmwm 2mm u Embedding adding edges to the original graph corresponds to macro or relaxed operators Homomorphism grouping together sets of states to create a single abstract state corresponds to dropping a featurdvariable from the state representation Eliminate conditions Make possible new opeiatoi swim szmmmi 2mm is mum mmwm 2mm in If state 5 must be expanded by blind search then either 5 or Xs must be expanded by A using M The primary risk in using a heuristic e Astate isnenessaniyexpanoeo bybimo Search iiits disiarme mm the Stan State is Siriuiiy iess than the disianue immihe Stan state in the gnai state created by abstraction is that the total cost of computing h over the course AS a result of the search can exceed the sailings e no speedrupwhend is an embedding smue s mm mm 7 possibie speedup when c is a nnmnmmpmsm 39 Q What speedup can be achieved WWW sumquotva 2mm H mm mmwm 2mm ix sue mum Inga gages mm a mam nuance Isgrmpedtogaher mm nagmms mm mn The state with the highest degree is grouped together with its neighbors within a certain distance the abstraction radius to form a single abstract state WWW sumquotva 2mm w mum mmwm 2mm in TABLE 1 Native Hierarchical A abstraction deus 2 Semh 812th Nodeskpanded Observation all searches related to the 5 A EN mar mmwhmrm same base level problem have the same Levels level Sealch All Levels Baselevel goaL Elnnksri ll rl 866 W89 7766 l 18 j puzzle 96L 72Cl 348 3119 224 Fool39sDisk 4709 4096 1635 12680 629 This allows additional types of caching of Hallnl 7 7894 787 IDGD l8879 7m values 102000 3107 2736 1236 7059 641 MC 0 40 7 7071 l878 914 74 7 707 PL lnlul 39 73L 7 286 80b 7 Worth 5330 4493 1923 was 604 It leads to breaking Valtorta s barrler In 5 out of 8 search spaces A single base level search can spawn a large number of searches at the abstract level newquotva szlbusmln vlgsss mpscrm 21 mom sartmneveee mpscrm 22 Na39l39ve Hierarchical A e Cacne n rn abstract space 39lABLL z Hierarchical 2 tlbslltwlluululliu 2l v1 h caching Nodes Expanded prohlems e Cacne exact n s nu along optrrnal solutlorl rn abstract space stulolt Blmll thermolqu A v3 lt33 Explelt lnmrtnersearcnes ln abstract space and cacnereruse ln base Spam Search Naive VI V7 V out nf 700 D EVE EEE39EH t n W t b m h Blocksrj 38 266 1235 43 402 96 e oes no preserve rnono one prope res no cornpara evvl I butdonlmeedmeopennodes Srpuzzle 318 3119 1616 SSI 563 1l V2 Fool39s Dlsk 1635 139 30 3612 3950 1525 132 Harm 7 law lame mm 5357 3 l74 ll 7 Cacne optrrnal patn rn abstract space optlmalrpam cacnrng 2000 H36 7059 3490 15 1028 171 V3 MC 6074011 934 2412 1531 1154 863 12s 7 Remember optrrnal patn lengtn rn abstract searcn space Peg Permuteo 286 806 482 279 242 113 WWW Words 1923 19336 r591 2349 1410 124 P belrlg optrrnal patn length rrurn startto gual rn abstractspace newquotva szlbusmln vlgsss mpscrm 21 mom sartmneveee mpscrm 24 0 Increasing the radius nf abstractinn has th cnntradictnry effects abstract spaces cnhtain fewer states and each abstract search prnduces values fnr mare states but the heuristic is less discriminating The best case breaks the Valtnrta s barrier in every search space new va 5211basmm vtgssq mpscrm 25 TABLE 3 Hierarchich A39 thest abstraction Imus Search Spam mucus 5 puzzle Fuut39s Dbk 11am KLZDDO MK39 107409 Pennies Wnrer Rams Nams hxpmmcd Dlmd Smelt 389 34s 1635 1009 1236 724 286 1 1m mammava Naive V3 611 309 354 340 131K 1111 109 1035 1306 1011 s22 50 201 194 171114 I356 or prnwcrns v3 lt 135 um u 200 123 131 191 11 178 144 192 m PH second Dlmd Search 69 35 873 101 398 Wm 83 1 1m V3 86 40 902 108 381 9 s2 67 w u mm s thbasmm vtgssq mpscrm 2e mnmm r quotxumm q j m am 531mb space 11 mm ANAL new va 5211basmm vtgssq mpscrm 27 Traditional problem solver e prebtem space seter uperaters setur states 7 Probtern 1nrtra1 state Guat state Hierarchical problem solver 7 Generate abstractron spaces Set Elf uperaturs and states 7 Produce sotutr on 1n nrgnest abstraction space Map trern eperaters and states 1n gruund space 7 Renne down to ground 1eve1 Map tn uperaters and states 1n gruund space mm s thbasmm vtgssq mpscrm 2e MovLDtsnajnotnjEczjojEca 01mm lon m peg tmtmnm pagztt mtmnm pagztt tmtmnm pagan tmtmnm peanut pr ttmtm m PEST 1 quot 5 Pl llll targets MOVErotsnzfnoMJEcuojEca 1mm ton askt pm tmttm um pegztt tmttm um pagan 11quotquot 1 quot 3954 PEST Pt 1 quot Ski Pl llll areas A wallet otsk Lth be always moved mtnnut tnlerletttto win a latoe otskll cmwmt Smxrshnlvtaw cmrm Idea Abstraction spaces are formed by removing sets of literals from the operators and states of the domain Premise Literals in a domain only interact with some ofthe other literals r ltletals trt D3 moves do rtol trtletaelvvtllt ltletals trt D2 moves Metho artition literals into classes based on their interactions and orderthe classes This forms a monotonic hierarchy of abstraction spaces that is any plan to achieve a literal cannot add or delete a literal higher in the hierarchy 2 mm snrmem 2mm Jo bpffnnn repeennn riman mnm39rntrtmrmrm 9 mathth mmmruvmmnsr r mramumnurznmuns I ewe a tn m nwttt nee ame agpttm tm nmm 1 mnratn sw mt zte39cenwmmrrennrm Otmplevly 0utt7 e ts numbet et upetatuts n ts numbet El ertteent tttslattltaleo Metals cmwmt Smxrshnlvtaw cmrm A smallet otsk Lth be altaysmoveownttom tttlerletttto mtn a latoe lskll A otremeo eooe tnotLaleslhal the rst tnerat nustbe at a nrgner nrtne same letel on dtxkl wall 3939 m ken rx r dklps tal twat Level 1 3t mum snrmevm 2mm 2 Cuwnght Slebevslein av Lassen CMPSCl 583 33 Plans using a hierarchy of abstraction spaces Tries to avoid backtracking by working on more important goals first Criticality assigned to preconditions by user and adjusted by system based on ability of operators to achieve them At each level planner would assume less critical preconditions to be true Cuwnght Slebevslein av Lassen CMPSCl 583 35 Solution to an ndisk problem will require 2quot steps Backtracking across abstraction levels or subproblems within an abstraction level is never required Search space reduction is from exponential 0b39 to linear 0L in length of the solution where b is the branching factor Never factored in construction of abstraction space assumption used over and over for many problems Cupynght Slebevstem gv Lassen CMPSCl 683 34 sum men w m mm mm cum m nah u 4 m n er me n mquot e V m mm my mum rk M e we a me a l mm mm 9 mm a nil mum 1 Gel m a e m M m M a m em 4 W w cemng Slebevstem w Lesser mm x C as Assign precondition criticaii es Mm mm amm m m mun um w x MW n w mm w z Hum x mm Sziheraein a Viz en mvsci m 37 i nonhuman raw 3 545453453 522m3m ox imam EZE39SS iGU weave 553 in Ann Xpmhimg mm D in 25 mama szmaeoiau 553lti21 252 mm mm m w I m w jw ii mm mum ya Anl imiiii ita immmu Mb39zigo39i l hkx iiniw Equm n mi 7 immssammm 3E What are open list and closed list Why do we need them Why is Aoptimal Why does A suffer from high memory requirement Enang s mammavum mvscisxa on Maui mm M NH How is DA different from standard iterative m nmm 1m deepening 11 n W atquot mu What is the fbnund of each iteration Why does DA use less memory than Aquot What problems dnes DA suffer from m sum 1mm i uwx i um in w 55 mm mm mmwm 2mm u cmwmi mmva anim n mom Enmim M E m mm x in nu min Nu m Aha quotmin m m m Vrdmmmigfsgmz m n a 5m Emwmi mmva swim a mum mmwm mum is Why do we need to memorize the best 1 alternative path Why do we need to memorize the best m m m descendent of a forgotten node GD W Why does RBFS need less space than A m a m Wh is RBFSn timal Whyt bl RBFS ff f 7 M w a pro em nes su er rnm M an m W m Emynw mmva 2mm ts mum snmwm 2mm um W w W n W W M wm 5 Du We end here Emynw mmva 2mm n mum snmwm mm mm m Sn utmn Tmmd s t nphmaW u Why do we need to back up the best fvalue of all the successors of a node Why do we need to back up the fvalue of a node s best forgotten child ls SMA optimal Why Why is SMAquot guaranteed not to get stuck in a loop mum SlehasmmMlgssq mmm Iterative Improvement Simulated Annealing Hill Climbing Solution RepairDebugging GSAT Heuristics for CSP texture measures mm s lebasmm vlgssq msmm 6n
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'