swappedgraphsearch

EdgePartitioninginExternal-MemoryGraphSearchRongZhouPaloAltoResearchCenter3333CoyoteHillRoadPaloAlto,CA94304rzhou@parc.
comEricA.
HansenDept.
ofComputerScienceandEng.
MississippiStateUniversityMississippiState,MS39762hansen@cse.
msstate.
eduAbstractThereiscurrentlymuchinterestinusingexter-nalmemory,suchasdiskstorage,toscaleupgraph-searchalgorithms.
Recentworkshowsthatthelocalstructureofagraphcanbeleveragedtosubstantiallyimprovetheefciencyofexternal-memorygraphsearch.
Thispaperintroducesatechnique,callededgepartitioning,whichexploitsaformoflocalstructurethathasnotbeencon-sideredinpreviouswork.
Thenewtechniqueim-provesthescalabilityofstructuredapproachestoexternal-memorygraphsearch,andalsoguaran-teestheapplicabilityoftheseapproachestoanygraph-searchproblem.
Weshowitseffectivenessinanexternal-memorygraph-searchalgorithmfordomain-independentSTRIPSplanning.
1IntroductionBreadth-rstsearch,A*,andrelatedgraph-searchalgorithmsstoregeneratednodesinmemoryinordertobeabletodetectduplicatesandpreventnoderegeneration.
Thescalabilityofthesegraph-searchalgorithmscanbedramaticallyincreasedbystoringnodesinexternalmemory,suchasdiskstorage.
Becauserandomaccessofdiskisseveralordersofmagni-tudeslowerthaninternalmemory,external-memorygraph-searchalgorithmsuseduplicate-detectionstrategiesthatseri-alizediskaccessinawaythatminimizesdiskI/O.
Awidely-usedapproachtoexternal-memorygraphsearchisdelayedduplicatedetection[SternandDill,1998;Korf,2004;Edelkampetal.
,2004].
Initsoriginalandsimplestform,delayedduplicatedetectionexpandsasetofnodes(e.
g.
,thenodesonthesearchfrontier)withoutcheckingfordu-plicates,storesthegeneratednodes(includingduplicates)inadiskle,andeventuallyremovestheduplicatesbysort-ingthele.
Inkeepingwithitsusebytheoreticalcomputerscientistsinanalyzingthecomplexityofexternal-memorygraphsearch[MunagalaandRanade,1999],delayeddupli-catedetectionmakesnoassumptionsaboutthestructureofthesearchgraph(exceptthatitisundirectedandunweighted).
Recentworkshowsthattheperformanceofexternal-memorygraphsearchcanbesignicantlyimprovedbyex-ploitingthestructureofagraphinordertolocalizemem-oryreferences.
ZhouandHansen(2004;2005;2006b)pro-poseatechniquecalledstructuredduplicatedetectionthatexploitslocalstructurethatiscapturedinanabstractrepre-sentationofthegraph.
Forgraphswithsufcientlocalstruc-ture,structuredduplicatedetectionoutperformsdelayeddu-plicatedetectionbecauseitnevergeneratesduplicates,eventemporarily,andthushasloweroverheadandreducedcom-plexity.
KorfandSchulze(2005)showhowtoimprovetheperformanceofdelayedduplicatedetectionbyusingsimilarlocalstructuretoreducethedelaybetweengenerationofdu-plicatesandtheireventualdetectionandremoval.
Althoughapproachesthatexploitagraph'slocalstructureareveryeffective,theydependonagraph-searchproblemhavingtheappropriatekindoflocalstructure,andasufcientamountofit,inordertobeeffective.
Thusonecanlegit-imatelyquestionwhethertheseapproacheswillbeequallyeffectiveforallgraphs,oreffectiveatallforsomegraphs.
Inthispaper,weintroduceatechniquethatexploitsadif-ferentkindoflocalstructurethanisexploitedinpreviouswork.
Thekindoflocalstructureexploitedbythistechniqueisinsomesensecreatedbythewaythealgorithmexpandsnodes,inparticular,byuseofanovelformofincrementalnodeexpansion.
Thenewtechnique,callededgepartition-ing,canlocalizememoryreferencesinanygraph,nomatterwhatitsstructure–evenafully-connectedgraph.
Moreover,thewaythisnewtechniquelocalizesmemoryreferencescom-plementsthekindoflocalgraphstructurethatisexploitedbypreviousapproaches.
Thisallowsthenewtechniquetobecombinedwithpreviously-developedapproachesinordertocreateamorepowerfulexternal-memorygraph-searchalgo-rithm.
Inthispaper,wefocusonhowtouseedgepartition-ingtoimprovetheperformanceofstructuredduplicatedetec-tion.
Weimplementitinanexternal-memorygraph-searchal-gorithmfordomain-independentSTRIPSplanningthatusesstructuredduplicatedetection,andshowthatitgreatlyim-provesscalability.
Atthecloseofthepaper,wediscusshowedgepartitioningcanalsobeusedtoexploitlocalstructureindelayedduplicatedetection.
2StructuredduplicatedetectionStructuredduplicatedetection(SDD)[ZhouandHansen,2004]isanapproachtoexternal-memorygraphsearchthatleverageslocalstructureinagraphtopartitionstorednodesbetweeninternalmemoryanddiskinsuchawaythatdupli-catedetectioncanbeperformedimmediately,duringnodeex-IJCAI-072410pansion,andnoduplicatesareevergenerated.
Thelocalstructurethatisleveragedbythisapproachisrevealedbyastate-spaceprojectionfunctionthatisamany-to-onemappingfromtheoriginalstatespacetoanabstractstatespace,inwhicheachabstractstatecorrespondstoasetofstatesintheoriginalstatespace.
Ifastatexismappedtoanabstractstatey,thenyiscalledtheimageofx.
Onewaytocreateastate-spaceprojectionfunctionisbyignoringthevalueofsomestatevariables.
Forexample,ifweignorethepositionsofalltilesintheEightPuzzleandconsideronlythepositionofthe"blank,"wegetanabstractstatespacethathasonlynineabstractstates,onecorrespondingtoeachpossiblepositionoftheblank.
Givenastate-spacegraphandstate-spaceprojectionfunc-tion,anabstractstate-spacegraphisconstructedasfollows.
Thesetofnodesintheabstractgraph,calledtheabstractnodes,correspondstothesetofabstractstates.
Anabstractnodeyisasuccessorofanabstractnodeyifandonlyifthereexisttwostatesxandxintheoriginalstatespace,suchthat(1)xisasuccessorofx,and(2)xandxmaptoyandy,respectively,underthestate-spaceprojectionfunction.
Figure1(b)showstheabstractstate-spacegraphcreatedbythesimplestate-spaceprojectionfunctionthatmapsastateintoanabstractstatebasedonlyonthepositionoftheblank.
EachabstractnodeBiinFigure1(b)correspondstothesetofstateswiththeblanklocatedatpositioniinFigure1(a).
Instructuredduplicatedetection,storednodesintheorigi-nalsearchgrapharedividedinto"nblocks"witheachnblockcorrespondingtoasetofnodesthatmapstothesameab-stractnode.
Giventhispartitionofstorednodes,structuredduplicatedetectionusestheconceptofduplicate-detectionscopetolocalizememoryreferencesinduplicatedetection.
Theduplicate-detectionscopeofanodexintheoriginalsearchgraphisdenedasallstorednodes(orequivalently,allnblocks)thatmaptothesuccessorsoftheabstractnodeythatistheimageofnodexundertheprojectionfunction.
IntheEightPuzzleexample,theduplicate-detectionscopeofnodesthatmaptoabstractnodeB0consistsofnodesthatmaptoabstractnodeB1andthosethatmaptoabstractnodeB3.
Theconceptofduplicate-detectionscopeallowsasearchalgorithmtocheckduplicatesagainstafractionofstorednodes,andstillguaranteethatallduplicatesarefound.
Anexternal-memorygraphsearchalgorithmcanuseRAMtostorenblockswithinthecurrentduplicate-detectionscope,andusedisktostoreothernblockswhenRAMisfull.
SDDisdesignedtobeusedwithasearchalgorithmthatexpandsasetofnodesatatime,suchasbreadth-rstsearch,wheretheorderinwhichnodesinthesetareexpandedcanbeadjustedtominimizediskI/O.
SDD'sstrategyforminimiz-ingdiskI/Oistoordernodeexpansionssuchthatchangesofduplicate-detectionscopeoccurasinfrequentlyaspossible,and,whentheyoccur,theyinvolvechangeofasfewnblocksaspossible.
WhenRAMisfull,nblocksoutsidethecur-rentduplicate-detectionscopeareushedtodisk.
Writingtheleast-recentlyusednblockstodiskisonewaytoselectwhichnblockstowritetodisk.
Whenexpandingnodesinadifferentnblock,anynblocksinitsduplicate-detectionscopethatarestoredondiskareswappedintoRAM.
Figure1:Panel(a)showsallpossiblepositionsoftheblankfortheEightPuzzle.
Panel(b)showsanabstractstate-spacegraphthatiscreatedbythestate-spaceprojectionfunctionthatconsidersthepositionofthe"blank"only.
3EdgePartitioningThekindoflocalstructurethatisexploitedbySDDiscap-turedinanabstractstate-spacegraphwhenthemaximumoutdegreeofanyabstractnodeissmallrelativetotheto-talnumberofabstractnodes.
Thelargestoutdegreeofanyabstractnodereectsthelargestduplicate-detectionscope,andthisinturndeterminestheinternal-memoryrequire-mentsofthesearchalgorithm.
Experimentsinseveraldo-mainssuggestthatthisformoflocalstructureispresentinmanysearchproblems[ZhouandHansen,2004;2005;2006b].
Howeveritispresentinvaryingdegrees,andthereisnoguaranteethatitispresentineverysearchproblem.
More-over,thedegreetowhichitispresentcanaffectthedegreeofscalabilitythatispossible.
ThismotivatesthedevelopmentofatechniquethatmakesSDDeffectiveregardlessofwhether,andtowhatdegree,thiskindoflocalstructureispresent.
Infact,thenewtechniqueweintroduceiseffectiveeveniftheabstractstate-spacegraphisfully-connected,andthuscapturesnolocalstructureatall.
Theideabehindthistechniqueisthatthelocalstructureex-ploitedbySDDcanbecreated,insomesense,byexpandingnodesincrementally,whichmeansgeneratingonlysomeofthesuccessorsofanodeatatime,andgeneratingtheothersuccessorslater.
Incrementalnodeexpansionmakesitpos-sibletopartitiontheoriginalduplicate-detectionscopeintosmallerduplicate-detectionscopes,andthiscansignicantlyreducetheinternalmemoryrequirementsofthealgorithm.
IntheoriginalformofSDD,theduplicate-detectionscopeofanodebeingexpandedisdenedasallstorednodesthatmaptoanyabstractnodethatisasuccessoroftheabstractnodethatistheimageofthenodebeingexpanded.
Thusthelargestduplicate-detectionscopereectsthelargestnum-berofsuccessorsofanodeintheabstractgraph.
Butthisassumesthatallsuccessorsaregeneratedatthesametime.
Ifnodesareexpandedincrementally,itispossibletosubdi-videthisduplicate-duplicatescopeintosmallerscopes,oneforeachpairofabstractnodeandsuccessorabstractnode,or,equivalently,oneforeachoutgoingabstractedge.
Thisisthekeyideaofedgepartitioning.
Itconsidersasetofnodesthatmaptoaparticularabstractnode,andapar-ticularoutgoingabstractedge,andonlyappliestheopera-torsthatcorrespondtotheabstractedge,inordertogenerateonlythesuccessornodesthatcorrespondtothesuccessorab-stractnodealongthatedge.
Asaresult,inedgepartitioning,IJCAI-072411theduplicate-detectionscopeconsistsofonlyasinglenblockcorrespondingtothesingleabstractnodethatisthesuccessorofanabstractedge.
Atalaterpointinthealgorithm,adiffer-entoutgoingabstractedgeisconsidered,andadifferentsetofoperatorsareappliedtothesamesetofnodes,inordertogenerateadditionalsuccessornodeswithpotentialduplicatesinadifferentnblock.
Eventually,alloperatorsareappliedtoasetofnodesandtheybecomefullyexpanded.
Notethatfullexpansionofanodenowrequiresasequenceofincrementalexpansions.
3.
1OperatorgroupingThestate-spaceprojectionfunctionandabstractstatespacegraphusedbySDDwithedgepartitioningarethesameasforSDDinitsoriginalform.
Butsincenodesareexpandedincre-mentally,andonlyoneabstractedgeisconsideredatatime,itisnowimportanttoidentifywhichoperatorsareassociatedwitheachabstractedge,inordertoknowwhichsuccessorstogenerate.
Werefertothisannotationoftheedgesoftheabstractgraphasoperatorgrouping.
Wepointoutthatan"operator"herereferstoaninstantiated(orgrounded)opera-tor.
Forexample,theEightPuzzlehasatotalof192groundedoperators,eventhoughthereareonlyfour(left,right,up,anddown)operatorspriortoinstantiation.
Operatorgroupingisbuiltontopofstateabstraction.
LetObethesetofallinstantiatedoperatorsofasearchproblem.
Anoperatoro∈Oisapplicabletoanabstractnodeyifandonlyifthereexistsastatexintheoriginalstatespace,suchthat(a)oisapplicabletox,and(b)xmapstoy.
ConsidertheEightPuzzle.
Thereare2*8=16operatorsthatareapplica-bletoabstractnodeB0,becausetheblank,whenlocatedatthetop-leftcornerofthepuzzleboard,canmoveeitherright(B0→B1)ordown(B0→B3),andeachmovehas8differ-entinstantiations,dependingonwhichtileoftheEightPuz-zleismovedintotheblankposition.
Similarly,eachoftheabstractnodesB2,B6,andB8has16applicableoperators.
AbstractnodesB1,B3,B5,andB7eachhave3*8=24applicableoperators,andabstractnodeB4has4*8=32applicableoperators.
Oncethesetofapplicableoperatorsforeachabstractnodeisdetermined,operatorgroupingidenties,foreachapplica-bleoperator,theabstractedgeitisassociatedwith.
Anab-stractedge(y,y)isanedgeintheabstractgraphthatcon-nectsapairofabstractnodesyandy,ifandonlyifyisasuccessorofy.
Werefertoy(y)asthesource(destination)ofabstractedge(y,y).
LetOybethesetofoperatorsapplicabletoabstractnodey.
Anoperatoro∈Oyisassociatedwithanabstractedge(y,y)ifandonlyifthereexiststwostatesxandxintheoriginalstatespace,suchthat(1)oisapplicabletox,(2)xistheresultingstateafterapplyingotox,and(3)xandxmaptoyandy,respectively.
Foroperatorswithdeterministiceffects,itiseasytoseethatforeveryo∈Oy,thereisauniqueabstractedge(y,y)thatoisassociatedwith.
Essentially,thereisamany-to-onemappingfromtheoperatorspacetotheabstract-edgespace.
Toexploitlocalstructureintheoperatorspace,edgeparti-tioningusesoperatorgroupingtodividethesetofapplicableoperatorsOyforabstractnodeyintooperatorgroups,oneforeachsuccessorofyintheabstractgraph.
AnoperatorgroupOy,yisasubsetofOythatconsistsofalltheopera-torsthatareassociatedwithabstractedge(y,y).
NotethatOy,y∩Oy,y=forally=y,andy∈successors(y)Oy,y=Oy,wheresuccessors(y)isthesetofsuccessorsofyintheab-stractgraph.
Althoughthetechniqueofoperatorgroupingispresentedhereinthecontextofsearchingimplicitly-representedgraphs(i.
e.
,graphsrepresentedbyastartstateandasetofoper-atorsforgeneratingsuccessors),itshouldbeclearthatthesametechniqueapplieswithlittlemodicationtosearchingexplicitly-representedgraphs(i.
e.
,graphsrepresentedbyasetofverticesandasetofedges).
3.
2Edge-partitionedduplicate-detectionscopeTheideaofedgepartitioningforSDDistosubdividetheduplicate-detectionscopeintosmallerscopes,oneforeachabstractedge,anduseonlytheoperatorgroupthatisassoci-atedwiththeabstractedgetogeneratesuccessorsatatime.
Thisleadstotheconceptofduplicate-detectionscopeforanabstractedge,whichisdenedasfollows.
Denition1Theduplicate-detectionscopeforanabstractedgeisthesetofstorednodesthatmaptothedestinationoftheabstractedge.
Theduplicate-detectionscopeforanabstractedgeisguar-anteedtocontainonlynodesthatmaptoasingleabstractnode,regardlessofthestructureoftheabstractgraph.
Thefollowingtheoremfollowsfromthedenition.
Theorem1Theduplicate-detectionscopeforanabstractedgecontainsallstoredduplicatesofthesuccessorsgener-atedbyapplyingitscorrespondingoperatorgrouptothesetofnodesthatmaptothesourceoftheabstractedge.
Theorem1guaranteesthatedgepartitioningonlyneedstostoreasinglenblockinRAM,inordertocatchallthedu-plicatesthatcouldbegenerated,evenintheworstcase.
Thisworksinthefollowingway.
Foreachabstractedge(y,y),edgepartitioningusesoperatorso∈Oy,ytogeneratesuc-cessorsfornodesthatmaptoabstractnodey.
Afteredgepar-titioninghasexpandedthesenodesusingoneoperatorgroup,itusesadifferentoperatorgroupOy,ytogeneratesucces-sorsforthesamenblock,untilalloperatorgroupshavebeenusedingeneratingsuccessorsforthenblock.
Thenitchoosesadifferentnblocktoexpandnext.
Becausenotallsuccessorsaregeneratedbyedgepartition-ingwhenanodeisexpanded,wecallanodeexpansioninedgepartitioninganincrementalexpansion.
Nodeseventu-allybecomefullyexpanded,oncealloperatorsareapplied.
3.
3ExampleWeusethefollowingexampletoillustratehowedgeparti-tioningworksinSDD.
LetxibeasearchnodethatrepresentsastateoftheEightPuzzlewiththeblanklocatedatpositioniasshowninFigure1(a).
SupposethereareonlytwostoredIJCAI-072412nodes{a0,b0}thatmaptoabstractnodeB0showninFig-ure1(b).
Let{a1,a3}and{b1,b3}bethesuccessorsofa0andb0,respectively.
(Thesubscriptencodesthepositionoftheblank.
)Whenedgepartitioningexpandsnodesa0andb0,itrstusesoperatorso∈OB0,B1.
Thiscorrespondstomovingtheblanktotheright,togeneratethersttwosuc-cessornodesa1andb1.
NotethatonlynodesthatmaptoabstractnodeB1needtobestoredinRAMwhena1orb1isbeinggenerated.
Next,edgepartitioningusesoperatorso∈OB0,B3,whichcorrespondtomovingtheblankdown,togeneratethethirdandfourthsuccessornodesa3andb3.
Thistime,onlynodesthatmaptoabstractnodeB3needtobestoredinRAM.
4ImplementationBeforediscussingsomestrategiesforimplementingSDDwithedgepartitioninginanefcientway,wereviewthekeystepsinimplementingSDD.
First,beforethesearchbegins,SDDusesastate-statepro-jectionfunctiontocreateanabstractgraphthat(hopefully)captureslocalstructureintheoriginalsearchgraph.
Thestate-spaceprojectionfunctionpartitionsstorednodesintonblocks(oneforeachnodeintheabstractgraph)thatcanbemovedbetweenRAManddisk,andsoeachnblockmustbeabletotinRAM.
Thestate-spaceprojectionfunctioncanbehand-craftedorautomaticallygenerated,asdescribedin[ZhouandHansen,2006b].
Likedelayedduplicatedetection,SDDisdesignedtobeusedaspartofasearchalgorithmthatexpandsasetofnodesatatime,suchasthefrontiernodesinbreadth-rstsearch.
TheideaofSDDistoexpandthesenodesinanorderthatminimizesdiskI/O.
Thisisaccomplishedbyexpandingnodeswiththesameduplicate-detectionscopeconsecutively,andminimizingchangesofduplicate-detectionscopeduringex-pansionofallnodes.
Asimpleandeffectiveheuristicistoex-pandnodesinorderofnblock,withnblocksorderedaccord-ingtoabreadth-rsttraversaloftheabstractgraph.
WhenRAMisfull,SDDneedstodecidewhichnblockstomovefromRAMtodisk.
Asimpleandeffectiveheuristicistowritetheleast-recentlyusednblockstodisk.
SDDwithedgepartitioningusesasimilarstrategyoftry-ingtominimizechangesofduplicate-detectionscopeduringexpansionofasetofnodes.
Thedifferenceisthatitconsid-erstheduplicate-detectionscopeforanabstractedge,andthisrequiresincrementalnodeexpansion.
Asimpleandeffectiveheuristicistoapplyoperatorstonodesinorderofnblock,and,foreachnblock,inorderofoutgoingabstractedge.
Wenextconsidersomewaystoimproveperformance.
Toreducetheoverheadofoperatorgrouping,ourimplementa-tionusesalazyapproachinwhichoperatorgroupingforanabstractnodeisonlycomputedimmediatelybeforethersttimeanodethatmapstoitisexpanded.
Becausetherecouldbeanumberofabstractnodesthatdonothaveanynodesthatmaptothemduringsearch,thisapproachavoidstheover-headofoperatorgroupingfortheseabstractnodes.
Wehaveobservedthattheeffectivenessofthisapproachtendstoin-creasewiththesizeoftheabstractgraph.
Ourimplementationalsousesalazyapproachtoreadingnodesfromdisk.
Uponswitchingtoaduplicate-detectionscopethatconsistsofnodesstoredondisk,ourimplemen-tationdoesnotreadthesenodesfromdiskimmediately.
In-stead,itwaitsuntilthersttimeanodeisgenerated.
Thereasonforthisisthatwhenasingleoperatorgroupisusedtogeneratesuccessorsfornodesinannblock,itmaynotgener-ateanysuccessornode,if(a)thenodestowhichtheoperatorsinthegroupareapplicablehavenotyetbeengenerated,or(b)thegeneratedsuccessornodeshaveanf-costgreaterthananupperboundusedinbranch-and-boundsearch.
Thelazyap-proachavoidstheoverheadofreadingnodesfromdisk(inordertosetuptheduplicate-detectionscopeinRAM)ifnosuccessorsaregeneratedbyanoperatorgroupforannblock.
Aspreviouslydiscussed,SDDneedstodecidewhichnblockstomovefromRAMtodisk,whenRAMisfull.
Exceptforthenblocksthatmakeupthecurrentduplicate-detectionscope,anynblockscanpotentiallybeushedtodisk.
Butthismeansifannblockdoesnotincludeitselfaspartofitsownduplicate-detectionscope,itmaybeushedtodiskevenwhenitsnodesarebeingexpanded.
Whilethisisallowedinourimplementation,itshouldbeavoidedasmuchaspossibleforefciencyreasons.
Wemaketwosimplemod-icationstotheleast-recentlyusedalgorithmtoensurethis.
First,insteadofupdatingthetimestampofannblockeverytimeitisaccessed,itstimestampisonlyupdatedwhen(a)thecurrentduplicate-detectionscopechangesand(b)thenblockisthenexttobeexpandedorispartofthenewscope.
Thisalsosimpliesthemaintenanceoftheclock,whichneedsnoupdatesuntiltheduplicate-detectionscopechanges.
Thesecondmodicationisthatinsteadofmovingforwardtheclockbyoneclocktickwhentheduplicate-detectionscopechanges,ouralgorithmadvancesitbytwoclockticks.
Thenthetimestampoftheto-be-expandednblockissettooneclocktickearlierthanthenewclocktime.
Finally,thetimestampsofallthenblockswithinthenewduplicate-detectionscopeareupdatedtothenewclocktime.
Asaresult,ifthenblocktobeexpandednextdoesnotbelongtothenewduplicate-detectionscope,itisthelasttobeushedtodisk,sinceitstimestampismorerecentthananyotherushablenblockandearlierthananynon-ushablenblock,whichhasatimestampequaltothecurrentclocktime.
Finally,recallthatedgepartitioningexpandsnodesinasinglenblockmultipletimes,oneforeachoperatorgroup.
Thisaffectsthestrategywithwhichtoremovenodesstoredondiskforthecurrently-expandingnblock.
Whilethesim-pleststrategyistoremovethesenodesfromdiskassoonastheyareswappedintoRAM,itmayincurextraoverheadifthesenodesmustbewrittenbacktodiskshortlyafter,inor-dertomakeroomfornewly-generatednodes.
Notethatnodesinthecurrently-expandingnblockdonotchangeaslongastheoperatorgroupusedtogeneratethesuccessorsisnotas-sociatedwithanabstractedgewhosesourceanddestinationarethesame(i.
e.
,a"selfloop").
Becauseselfloopsareeasytodetect,ourimplementationpostponestheremovalofnodesstoredondiskforthecurrently-expandingnblockuntila"selfloop"operatorgroup,which(ifany)isalwaysthelastopera-torgroupappliedtoannblockinourimplementation,isusedtoexpandthenblock.
IJCAI-072413SDDSDD+EdgePartitioningProblemRAMDiskExpSecsRAMDiskIncremExpSecsdepots-72,662,2539,524,31416,801,412342742,98810,705,324191,263,008460blocks-163,194,7035,527,22718,075,7793871,069,9016,997,695395,738,702823trucks-97,085,62120,888,17354,348,8203,995953,64226,106,623590,454,3545,982storage-125,520,445230,451,662282,931,3349,141891,585221,072,5582,914,075,5029,071freecell-411,447,191114,224,688208,743,83014,7172,218,545122,033,8064,206,478,52722,960elevator-151,540,657126,194,100430,804,93316,48761,900127,685,64012,775,795,01560,229gripper-1013,736,629328,271,6322,007,116,25435,0521,069,901340,780,44013,366,646,79336,377logistics-95,159,767540,438,5861,138,753,91141,028742,988544,285,2379,856,519,13849,004driverlog-1349,533,8732,147,482,0932,766,380,501108,0514,299,8062,147,483,53538,879,000,039122,877satellite-712,839,146571,912,557838,488,709160,687429,971584,308,51628,532,162,097129,608trucks-10----7,085,621231,515,5026,282,870,88870,963depots-10----41,278,2281,373,427,38526,548,426,03890,644Table1:Comparisonofstructuredduplicatedetection(SDD)withandwithoutusingedgepartitioningonSTRIPSplanningproblems.
ColumnsshowpeaknumberofnodesstoredinRAM(RAM),peaknumberofnodesstoredondisk(Disk),numberoffullnodeexpansions(Exp),numberofincrementalnodeexpansions(IncremExp),andrunningtimeinCPUseconds(Secs).
A'-'symbolindicatesthatthealgorithmcannotsolvetheproblemwithin2GBofRAM.
5ComputationalresultsWeimplementedSDDwithedgepartitioninginadomain-independentSTRIPSplannerthatusesasitsunderlyingsearchalgorithmbreadth-rstheuristicsearch[ZhouandHansen,2006a].
Thereasonforusingbreadth-rstheuristicsearchisthatitusesinternalmemoryveryefciently.
Build-ingSDDwithedgepartitioningontopofitimprovestheover-allefciencyofsearchbylimitingtheneedtoaccessdisk.
Oursearchalgorithmusesregressionplanningtondop-timalsequentialplans.
Asanadmissibleheuristic,itusesthemax-pairheuristic[HaslumandGeffner,2000].
Wetestedourexternal-memorySTRIPSplannerintendifferentdo-mainsfromthebiennialplanningcompetition,includingtwodomains(trucksandstorage)fromthemostrecentcompeti-tion.
ExperimentswereperformedonanAMDOperton2.
4GHzprocessorwith4GBofRAMand1MBofL2cache.
Table1comparestheperformanceofSDDwithandwith-outedgepartitioning.
TheseproblemsareamongthelargestineachofthetenplanningdomainsthatSDDwithedgepar-titioningcansolvewithouteither(a)usingmorethan2GBofRAMor(b)takingmorethan2CPUdaysofrunningtime.
Twoproblems(trucks-10anddepots-10)canonlybesolvedwithintheselimitsusingedgepartitioning.
Forthesetwodo-mains,thetablealsoincludesthelargestinstancesthatcanbesolvedwithoutedgepartitioning.
BothversionsofSDDusethesamestate-spaceprojectionfunction.
Table1showsacoupleofinterestingthings.
First,itshowsthatedgepartitioningcanreducetheinternal-memoryre-quirementsofSDDbyanaveragefactorof11timesfortheseplanningproblems.
Indoingso,itonlyincreasesthepeaknumberofnodesstoredondiskbyabout7.
5%.
Second,itshowsthattheoverheadthatresultsfromusinganincremen-talapproachtoexpandingnodesisratherinexpensive.
Al-thoughonaveragethereare16.
8timesasmanyincrementalexpansionswhenedgepartitioningisusedastherearefullexpansionswhenitisnot,thisonlyincreasesrunningtimeby53%onaverage.
Notethattheextratimetakenbyedgepartitioningincludestimeforoperatorgrouping.
Indirectly,thetableshowsroughlyhowmuchinternalmemoryissavedbyusingSDDwithedgepartitioninginsteadofA*.
ThenumberoffullnodeexpansionsinSDDgivesanestimateofhowmanynodesA*wouldneedtostoreinordertosolvetheproblem,sinceA*hastostoreeverynodeitex-pands,andbreadth-rstheuristicsearch(withanoptimalup-perbound)expandsroughlythesamenumberofnodesasA*,disregardingties.
Basedonthenumberoffullnodeexpan-sionsshowninTable1,A*wouldneed,onaverage,atleast1,340timesmoreinternalmemorytosolvetheseproblemsthanbreadth-rstheuristicsearchwithSDDandedgeparti-tioning.
BecausethisestimateignoresthememoryneededbyA*tostoretheOpenlist,whichisusuallylargerthantheClosedlist,itisactuallyaconsiderableunderestimate.
Astheresultsshow,SDDwithoutedgepartitioningisal-readyveryeffectiveinsolvingtheseSTRIPSplanningprob-lems,whichindicatesthatthesesearchproblemscontainagreatdealofthekindoflocalstructurethatSDDexploits.
Thismeansthattheseproblemsactuallypresentaseriouschallengeforedgepartitioning,whichmustidentifyaddi-tionalstructurethatcanbeexploitedtoreduceinternalmem-oryrequirementsevenfurther.
ForsearchproblemsforwhichSDDwithoutedgepartitioningislesseffective,SDDwithedgepartitioningislikelytoreduceinternalmemoryrequire-mentsbyamuchlargerratio.
SinceedgepartitioningiseffectiveevenwhentheabstractgraphusedbySDDdoesnotcaptureanylocalstructure,onemightwonderwhethersuchlocalstructureisusefulanymore.
Althoughitisnolongerneededtoreduceinternalmemoryre-quirements,itisstillusefulinreducingtimecomplexity.
Firstofall,ifaproblemcanbesolvedbySDDwithoutedgeparti-tioning,thetimeoverheadofincrementalnodeexpansioncanbeavoided.
Ifedgepartitioningisused,thenthemorelocalstructure(i.
e.
,thefewersuccessornodesofanabstractnodeintheabstractgraph),thefewerincrementalexpansionsareneededbeforeanodeisfullyexpanded,andtheoverheadofincrementalnodeexpansionisreduced.
TheresultsinTable1showthatedgepartitioningreducestheamountofinternalmemoryneededinexchangeforanincreaseinaveragerun-ningtime,althoughtheactualincreaseisstillfairlymodest.
IJCAI-0724146ApplicationtodelayedduplicatedetectionSofar,wehavedescribedhowtouseedgepartitioninginSDD,whereitimprovesscalabilitybyreducinginternal-memoryrequirements.
Inparticular,itreducestheproportionofgeneratednodesthatneedtobestoredininternalmemoryatanyonetimeinordertoensuredetectionofallduplicates.
Aswenowshow,edgepartitioningcanalsobeusedinaformofdelayedduplicatedetection(DDD)thatuseslocalstructuretoreducethedelaybetweengenerationofnodesandeventualdetectionandremovalofduplicates.
ThishastheadvantageofreducingthediskstoragerequirementsofDDD.
WebeginwithareviewofDDDandthendescribehowedgepartition-ingcanenhanceitsperformance.
6.
1DelayedduplicatedetectionDDDalternatesbetweentwophases;successorgenerationandduplicateelimination.
Dependingonhowduplicatesareeliminated,therearetwoformsofDDD,asfollows.
Sorting-basedDDDTherstalgorithmsforexternal-memorygraphsearchusedsorting-basedDDD[SternandDill,1998;MunagalaandRanade,1999;Korf,2004;Edelkampetal.
,2004].
Sorting-basedDDDtakesaleofnodesonthesearchfrontier,(e.
g.
,thenodesinthefrontierlayerofabreadth-rstsearchgraph),generatestheirsuccessorsandwritesthemtoanotherlewithoutcheckingforduplicates,sortstheleofgeneratednodesbythestaterepresentationsothatallduplicatenodesareadjacenttoeachother,andscanstheletoremovedu-plicates.
TheI/OcomplexityofthisapproachisdominatedbytheI/Ocomplexityofexternalsorting,andexperimentsconrmthatexternalsortingisitsmostexpensivestep.
Hash-basedDDDHash-basedDDD[KorfandSchultze,2005]isamoreef-cientformofDDD.
ToavoidtheI/Ocomplexityofexter-nalsortinginDDD,itusestwoorthogonalhashfunctions.
Duringnodeexpansion,successornodesarewrittentodiffer-entlesbasedonthevalueofthersthashfunction,whichmeansallduplicatesaremappedtothesamele.
Oncealeofsuccessornodeshasbeenfullygenerated,duplicatescanberemovedfromit.
Toavoidtheoverheadofexternalsortinginremovingduplicates,asecondhashfunctionmapsallduplicatestothesamelocationofahashtable,whichac-complishesbyhashingwhatotherwisewouldrequiresorting.
Sincethehashtablecorrespondingtothesecondhashfunc-tionmusttininternalmemory,hash-basedDDDhasamin-imuminternal-memoryrequirementthatcorrespondstothelargestsetofuniquenodesinanyle.
Thus,thisapproachre-quiressomecareindesigningthersthashfunctiontomakesureitdoesnotmaptoomanyuniquenodestoasinglele.
Althoughhash-basedDDDinitsoriginalformdoesnotdependon,orleverage,thestructureofagraph,animpor-tantimprovement,called"interleavingexpansionandmerg-ing"[KorfandSchultze,2005],does.
Itworksasfollows.
Thenodesonthesearchfrontierarestoredinmultipleles,called"parentles,"dependingonthersthashfunction,andthesuccessornodesthataregeneratedwhenthenodesintheparentlesareexpandedarealsostoredinmultipleles,called"childles.
"Insteadofwaitinguntilallparentlesatagivendepthareexpandedbeforemerginganychildlesatthenextdepthtoremoveduplicates,achildleismergedassoonasallparentlesthatcouldpossiblyaddsuccessornodestoithavebeenexpanded.
Inotherwords,interleav-ingexpansionandmergingmakesitpossibletoremovedu-plicatesearly.
BecauseDDDgeneratesduplicatesandstoresthemondiskbeforeeventuallyremovingthem,thetechniqueof"interleavingexpansionandmerging"reducestheamountofextradiskstorageneededbyDDD.
Infact,inthebestcase,itcanreducetheamountofextradiskstorageneedbyDDDbyafactorofb,wherebistheaveragebranchingfactor,al-thoughtheactualreductionmaybeless.
Toallow"interleavingexpansionandmerging,"thersthashfunctionmustbedesignedinsuchawaythatitcap-tureslocalstructureinthesearchgraph.
Inparticular,achildlemustonlycontainsuccessornodesgeneratedfromasmallnumberofparentles.
Agenerichashfunctioncannotbeusedforthissinceitwilltypicallyhashnodesuniformlyacrossallles.
Instead,aproblem-specichashfunctionthatcaptureslocalstructuremustbedesigned.
Inthefollowing,weexplainhowthisenhancementofhash-basedDDDex-ploitsand,thus,dependsonthelocalstructureofagraph,andhowitcanfurtherexploitedgepartitioning.
6.
2EdgepartitioninginDDDToseehowedgepartitioningcanbeusedtoimprovetheper-formanceofhash-basedDDD,werstconsiderhowthekindoflocalstructureexploitedby"interleavingexpansionandmerging"isrelatedtothekindoflocalstructureexploitedbySDD.
Aspreviouslypointedout,hash-basedDDDrequiresaproblem-specichashfunction,andthe"interleavingexpan-sionandmerging"techniqueisonlyeffectivewhenthishashfunctionmapsnodestolesinsuchawaythatthenodesinonele(thechildle)aregeneratedfromnodesinonlyasmallnumberofotherles(itsparentles).
Infact,theserelationshipscanberepresentedbyanabstractstate-spacegraphinwhichabstractnodescorrespondtoles,andanab-stractedgeispresentwhennodesinonelehavesuccessornodesintheotherle.
Thisshouldmakeitclearthatthersthashfunctionusedbyhash-basedDDDisactuallyastate-spaceprojectionfunction,and,for"interleavingexpansionandmerging"tobeeffective,thishashfunctionshouldcap-turethesamekindoflocalstructurethatisexploitedbySDD.
Thefollowingconceptwillhelpmakethismoreprecise.
Denition2Thepredecessor-expansionscopeofachildleforanabstractnodeyunderastate-spaceprojectionfunc-tionΠcorrespondstotheunionofnodesintheparentlesforabstractnodesy∈predecessors(y),thatis,y∈predecessors(y)Π1(y),wherepredecessors(y)isthesetofpredecessorsofyintheabstractgraph,andΠ1(y)isthesetofnodesintheparentleforanabstractnodey.
Animportantpropertyofthepredecessor-expansionscopeisthatitisguaranteedtocontainallstoredpredecessorsofnodesinachildle,whichleadstothefollowingtheorem.
IJCAI-072415Theorem2Mergingduplicatenodesafterexpandingallnodesinthepredecessor-expansionscopeofachildleisguaranteedtoeliminateallduplicatesthatcouldbegener-atedforthechildle.
Theconceptofpredecessor-expansionscopeletsusiden-tifythelocalgraphstructureneededby"interleavingexpan-sionandmerging"inaprincipledway,andrelateittothekindoflocalstructureexploitedbySDD.
Forundirectedgraphs,theyareexactlythesame,sincethesetofpredecessorsofanabstractnodealwayscoincideswiththesetofitssuccessors.
Fordirectedgraphs,theymayormaynotbethesame.
Thisanalysisalsoletsusspecifyaconditionunderwhich"interleavingexpansionandmerging"willnotbeeffective,atleastbyitself.
Whentheabstractgraphisfullyconnected,thepredecessor-expansionscopeofanychildleistheentiresetofparentles.
Thismeanstheearliesttimeachildlecanbemergediswhenallnodesatthecurrentdepthhavebeenexpanded,whichpreventstheapplicationofinterleavingexpansionandmerging.
Wearenowreadytoshowhowedgepartitioningallows"interleavingofexpansionandmerging"tobeeffectiveeveninthiscase.
Theideaistoforcenodeswithinthepredecessor-expansionscopeofachildletogeneratesuccessorsonlyforthatchildlealone,withoutgeneratingsuccessornodesforotherchildlesatthesametime.
Thiscanbeachievedasfollows.
Letybetheabstractnodethatcorrespondstothechildlethatisthetargetofmerging.
Tomergeduplicatenodesinthisleasearlyaspossible,edgepartitioningonlyusesoperatorso∈Oy,ytogeneratethesuccessorsofnodesintheparentlesforabstractnodesy∈predecessors(y).
Onceallnodesintheparentleshavegeneratedtheirsuc-cessorsforthischildle,mergingcantakeplaceasusual.
Theadvantageofedgepartitioningisthatitsavesexternalmemorybynotgenerating(possiblyduplicate)successorsforanyotherchildlesbeforemergingisperformed.
Af-termergingduplicatesinachildle,edgepartitioningpicksanotherchildleasthenextmergingtarget,untilallthechildleshavebeenmerged.
Itcanbeshownthatbythetimethelastchildleismerged,edgepartitioningmusthaveusedalltheoperatorstogenerateallthesuccessornodesforthecur-rentdepth.
Bydoingsoinanincrementalway,itensuresthatthelocalstructureneededbythe"interleavingexpansionandmerging"techniqueisalwayspresent.
Althoughwedonotpresentempiricalresultsforedgepar-titioninginDDD,ouranalysishelpstoclarifytherelationshipbetweenSDDandhash-basedDDDwithinterleavingofex-pansionandmerging.
Bothexploitthesamelocalstructureofagraph,andthustheperformanceofbothcanbeenhancedbyusingedgepartitioninginasimilarway.
7ConclusionWehaveintroducedatechnique,callededgepartitioning,thatimprovesthescalabilityofstructuredapproachestoexternal-memorygraphsearchbyusingastrategyofincrementalnodeexpansiontolocalizememoryreferencesinduplicatedetec-tion.
Resultsshowthatitsignicantlyreducestheinter-nalmemoryrequirementsofstructuredduplicatedetection(SDD).
Moreover,itisguaranteedtobeeffectiveregardlessofthestructureofthegraph,andthisguaranteesthatSDDcanbeappliedtoanysearchproblem.
Finally,wehaveshownthatitcanalsobeusedtoreducetheamountofdiskstorageneededbydelayedduplicatedetection.
Thereareanumberofdirectionsforfuturework.
Onepos-sibilityistovarythedegreeofincrementalexpansion.
Forexample,insteadofusingoneoperatorgroupatatime,edgepartitioningcanusemultiple(butnotall)operatorgroupstogeneratesuccessornodesatatime.
Ifenoughinternalmem-oryisavailable,thiscanreducetheoverallnumberof(incre-mental)expansions.
Withedgepartitioning,wenowhavetwooptionstoreducetheinternal-memoryrequirementsofSDD.
Wecaneitherincreasethegranularityofthestate-spacepro-jectionfunction,orwecanuseedgepartitioning.
Whichop-tionisbetterunderwhatcircumstancesisaninterestingques-tion,andtheanswerislikelytohelpusunderstandhowtobesttradeoffinternal-memoryrequirementswiththenumberofdiskI/OoperationsneededbySDD.
References[Edelkampetal.
,2004]S.
Edelkamp,S.
Jabbar,andS.
Schr¨odl.
ExternalA*.
InProc.
ofthe27thGermanConf.
onArticialIntelligence,pages226–240,2004.
[HaslumandGeffner,2000]P.
HaslumandH.
Geffner.
Ad-missibleheuristicsforoptimalplanning.
InProc.
ofthe5thInternationalConferenceonAIPlanningandScheduling,pages140–149,2000.
[KorfandSchultze,2005]R.
KorfandP.
Schultze.
Large-scaleparallelbreadth-rstsearch.
InProc.
ofthe20thNationalConferenceonArticialIntelligence(AAAI-05),pages1380–1385,2005.
[Korf,2004]R.
Korf.
Best-rstfrontiersearchwithdelayedduplicatedetection.
InProc.
ofthe19thNationalConf.
onArticialIntelligence(AAAI-04),pages650–657,2004.
[MunagalaandRanade,1999]K.
MunagalaandA.
Ranade.
I/O-complexityofgraphalgorithms.
InProc.
ofthe10thSymposiumondiscretealgorithms,pages687–694,1999.
[SternandDill,1998]U.
SternandD.
Dill.
Usingmagneticdiskinsteadofmainmemoryinthemur(phi)verier.
InProc.
ofthe10thInternationalConferenceonComputer-AidedVerication,pages172–183,1998.
[ZhouandHansen,2004]R.
ZhouandE.
Hansen.
Struc-turedduplicatedetectioninexternal-memorygraphsearch.
InProc.
ofthe19thNationalConferenceonAr-ticialIntelligence(AAAI-04),pages683–688,2004.
[ZhouandHansen,2005]R.
ZhouandE.
Hansen.
External-memorypatterndatabasesusingstructuredduplicatede-tection.
InProc.
ofthe20thNationalConferenceonArti-cialIntelligence(AAAI-05),pages1398–1405,2005.
[ZhouandHansen,2006a]R.
ZhouandE.
Hansen.
Breadth-rstheuristicsearch.
ArticialIntelligence,170(4-5):385–408,2006.
[ZhouandHansen,2006b]R.
ZhouandE.
Hansen.
Domain-independentstructuredduplicatedetection.
InProc.
ofthe21stNationalConferenceonArticialIntelligence(AAAI-06),pages1082–1087,2006.
IJCAI-072416