Class Note for CMPSCI 683 at UMass(6)
Class Note for CMPSCI 683 at UMass(6)
Popular in Course
Popular in Department
This 8 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 44 views.
Reviews for Class Note for CMPSCI 683 at UMass(6)
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
2 Continuation ofSyslematic Search for CSPs More Complex Search Victor Lesser CMPSCI 683 Fall 2004 Vlb l mlm Z mm state the empty assignment functionBACKTRACKllGSlllfllcsplrelurnsasolutimlmfailure return RECURSWEBll llklllllllGl 0 l Successor lUllClIOll a value can be H l assigned to any variable as long as function RECURSllEBACKTRllKllGlamigmllll plrelurnsnsolullomrllllule ilwiwmmrlscomletelllnIllurnasslvnmcw noconstramtlswolated I l 1 vare lmLNlssJGVEDlllulullllAlllBLElcsplmgmlmclpl 39 Goal test the current assignment is forelchvalleinORDERDOMllVl lwlslmnarsigmnlnmlvldo complete if value is conslslent will alliglmenlaccordlng 10 C0lll1ll llalpl then I l l llllERECUllSll39EBACKTMCKJMWlWllc llllmlll ll tlpl Path COSt39 a consul 00 for every ilresull llilzvrelhenreturnmsul Step end relurlfllllm v mme K v lawman Al Wl39HDd Wlim Nigreeii iiiiiue 4P WAiE Nigimi 04er i An arc from Xto Yin the constraint graph is consistent if for every value of x there is some value of Ythat is consistent with X Can detectmore inconsistencies than forward checking Can be applied as a preprocessing step before search As a propagation step after each assignment during search how is this advantageous Process must be applied repeatedly until no more inconsistencies remain Whi Reduce the branching factor by deleting values that are not consistent with the values ofthe assigned variables FonNard checking a simple kind of propagation WA in 0 Raw v SA T lrilialdomains RGERGB RGE GE RGERGE REE Al lerV lAiej GE RGE GE F63 GE RGE Amman a e R a R c 3 E R s e Merlhlae a G R R s a 0 r anammechnum m o nsw v SA r W lJIZIEIZIIIIJZIIIEI 9 W W i was VINSW CE Wmmw sum No possible solution with WAred and Qgreen mnmsllmm x nimi ilm nuilre ptmllllymlhredu Amman inpnls uni airing sewn lamblchs X3 lacnl variable nunln a qnene at ales mmally allr e ms in can lnnn nnila thut39 Min amply tin ix XJOKLlllOVErl RUNqulit39lldl if RM m l rll 0ll l NlVAl lll or anal xi in XErGHEoRSle do attain 39iwilwic lgllnen propagates effems hm network and funm on REMO Erlt 0 mummies X X1 mum true in ne remove a value mn39ll39tti t itilu loop or each x in Do leerYgl do new a mnlmncycm no he ansnaa m some vane yln nonnmngl inen ddele x from DOMNMW lenwveltnne and ram rn YUlllilLL end v mmcm m w A binary CSP has at most 0n7 arcs Each arc X gtY can only be inserted on the agenda d times because at most d values of Ycan be deleted Checking consistency of an arc can be done in 0d7 time Worst case timecomplexity is 0n2d Does not reveal every possible inconsistency v new in in A graph is k consistent if for any set of k variables there is always a consistent value forthe kth variable given any consistent partial assignment for the other k 1 variables 7 A graph is strongly laconsistent if it is erOrlSlSlerll for i l k e lF Krlurnber of nodes tnan no backtracklrlg Higher forms of consistency offer stronger forms of constraint propagation 7 Reduce amountofbacktracklflg 7 Reduce effecthe branchlflg factor 7 Detectlrlg inconsistent partial assignments Balance of howmuch preprocessing to get graph to be k consistent versus more search v mmcm m i i Mrquot nicinnigirai nariiiiatling always hacktrackto most recent assignment Not enicient Carillliil Get A set olvariahles that caused the lailnre Eatklllmplllu backtracktotne most recent variable assignment in the con i set Simple modnication olBACKrRACKINGSEARCH leed iaiiaale niaeiing GNSWVISAWANT lonswvfi Skz backup in T makes nu sense Wnat Variables Caused lne Cunllicl 9 o 39 Forward Checking can also generate conlliclset based on variables that remove elements lroln domain Batklratkln V most retenlvarlable set lfl Enfllllrl set v new in ii LDilTlitJl unmet naextumpmg better de nition olconllictsets leads to better perlormance holtomnptopdown state integration WAred NSWred can never be solved T red lhen assign NT G V SNalWayslails HnWln knowlhal indirect DDMllUl sel nlNT is WAand NSW sere they don t Conlliolwilh NT Conlliol set DTNT is selnlpreoedmg yanabieslhal Daused NT lngelher Willi any subsequenlvanables lo have no Consistent solutions SAlaiis oonlliollWANT G based on forward propagation baoklump to o o absorbs Conlliol sel olSA minus a WA NSW NTL backiump to NT NT absorbs oonlliol sel olG minus NT WA NSWL worm 3 1m 93 341th Plummle lNFORMEDrENZKTRNZK WRSLEFT VARSVDONE it all variables are Corsiaenl men minimquot inmd STOP Lei WM a variable in WRSVLEFT mat is in Emlle Maren random Remove WR Ymm WRSVLEFT PM WM min WRSVDONE Let VALuES its ntmsstme valuesloWAR ordered in agenan order ammth to mmme otoomlids win varieties erARSrLEFT mmmmmneunsnc Foream mm in VALuES until minim loom iWALUE does mt mnllid wtn anyyanademal ismVARSDONE mm ssign VALuE to VAR Cali iNFORMEDrEAEKTRAEKWARSLEFT VARSVDONE end ll end rm end pmoedure Begin pmgmm Let yARsLErr its at all yaiaoies eam assgnee m vvnai sate Let VARSVDONE mi Cali iNFORMEDrEMKTRAEKOARSVLEFT VARSDONE End pmgmm mnmsumm u 39 yihll j The complexity of solving a CSP is strongly related to the structure of its constraint graph Decomposition into independent subproblems yields substantial savings Didquot u Oldcrnc Tree slruclured problems can be solved in linear time Oln d1 Cutset conditioning can reduce a general CSP to a treestructured one and is very e icient if a small cutset can be found worm is 1 loose a variable as roul order Valiables from root to leaves such that every node s patent precedes it in the ordering 2 For 1 lromndown to 2 applyREuovolyconsmemiPmntiXl 39 3 For y mm 1 to it aeign A wustttentiy with Pvr39evHXJ mnmsumm a 5 are a special kind of probierri Conditioning instantiate a variable prune its neighbors domains Smes de ned 5 wines 1 M 5 039 quotWhile goal res defined is mnsrlainrs oh vshsbis vaiues A in a n U Backtracliin depthstirst search with one variable assigned ssh nod V Variabie ordering and value selmion heuristics lielp signifimntiy 0 Forward checking prevenls assignments that guarantee iater failure G Conslrainl propagation 5 are consistency does additivnai wash to constrain values and detect lnconsistences s s s a The CSP i resentation ziiows anai sis of mblem structure Cutset conditioning instantiate in all ways a set of variables p y P such that the remaining constraint graph is a tree Treesstiuctured CSPs ssh be soived in linear time Cutset size 5 a runiime oisrhe Mi very last is small c Iterative mincontra is usvziieiieuive in warm m Operators applicableto a search node are not affect by path to node Markcixlike assumption Rating of one search node doesn t affect MultiLevelHierarchical Search lnterdependence of Search Paths N0nM0n0tonic Dom am rating of others nodes on different paths Near independence of search Paths Cost of Control Contrast Nonuniform cost of operator application 39Drilling example quot samples ken 0m 0 well may change the likelihood of olher well being successful vunmsixmmh is mnmsllmm m Woni List Mt Lasei Ale Lee Eel Lille Hike Sails Hos Sheet Keel Steel iieunsuc Search Km Ti ShiesOpemiorsi Each numbered row L418 and column 356 Independence of StatesOpemiorsi If4 i1nequotiiien no my to fill 1n5 woman 1i Crossword Puzzle Search as Interacting Subproblems Walt Filteiing Exploiting PaiiVi se Constraints Examinations 000k EDiMiii EDquot PdthiizziuJani f uunt Pniziixilh APmianiiti What happens if you add in more constraints among words Grammar heme What happens if you add in speech input 7 Probabiisiib knowiedge about Word iikeiihnnd r Constraint saiisiaciimi vs Constraint optimization 39 Ham and suit Lnnsiiainis How does the interaction among subproblems change woman 2 Subgoals B and 0 cannot be solved independeniiy El giCi aim From the pespective of subgoai B subgoai D appears to be the best soiution cost oi2 vs cost of 5 Lian subgod C but since 0 must aiso be sanded to sdve A the overaii best sdution is subgoai C mnmslmlm 2t Simple blocks world problem initia Hna Inhial state ONCACLRBCLRC Goal state ONBCONABCLRA Operators 1i Clearaimomxyl A CLRM CLRy 2i Put0nCLRw A cuzm 0mm Decompos ion with subgoal interactions Cannot just combine the solutions to omega and cums since eachsolution malm the othersolution invalid tomsmi 2o Take into account the existence of other states or solution to other subproblems ARC consistency Reevaluate rating nodeoperator Reduce yariancei uncertainty in rating Decrease cost of operator application V eliminates Certain states as inleasible Some problems are nearly decomposable Their subproblems have only a small amount of interaction A goal that can be decomposed into a set of subgoals is nearly decomposable if most ofthe time independently considered solutions to the subgoals can be combined into a consistent solution to the goal Only a subset ofthe subgoal solutions interact so as to be inconsistent Consistent solutions can be found without completely resolving the joint subproblem tomsmi 2x Two states both apply to same operatorampdata Many Al techniques have been developed to handle nearly decomposable problems 39 TW quotOdes A amp 3 ratquot19A gt ratiquot93 If extended by same data then ratingA1 gt rating Bl Typically thIs Involves Independently soIVIng AEK the subproblems and then repairing the solutions to deal with any interactions How does it relate to success of Heuristic RepairLocal Search success Dynamically evolving interacting subproblems pl I ilwilcmmvquoti lt lHymnquotmurmur NourMouotoue Example v uxxvcssmrmm m v uxxmssmrmni I Blackboard Systems v uxxvcssmrmm 1
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'