Assumegraph

AGraphSearchAlgorithmforIndoorPursuit/EvasionPRELIMINARYVERSION!
!
!
AbstractWeformulatetheproblemofindoorpursuit/evasionintermsofsearchingagraphforamobiletarget.
Thenwepresentanalgorithmtosolvethegraphsearchproblem.
Ouralgorithmisbasedongreedyiterativecomputationofthesearchstatespace,canuse"extended"(acrossnodes)visibility,allowsforrecontaminationofthegraphandproducesinternalsearchschedules,i.
e.
schedulesinwhichthesearchersmoveonlyalongtheedgesofthegraph(no"teleporting"isused).
Thealgorithmisextensibleinseveralways,forexampleitcandealwith…niteand/orprobabilisticallymovingevaderspeed.
Weevaluatethealgorithmbyseveralexperiments.
1IntroductionInthispaperwepresentaformulationofpursuit/evasionasagraphsearchproblemandintroduceanalgorithmtosolvethisproblem.
Wewereintroducedtothepursuit/evasionprobleminthecontextof…eldrobotics,butboththeformulationandthealgorithmwepresenthavemoregeneralapplicability.
Inbroadtermspursuit/evasion(PE)involvesateamofKpursuerstryingtolocate/captureamobileevader.
Severalmorespeci…cvariationsoftheproblemcanbede…ned,dependingonthepropertiesofthepursuers,theevaderandtheenvironmentinwhichPEtakesplace,aswellasontheamountofinformationavailabletothepursuersandtotheevader,thetypeofsolutionsoughtandsoon.
InthispaperweareconcernedwiththefollowingversionofthePEproblem.
1.
Thepursuittakesplaceinanindoorenvironment(e.
g.
ahouse,anocebuilding)andtheevadercannotleavetheenvironment(i.
e.
noexitsareavailable).
2.
Theevaderisadversarial(i.
e.
wantstoavoidcapture),arbitrarilyfastandomniscient(i.
e.
itknowsthemapoftheenvironmentandthelocationsofthepursuers).
3.
Thepursuersknowthemapoftheenvironmentandthelocationsoftheirteammates.
Theydonotknowtheevader'spositionunlessitiswithintheirvisibilityregion(visibilityregionwillbede…nedpreciselyinSection2).
Inaddition,weexamineadiscretizedversionoftheproblembyintroducingthefollowingassump-tions.
1.
ThePEprocessevolvesindiscretetimet=1;2;3;:::andateverytimetmovementissequential,i.
e.
…rsttheevadermovesandthenonepursueratatime.
2.
Themapoftheenvironmentisdecomposedintoconvexcellsandeachcellisrepresentedasanodeofa…nitegraph;theedgesofthegraphcorrespondtotheconnectivityofcellsintheoriginalenvironment;itisassumedthatateverytimesteppursuersandevaderresideinthenodesofthegraph.
13.
Capturetakesplacewhentheevaderandatleastonepursuerresideinthesamenode.
Theaboveisafairlycompletede…nitionofthePEvariantwhichwestudyinthecurrentpaper(severaladditionaldetailswillbeprovidedinSection2).
Forthisproblemwepresentanalgorithmwhichcomputesaguaranteedsearchschedule,i.
e.
asequenceofpursuermoveswhichensuresthatatleastonepursuerwilleventuallybelocatedinthesamenodeastheevader,foreverypossiblesequenceofevadermoves.
Thisisachievedbyensuringthatthe"dirtyset"(thesetofnodeswhichmaycontaintheevader)decreasesprogressivelyuntilitreducestotheemptyset.
The…rststudiesofPEongraphsappearedin[33,30,31].
Thesewerefollowedby[21,29]whichplacedtheprobleminthecontextof"pure"graphtheoryandinitiatedavigorouslineofresearchwhichcontinuestothisday;forrecentreviewssee[1,].
Inthiscontexttheproblemisusuallydescribedas"graphsearch"butitshouldbedistinguishedfromboth(a)searchingagraphforanimmobiletargetand(b)pursuingavisiblemobileevader("cops-and-robbers"problems,e.
g.
[35,]).
Inaddition,graphsearchintheabovesenseischaracterizedbysomefeatureswhichdonotquite…troboticPE.
First,ingraphsearchtheevaderisusuallyassumedtoresideintheedgesofthegraph,notinthenodes.
Second,searchschedulesarenotnecessarilyinternal,i.
e.
apursuermayattimesmovebetweennon-adjacentnodeswithoutrespectingtheconnectivityofthegraph(thisiscalled"teleporting"andgenerallyisnotappropriateforroboticsproblems);onlyrecentlyhassomeresearchbeenpublishedthatconcentratesoninternalsearch[37,].
Third,mostgraphsearchalgorithmsdonotallowrecontamination,i.
e.
onceanodeiscleareditmustbeguardedsothattheevaderwillneverenteritagain;aswewillargueinSection5,thisassumptionistoorestrictive.
IndoorPEinroboticswasinitiatedbyLavalleandhiscollaborators[23,24,25]andfurtherstudiedbyseveralotherresearchers[34,,,15].
AveryextensiveexpositionofworkonPEappearsinthebook[26].
Whileroboticsresearchersmakeuseofthegraphrepresentation,apparentlytheyhavenotmademuchuseofthegraphtheoreticresearchmentionedinthepreviousparagraph.
Thepaperisorganizedasfollows:inSection2weformulatetheproblem;inSection3wepresentouralgorithm;in4wepresentexperimentstoevaluatethealgorithm;inSection5wediscussourresults;inSection6wepresentourconclusionsanddirectionsforfutureresearch.
2ProblemFormulationAsalreadymentionedwewillstudyPEinindoorenviroments.
Considerthemapofonesuchenviron-ment,illustratedinFig.
1.
a.
Thismapcanbereducedtoagraphbydiscretization.
ForexamplethemapofFig.
1acanbereducedtothegraphofFig.
1b.
RecallthatagraphG=(V;E)isfullydescribedby(a)thesetsofnodesVand(b)thesetofedgesEVV.
Wewilllabelnodesbyintegers,i.
e.
foragraphofNnodeswewilltakeV=f1;2;:::;Ng.
Wealsohave(usingthesetcardinalitynotationjj)thatjVj=N.
Themap-to-graphreductionise¤ectedby1.
decomposingthemapoftheenvironmentintoconvexcells(typically,butnotnecessarily,rectan-gles),2.
correspondinganodetoeachcell,3.
insertingedgesbetweennodeswhichcorrespondtoadjacentcells(andalsoanedgefromeachnodetoitself).
2(a)Anindoorenvironmentpartitionedintorectangularcells.
(b)Agraphobtainedbycorrespondingtheconvexcellsof1.
a.
tonodes.
Thegraphalsoincludesloops,i.
e.
edgesfromeachnodetoitself,whicharenotdisplayedforsimplicityofpresentation.
Thegraphreductionisnotunique,sincethecelldecompositionisnoteither.
Inotherwordsthesamemapcanbereducedtomorethanonegraph.
ForexamplethemapofFig.
1aisreproducedinFig.
2awithadi¤erentcelldecompositionandthecorrespondinggraphappearsinFig.
2b.
(a)ThesameenvironmentasinFig.
1.
a.
,partitionedintodi¤erentcells.
(b)Thecorrespondinggraph.
Comparewith1.
b.
Thegraphagainincludesnon-displayedloops.
GivenagraphG=(V;E)withNnodes,theneighborhoodofnoden2VisdenotedbyN(n)andde…nedbyN(n)=fm2V:(n;m)2Eg:TheNNadjacencymatrixAofthegraphisde…nedbyAnm=1i¤n2N(m);0else.
3Forexample,theadjacencymatricesofthegraphsinFig.
1bandFig.
2bare,respectively,A=2666641001001100011111011000101377775;C=2666666666641100100011000000001100000011110010011010000101100000111100000011377777777775:(1)Givenagraphobtainedfromamap,thevisibilityregionofnoden2VisdenotedbyV(n)andde…nedbyV(n)=fm2V:misvisiblefromng:Thecondition"misvisiblefromn"isevaluatedundertheassumptionof"straight-line-visibility"and,obviously,dependsonthemapandcelldecompositionfromwhichthegraphwasobtained.
Morespeci…cally,"misvisiblefromn"holdsi¤everypointofcellmisvisiblefromeverypointofcelln(understraightlinevisibility).
TheNNvisibilitymatrixBisde…nedbyBnm=1i¤n2V(m);0else.
Again,thevisibilitymatrixofagraphdependsonthemapandcelldecompositionfromwhichthegraphwasobtained.
Forexample,forthegraphsofFigs.
1band2bthevisibilitymatricesare,respectively,B=2666641000001000001000001000001377775;D=2666666666641000101001000000001000000001000010001010000001111000111100000111377777777775:(2)NotethatthevisibilitymatrixB(correspondingtoFig.
1)issimplytheidentitymatrix.
IntherestofthispaperwewillassumethatPEtakesplaceinagraphG=(V;E)withjVj=N,byateamofKpursuers.
Wewilldenotethepositionofthek-thpursuerattimetbyxk(t).
TheK-longvectorofpursuerpositionswillbedenotedbyx(t)=[x1(t)xK(t)],andittakesvaluesinthespaceof(pursuer)con…gurations,denotedbyX=f1;2;:::;NgK.
Ifanodemaycontaintheevader,thenodewillbecalleddirty,otherwiseclear(forexample,ifapursuerresidesinnoden,thennisaclearnode).
Anodenisclearedwhenvisitedbyapursuerorfallsinsidethepursuer'svisibilityregionandremainsclearaslongasthereisnofree(frompursuerinspection)pathfromittoadirtynode;hencetheclearsetismorethansimplytheunionofthepursuers'visibilityregions.
Ifatsometimeafreepathfromtheclearnodentoadirtynodembecomesavailable,thennisrecontaminated.
Thesetofalldirtynodes(resp.
clearnodes)isthedirtyset,denotedbyD(resp.
clearset,denotedbyC).
ObviouslyC[D=V,C\D=;.
Wewilloftendescribesetsbytheirindicatorvectors:ForexampletheindicatorvectorofDisd=[d1;d2;:::;dN],wheredn=1i¤n2D,0else;similarlycistheindicatorvectorofC.
Thelengthofdisjdj=PNn=1dn(notethatwehavejdj=jDj);similarlyforc.
4Sincetheevaderwasassumedadversarial,omniscientandarbitrarilyfast,itwillstayoutsidethepursuers'visibilityregionsforaslongaspossible.
Inotherwords,theevaderwillonlybecapturedwhenthedirtysetbecomesempty.
Hencewemustmovethepursuersinamannersuchthatthedirtysetisprogressively(butnotnecessarilymonotonically)reduced,untilitbecomestheemptysetwhichisequivalenttocaptureoftheevader.
Infactthestrategydescribedaboveisconcernedwiththedirtyset,notwiththeevaderperse,andcouldbeexecutedevenintheabsenceofanevader!
Wewillsometimescallthegradualreductionofthedirtysetsweepingthegraph.
WeassumethePEprocessevolvesindiscretetimet=1;2;:::.
Attimet,theessentialinformationavailabletoeachpursueriscontainedinthevectorz(t)=[x1(t)xK(t);d1(t)dN(t)];i.
e.
everypursuerknowsthelocationofitselfanditsteammatesandthepossiblelocationsoftheevader.
Wecallz(t)thestatevectorofthePEprocess(fromthepursuers'pointofview).
Foreveryt,z(t)takesvaluesinthestatespaceZ=XD,whereX=f1;:::;NgK(thesetofallpossiblecon…gurations)andD=f0;1gK(thesetofallpossibledirtysets).
Henceeveryelementz2Zcanbewrittenasz=(x;d),wherex2Xisacon…gurationvectorandd2Disadirtysetindicatorvector.
TheZelementsoftheformz=(x;0)aretheclearstates,i.
e.
theonesforwhichtheclearsetC=V.
SincethestatespaceZis…nitewecanalsovisualizethestateevolutionequationintermsofadirectedstatetransitiongraphS(thisisdi¤erentfromtheoriginalgraphG)wherethenodesarestatesz=(x;d)andthedirectededgesarestatetransitions.
Wewillalsousethecontrolvectoru(t)=[u1(t)uK(t)],withuk(t)denotingthenextmoveofthek-thpursuer,i.
e.
xk(t+1)=uk(t).
Thestateevolutionequationhastheformz(t+1)=F(z(t);u(t));(3)i.
e.
ityieldsthenextstatez(t+1)intermsofthepreviousstatez(t)andthecontrolu(t).
Themovementoftheevader1ismodeledbymax-minmatrixmultiplication,denotedbyandde…nedasfollows:forarbitrarymatricesP(withdimensionsLM)andQ(withdimensionsMN)thematrixR=PQisde…nedbyRln=maxm=1;2;:::;M[min(Plm;Qmn)]:Thei-thmax-minpowerofasquarematrixPisdenotedbyP[i]andde…nedbyP[i]=PP:::Pitimes:Supposeforamomentthatthepursuersareremovedfromthegraphandtheevadermoveswithunitspeed(i.
e.
itcrossesexactlyoneedgepertimestep).
Thenattimet+1theevadercanbelocatedinanynodewhichisadjacenttoanodeinwichtheevadercouldbelocatedattimet.
Mathematicallythisisexpressedbyd(t+1)=d(t)Q;(4)where,forthepursuer-freesituation,thetransitionmatrixQequalstheadjacencymatrixA.
IftheevaderhasspeedM(itcrossesMedgesinasingletimestep)theninsteadof(4)wehaved(t+1)=d(t)Q[M](5)1Moreprecisely:theevolutionofthedirtyset.
5ForthecaseofarbitrarilyfastevaderitsucestosetM=N,thenumberofnodesinthegraph.
Nowsupposeasinglepursuerisplacedatnoden.
Thepursuerblockscertainpathswhich,iftakenbytheevader,wouldresultincapture.
Inparticular,theevaderwillnotmoveintoanynodewhichfallsinthevisibilityregionofthepursuer,becauseitwouldbecapturedimmediatelyafteritsmove.
Similarly,theevaderwillnotmoveoutofanynodeinthevisibilityregion,becauseitwouldbecapturedimmediatelybeforethemove.
Thesefactscanbemodeledasfollows.
WeintroducethecapturematricesP(n)(withn=1;2;:::;N)whicharede…nedbyPij(n)=8graphofFig.
1b,withadjacencymatrixAofeq.
(1)andthevisibilitymatrixBofeq.
(2).
Typicalcapturematricesare,forexample,P(3)=2666641000001000000000001000001377775;P(4)=2666641000001000001000000000001377775:AssumeaPEwithanevaderofunitspeedandtwopursuers,startingatnodes2and3andmoving,respectively,tonodesu1(1)=3andu2(1)=4.
Thentheinitialstatevectorisx1(1)=2x2(1)=3d(1)=10011andthetransitionmatrixisQ=PT(4)PT(3)AP(3)P(4)whichisQ=2666641000001000001000000000001377775T2666641000001000000000001000001377775T2666641001001100011111011000101377775266664100000100000000000100000137777526666410000010000010000000000013777756hence…nallyQ=2666641000001000000000000000001377775:Thenwehavex1(2)=u1(1)=3,x2(2)=u2(1)=4andthenewdirtysetisd(2)=d(1)Q=100112666641000001000000000000000001377775=10001i.
e.
theclearnodesare3and4,becauseoccupiedbypursuers,and2,becauseitwaspreviouslyclearandthereisnofreepathfrom2tothedirtynodes1and5.
Nowsupposethenextmovesareu1(2)=4andu2(2)=1.
Thenwehavex1(3)=4,x2(3)=1,andthenewdirtysetisd(3)=d(2)Q=d(2)PT(5)PT(4)AP(4)P(5)=100012666640000001100011010000000101377775=00101:Nodes1and4areclear,becauseoccupiedbypursuers.
Node3isrecontaminated,becausethereisafreepathfrom3tothedirtynode5.
Node2isclearbecause,eventhoughthereisafreepathfrom5to2,ithaslengthtwoandwehaveassumedinthisexamplethattheevaderhasunitspeed.
Thereadercancontinueinthismannertocomputedirtysetsafterapplicationofvariouscontrolsu(t),t=3;4;:::;weconcludetheexamplhere.
Wecompletetheproblemformulationbyintroducingacostfunctionwhichisnonnegativeandtakesthevaluezeroexactlywhentheevaderiscaptured(or,moreprecisely,whenitslocationisknownwithcertainty).
Thecostfunctionissimplythecardinalityofthedirtyset:J(t)=jd(t)j:(7)Indeed,ifJ(t)=0thenthedirtysethassize0,i.
e.
itisemptyor,inotherwords,theevaderhasbeendiscovered.
In(7)wehavewrittenJasafunctionoftime.
ActuallyitismorerelevanttowriteJasafunctionofthecontrolsu(1)u(t):asthepursuersapplyasearchschedule(describedbyu(1)u(t))thesizeofthedirtysetchanges,soattimet(aftertheentirecontrolsequencehasbeenapplied)wehaveJ(u(1)u(t))=jd(t)jandthisistheformwewilluseinwhatfollows.
Nowwearereadytopresentanalgorithmwhichwillselectu(1)u(t)soastominimizeJ(u(1)u(t)).
3TheAlgorithmWepresentoursearchalgorithminthreesteps:apreliminaryversionofthealgorithmispresentedinSection3.
1,animprovedversioninSection3.
2andsomeheuristicsforfurtherimprovementarediscussedinSection3.
3.
73.
1SearchAlgo:aPreliminaryVersionInthestatetransitiongraphSofthePEprocess,supposethatthepursuersstartataninitialnodezin=(xin;din).
Wewanttomovethepursuersthroughnodesz=(x;d)(andalongedgesofS)inamannersuchthatthe1'sinthedpartprogressivelydecrease(thedirtysetshrinks)untileventuallywereachoneoftheclearstates,sayzfin=xfin;dfin,wheredfin=0.
Tothisendwecould,theoretically,…ndapathfromzintosomezfin;indeedwecould…ndashortestpathusing,forexample,Dijkstra'salgorithm.
Notethatthisapproachdoesnottakeintoaccountanyspeci…cmovesoftheevader,itisaaworstcaseapproach,whichwecancallsweepingthegraphG.
Whilethisapproachsolvesthegraphsearchprobleminprinciple,itiscomputationallyintractable:evenformoderatevaluesofNandKthestatespaceistoobig.
Forexample,withN=10andK=2wehavejZj=102210=102400and,sinceDijkstra'salgorithmisquadratic()inthesizeofS,thesizeoftheproblemisprohibitive.
Toreducecomputationalburdenwewillresorttoapproximation.
Morespeci…cally,wewillusetwoapproximations.
1.
First,wewillprojectZtoasmallerset.
WecanprojectZtoeitherXorD.
LetusfornowconcentrateontheXprojection:itmapsseveralZelementstothesameXelement.
Thiscorrespondstothefactthatthesamepursuercon…gurationcanresultinmanydi¤erentdirtysets,dependingonthehistoryofhowthepursuersreachedthatparticularcon…guration.
2.
Bytheaboveprojectionthestatespaceisreducedtoasmallerset,butstillnotsucientlysmalltomaketheproblemcomputationallytractablebyanexactshortestpathalgorithm.
Soweuseasecondapproximation:toeachelementx2Xweassignacost,namelythesizeoftheleastknowndirtysetassociatedwithx.
By"leastknown"wemeanthatwewillgraduallyexploremoreandmorepathsterminatingatagivenpursuercon…gurationxandwillalwaysstoretheleastresultingcost(alongwiththepathyieldingthiscost).
Aswillbeseen,thiscomputationwillbeperformediteratively,updatingleastcostforagivencon…gurationintermsofpreviouslycomputedpathsanddirtysetsofothercon…gurations.
Weillustratetheaboveideasbypresentinginpseudocodeapreliminaryversionofouralgorithm.
Inthefollowingpresentationweassumetwopursuers,K=2,butextensiontootherKvaluesisobvious.
Foreverycon…guration(n1;n2)thealgorithmcomputesavectorofoptimalpathsp(n1;n2),anoptimaldirtysetvectord(n1;n2)(theoneobtainedbyfollowingp(n1;n2))andanassociatedoptimalcostv(n1;n2).
We…rstpresentthealgorithminpseudocodeandthencommentonitsvariousaspects.
Weusethefollowingnotation:thepathvectorp(n1;n2)hastheform(i1i2:::iT;j1j2:::jT)wherei1i2:::iTisthepathofthe…rstpursuer,andj1j2:::jTisthepathofthesecondpursuer;wealsodenotethecomponentsofp(n1;n2)byp(n1;n2;1)=i1i2:::iTandp(n1;n2;2)=j1j2:::jT.
Also,thevalueassociatedwithcon…guration(n1;n2)isdenotedbyv(n1;n2).
Finally,foreverysetofnodesA,Ind(A)denotestheindicatorvectorofA.
Input:GraphG=(V;E);VisibilitymatrixB;Startingnodesi,jInitializationForn=1:NForm=1:Np(n;m)=()d(n;m)=V8v(n;m)=NNextnNextmp(i;j)=(i;j)d(i;j)=Ind(VV(i)V(j))v(i;j)=d(i;j)vBest=v(i;j)pBest=(i;j)MainWhilevBest>0Forn1=1:NForn2=1:NForm12N(n1)Form22N(n2)bp=(p(n1;n2;1)m1;p(n1;n2;1)m2)bd=F[n1;n2];d(n1;n2);[m1;m2]bv=bdIfbvgraphtobesearched(alongwithitsvisibilitymatrixB)andthenodesi;jwherethepursuersstart.
(b)Atinitializationeachpursuercon…guration(n;m)isassociatedwiththeemptypath,the"full"dirtyset(D=V)andthe"full"costN.
Theonlyexceptionisthe"starting"con…guration(i;j),whichisassociatedtopathvector(i;j),dirtysetVV(i)V(j)(i.
e.
allnodesoutsidethevisibilityregionsofnodesiandj)andthecorrespondingcostv(i;j).
AlsothebestcurrentcostvBestissettov(i;j).
9(c)Inthemainloopthealgorithm,foreverycon…guration(n1;n2)takesthecorrespondingpathp(n1;n2)=(i1:::it;j1:::jt)andexpandsit,i.
e.
examineseverypath(i1:::itm1;j1:::jtm2)wherem1isaneighborofit,m2isaneighborofjt.
Atline"bd=F[n1;n2];d(n1;n2);[m1;m2]"thestateevolutionfunctionofeq.
(3)(morepreciselyeq.
(6))isusedwithcontrolvectoru=[m1;m2]andpreviousstatevectorz(t)=[n1;n2];d(n1;n2)tocomputethenextdirtyset.
(d)Ifforsomepaththecostof(m1;m2)isreduced,thepath,dirtysetandcostof(m1;m2)isupdated.
Notethattheupdateconcernstheendingcon…guration(m1;m2),notthestartingone(n1;n2).
Henceinonepassoftheouterloopsonn1;n2thecostsofseveralcon…gurations(m1;m2)maygetupdated.
(e)Ifinthecourseoftheseupdatessomecon…guration(m1;m2)achieveszerocost,thealgo-rithmisterminated.
2.
Itcanbeeasilyunderstoodthatthisisagreedyalgorithmwhichcanbetrappedatsomelocalminimum.
Hencetermination(vBest=0)isnotguaranteed;thealgorithmmaygetstuckatsomepointwherenofurtherreductionofthecostispossible.
Ifthealgorithmterminates(makingthecostzeroandthedirtysetempty)wesaythatithasfoundaclearingpath.
3.
Wehavenotde…nedanyconceptofpathoptimalitysofar.
Wecould,forexample,de…neopti-malityintermsofpathlengthorinsomeotherway.
Butthereisnoguaranteethataclearingpathproducedbyouralgorithmisshortestoroptimalinanyotherway.
3.
2TheSearchAlgorithm:anImprovedVersionWenowpresentsomemodi…cationsofthepreviousalgorithmwhichresultinconsiderablereductionofcomputationalload.
3.
2.
1IndexingbyCon…gurationsvs.
DirtySetsWehavepresentedourbasicalgorithmintermsofgeneratingpursuercon…gurations(n1;:::;nK).
Howeverthereaderhasnoticedthatforeverysuchcon…gurationwealsostorethecorrespondingpathsanddirtysets.
Infact,westoretriples(x;d;p),i.
e.
con…gurations,dirtysetsandpaths.
Thecon…gurationsarespecialintwosenses:…rst,theyareusedtoindexthetriplesandsecond(asaconsequenceofthe…rst)atmostonetriplewithaparticularxisstored.
Wecanuseadi¤erentstrategy:toindexthestoredtriples(x;d;p)bytheirdirtysetsd;thenatanygiventimewestoreatmostone(thebest)triplewithagivendirtyset.
Whyindexbydirtysetsratherthancon…gurationsTheansweristhatindexingbydirtysetsrequireslessstorageandlesscomputationthanindexingbasedoncon…gurations.
Wecanseethisbyconsideringthetwocon…gurations(n1;n2)and(n2;n1);thesetwopairscorrespondtothesamePEsituation(onepursuerlocatedatn1andoneatn2)buttheyappearastwodi¤erentelementsofX;eachonewillbestoredseparately,acorrespondingbestpathwillbestoredforeachandexpandedandsoon.
Thisresultsinconsiderableduplicationofcomputation,especiallywhenwedealwithK>2pursuers(forexample,forK=3thesixcon…gurations(3,4,6),(3,6,4),(4,3,6),(4,6,3),(6,3,4),(6,4,3)correspondtothesamephysicalplacementofpursuers).
Ifweindexbydirtysetsitwillalwaysmakesensetoaddatriple(x;d;p)withdirtysetdnotpreviouslyseen.
Thiswillresultincontinuousincreaseofthesetoftriplestobeexpanded.
Buthowcanwecomparetwotriples(x;d;p)andbx;bd;bpwiththesamed=bdandretainonlyoneofthetwoInwhatsensewill(x;d;p)bebetterthanbx;bd;bpifevaluationisbeasedonjdj=bdTheanswer10liesinintroducinganadditionalcriterion,distanceofcon…gurationfromdirtyset.
Tounderstandthisconcept,…rstrecallthatdist(m;n),thedistanceofnodesm;ninagraph,isthelengthoftheshortestpathjoiningmandn.
Now,wede…nethedistancedist(U;W)betweensetsofnodesUandWtobethesumofdistancesbetweennodesofthetwosets:dist(U;W)=Xm2UXn2Wdist(m;n):RecallthatthedirtysetcorrespondingtodisDanddenotetheset(ofnodes)correspondingtothecon…gurationxbyX;usebXandbDforthecorrespondingsetsassociatedwithbxandbd.
Ournewcriterionisdescribedasfollows:1.
ifdist(X;D)>distbX;bDwereplace(x;d;p)bybx;bd;bp;2.
elseweretain(x;d;p)anddropbx;bd;bp.
Therationaleofthiscriterionisthat,betweentwocon…gurationswhichhavesamedirtyset,theoneinwhichthepursuersareclosertothedirtynodesissuperior;itcanbeseenasawaytoforcethepursuerstomoveclosertothedirtynodes.
3.
2.
2Parallelvs.
SerialSearchWehavepresentedthealgorithmofSection3.
1intermsoftwonestedloops"Forn1=1:N","Forn2=1:N".
Thefactthatthetwoloopsarenestedcorrespondstoparallelsearchofthecon…gurationspace(andthegraphG),i.
e.
thetwopursuersareassumedtomovesimultaneously.
Analternativeimplementationwouldbeserial:the…rstloopisexecutedandthenthesecond.
Thiscorrespondstosequentialsearch:…rstpursuerno.
1moveswhileno.
2remainsstationaryandthentheirrolesarereversed.
ThesamedistinctioncanbeappliedforthegeneralcasewithK2.
Parallelimplementation/nestedloopsiscomputationallymoreintensivethanserial.
ForKsearchersaroughestimateofthecomputationalcomplexityisON2KforparallelandOKN2forserialimplementation.
Tospeedupexecutiontime,ourimprovedalgorithmusesserialsearch2.
.
3.
2.
3TheModi…edAlgorithmIncorporatingserialcomputationandindexingbydirtysetsweobtainanewversionofoursweepingalgorithm.
Wegivehereapseudocodeversionfortwopursuers;generalizationtomorepursuersisstraightforward.
InthefollowingpseudocodethesetQwillbeusedtostorethedirtysets;x(d),p(d),v(d)willdenote,respectively,thecon…guration,pathandcostassociatedwithdirtysetd;x(d;1)andx(d;2)willdenotethelocationsofthe…rstandsecondpursuerstoredinx(d);p(d;1)andp(d;2)willdenotethepathsofthe…rstandsecondpursuerstoredinp(d).
FinallyD=Ind1(d)willdenotethedirtysetDwithindicatorvectord;similarlyforInd1(X)etc.
Input:GraphG=(V;E);VisibilitymatrixB;Startingnodesi,jInitialization2Forcompletenessletusmentionathirdmodeofsearch,whichwecancallserial/parallel.
ThisinvolvesbreakingdowntheKsearchersintoJgroupsofK1;K2;:::;KJsearchers;thej-thgroupisimplementedbyKjnestedloops,andtheJgroupsarerunserially.
Presumablythisgivesexecutiontimehalfwaybetweenserialandparallel.
11d=Ind(VV(i)V(j))Q=fdgx(d)=(i;j)p(d)=(i;j)v(d)=jdjpBest=pvBest=v(d)MainWhilevBest>0Ford2QD=Ind1(d)X=Ind1x(d)n1=x(d;1)n2=x(d;2)Form12N(n1)bx=(m1;n2)bX=Ind1(bx)bp=(p(d;1)m1;p(d;1)n2)bd=F(([n1;n2];d);[m1;n2])bD=Ind1bdbv=bdIfbd=2QQ=Q[nbdox(bd)=(m1;n2)p(bd)=bpv(bd)=bvElseIfdistbX;bDGraphAThe…rstexperimentinvolvestheenvironmentofFig.
,whichhasbeentakenfrom[Lavalle].
WealsoindicateinFig.
thediscretizationwewilluse.
InFig.
weplotthegraphcorrespondingtothediscretizationofFig.
.
Wehavealsoplacedtwopursuersatnode.
Dirtynodesareillustratedred.
WerunouralgorithmwithK=2,L0=,v0=and=.
Thealgorithmclearsthegraphinsteps;thepathusedis1144845666662697133111113145555514The…nalclearedgraphisplottedinFig.
Thefollowingremarks.
.
.
4.
3GraphB4.
4DiscussionTheresultsaregenerallygood.
Thepossibleexperimentsaredeterminedbythecombinationsof(graph,numberofpursuers,visibilitytype,searchmode,startingcon…g,algorithmparameters).
Therearetoomanycombinations,Ihavenotperformedallpossibleexperiments.
Ihavefocusedongraphs,C,H,P,NSHandmuseum.
1.
Withextendedvisibilityeverythingworks,butthisisnotasurprise,itworkedwiththeoldversionofT-algaswell.
2.
Withlocalvisibility,everyhtingusuallyworks.
ThebiggestissueasfarasIamconcernedisthedependenceofsearchsuccessoninitialcon…gurationofthepursuers.
I.
e.
Ihaveexperimentswhichareidenticalineveryrespectexceptinthestartingpositionofthepursuers;foronestartingcon…gthegraphclears,whilefortheotheritdoesn't.
3.
Ihavenotexperimentedwithextendedvisibility.
Theotherimportantissueistimetocompletion.
Forsomesearchmodes/parametervaluesthesolutionisfoundinafewseconds;forotheritcantakeseveral(orevenmany,>30)minutes.
OverallIgetthebestresultsfromTAlg11:serialsearchwiththeappropriatenumberofpursuers,PruneTol=0andActSize=10solveseverygraph:C(theonewiththecycles),HandPinnomorethan2or3seconds;NSHandmuseuminanythingbetween15and25seconds.
Ifeelfairlycon…dentthatT-algwouldworkinothersimilargraphs(arti…cialorextractedfromoorplans–infactIthinkbothNSHandmuseumaremuchharderthantheusualgraphs/oorplansusedbyauthorssuchasLaValle,Murrietaetc.
).
Notealsothatifonechoiceofsearchmode,K,PruneTol,ActSizeetc.
doesnotwork,wecanalwaystryadi¤erentcombination;allweneedissomecombinationthat…ndsaclearingsolution.
Thereisone…nalissue:thenatureofserialsearchissuchthatineverymoveonlyonepursuerchangesposition.
Thisresultsinlongclearingpaths,e.
g.
forthemuseumandNSHtheymaytake15around150steps.
Butthisdoesnotworrymemucheither;usually,insituationswhereonlyonepursuermovesatatime,wecanpostprocessandshortenthepath.
Forexampleconsiderthefollowingevolutionofcon…gurationstPurs.
1Purs.
2Purs.
3112523253345434654466456MyguessisthatwecancompressthistotPurs.
1Purs.
2Purs.
3112523463456andstillretainthegraphclearing.
Thisneedschecking,butIamverysureitcanbedone.
Letusmakeone…nalremark.
Ouralgorithmhasthreeparameters;v0;L0whichcanbetunedtoobtainvariousclearingschedules.
Graphsearchcanbeseenasapuzzle.
OneisagivenagraphtoclearandFinallyletusstressthatwecanplaywiththeparameters;v0;L0toobtainabettersolution.
PlayingwiththeparametersmaybeconsideredadhocbutitisperfectlyOKforthistypeofproblemwhichisessentiallyapuzzle.
.
.
Alsomanyalternativealgorithmscanbeusedinconjunction5DiscussionInthissectionwediscussthematerialoftheprevioussectionsincomparisontotheotherresearchers'workonindoorPE.
WedividePEworkintotwobroadcategories:workoriginatinginrobotics(suchas[Lavalle,Hollinger,Gerkey,Sarmiento,Isler])andwhatwecall,forlackofabettername,"puregraphtheoreticwork"(suchas[Megiddo,Kiroussis,Barriere]).
Notethatweonlydiscussworkconcerningdeterministic,guaranteedPE.
5.
1RoboticIndoorPEMostoftheworkinthiscategoryinvolvestwosteps:(a)conversionoftheindoorenvironmenttoagraphbydiscretizationand(b)developmentofagraphsearchalgorithm.
Inthediscretizationstepmostresearchers(Gerkey,Sarmiento,Hollinger)followanapproachsimilartoours:discretizationisbasedonanadhocdecompositionoftheenvironmentintorectangles.
AnotableexceptionisLavalle,whousesamuch…nerdiscretizationbasedoncriticalvisibilityevents.
NotehoweverthatouralgorithmcouldalsobeappliedinconjunctiontoLavalle'sdiscretizationor,forthatmatter,anyotherdiscretization.
Regardingsearch,themostpowerfulalgorithmweknowistheonebyHollinger[]whichactuallyoutperformsoursinseveralcases;forexampleHollinger'salgorithmcanclearthemuseumgraphofSectionusingthreesearchers.
HoweverHollinger'salgorithmdoesnotallowforrecontaminationandhencefailstoclearsomegraphswithminimumnumberofsearchers(seethenextsectionforadiscussionofsearchnumber),forexampleitcannotclearthegraphofSectionwith3searchers.
16Gerkey'salgorithmisbasedonlimited(lessthan3600)visibilityandhenceisnotdirectlycomparabletoours.
Lavalle'salgorithmis[]isaspecialcase.
Itsearchesaspecialdirectedgraphwhichrepresentstheinformationspace(similartoourSstategraph),ratherthanthegeometricenvironment.
Clearingtheindoorenvironmentcorrespondsto…ndingintheinformationgraphashortestpathtoaclearstate;thisisachievedusingDijkstra'salgorithm.
Thisapproachisviable(andgivesanexactsolution)forK=1searcherbutwhenK>1thentheproblemcanonlybesolvedbyvariousapproximations.
HencewebelieveouralgorithmisanattractivealternativetoLavalle'sandalsotothesimilarDidier'salgorithm[Didier].
Wewillnotdiscusshereanumberofalgorithmswhichconcernprobabilisticsearch(e.
g.
[Sarmiento,Didier,Isler]).
5.
2GraphTheoreticSearchAswewillpresentlyexplain,"graphtheoretic"searchdi¤ersfromtheroboticapproachinseveralimportantrespects.
Thebasiccharacteristicsofgraphtheoreticsearcharethefollowing.
1.
Ratherobviously,ingraphtheoreticsearchthediscretizationstepisomitted;onestartsdirectlywithagivengraphwhichmustbecleared.
2.
Thestandardversionofgraphtheoreticsearchisedgesearch,inwhichtheevaderisassumedtohideintheedgesofthegraph,notinthenodes3.
Strangely,avariantnamednodesearchalsoassumesthattheevaderhidesintheedges.
3.
Graphsearchcanbeinternal,wherethepursuersareassumedtomovealongtheedgesofthegraph,andnon-internal,wherethisconstraintisnotenforced(non-internalmovesarealsocalled"teleporting").
Graphtheoreticsearchisusuallynon-internal4.
4.
Finally,mostgraphtheoreticalgorithmsproducemonotonicsearches,i.
e.
thedirtysetalwaysdecreases.
Inotherwords,recontaminationisnotallowed.
Infactithasbeenproved[Lapaugh]thatrecontaminationdoesnothelpnon-internaledgesearch(forexampleitdoesnotdecreasethenumberofsearchersnecessarytoclearthegraph).
Butfortheproblemstudiedinthecurrentpaper,recontaminationdoeshelp(considertheexampleofSection).
Severalgraphtheoreticsearchalgorithmshavebeenpublished.
Someofthemareexactbutapplyonlytospeci…cclassesofgraphs;forexampletheonesin[Megiddo]and[Barriere]applytotrees.
Otheralgorithmsarebasedonpathdecompositions;see[Skodinis]forthede…nitionofpathdecompositionanditsrelationshiptothePE/graphsearchproblem.
Again,someofthepathdecompositionalgorithmsareeitherexact(usuallytheseareintractableforlargegraphs)orapproximate.
Apathdecompositionyieldsagraphsearchschedulewhichismonotonicandnon-internal(foranexception–whichhoweverappliesonlytotrees–see[Barrier]).
Inshort,fromthepointofviewofroboticPE,graphtheoreticsearchalgorithmssu¤erfromseverallimitations:theysearchedges(ratherthannodes)andproducemonotonicandnon-internalsearchchedules.
Inaddition,theycannothandlevariableevaderspeed(theyalwaysassumetheevaderisarbitrarilyfast)andassume"local"visibility,i.
e.
thepursueronlyseesthenodeinwhichitislocated.
Ouralgorithmsu¤ersnoneoftheabovelimitations,i.
e.
itsearchesnodesinaninternal,non-monotonicfashionandcanhandlevariableevaderspeedandnon-localvisibility.
3Therearehistoricalreasonsforthisapproach.
4Theevaderisstillassumedtomoveonlyalongedges.
17Aprominentconceptingraphtheoreticsearchisthesearchnumberofagraph,i.
e.
thesmallestnumberofsearchersrequiredtoclearthegraphforanyinitialcon…guration/dirtyset.
Butagraphpossessesmanysearchnumbers,dependingontheuseofmonotonic,connectedandinternalsearch.
ForexamplethesamegraphGhasa(plain)searchnumbers(G)andaconnectedmonotonesearchnumbercms(G)(andwehaves(G)cms(G),see[Barriere]).
Foragooddiscussiononthevarioussearchnumberssee[Barriere].
Thetypeofvisibility(localornonlocal)canalsoinuencethesearchnumberbutwearenotawareofanypaperstudyingthis.
Despitethedi¤erencesbetweengraphtheoreticsearchandroboticPE,webelievethetwo…eldscanpositivelyinuenceeachother.
ThestudyofgraphtheoreticsearchstartedwithanappliedPEproblem[Parsons];thecurrentgraphtheoreticsearchalgorithmscanbeusedasstartingpointsforthedevelopmentofroboticPEalgorithmsand,perhapsmostimportant,thetheoreticalissuesaddressedingraphtheoreticsearch(monotonicity,computationofsearchnumberetc.
)provideusefulguidelinesforthetheoreticalanalysisofroboticPE,anareawhichhasnotbeensucientlystudiedyet.
Inthereversedirection,roboticPEcanprovidemotivationforthestudyof(true)nodesearchbygraphtheoreticmethodsandperhapsroboticnodesearchalgorithms(suchastheonepresentedinthecurrentpaper)canbemodi…edtoperformedgesearch,aproblemwhich,despitemuchgraphtheoreticwork,stillremainsratheropen.
6ConclusionWehavepresentedanapproachtoroboticindoorPEwhichisbasedon(a)conversionoftheindoorenvironmenttoagraphand(b)searchofthegraphbyagreedyiterativealgorithm.
Thealgorithmsearchesthegraphnodesinaninternal,non-monotonicfashionandcanhandlerecontamination,vari-ableevaderspeedandnon-localvisibility.
Whilethealgorithmisnotguaranteedtoalways…ndasolution,ithasdonesoinalltheexampleproblemswehavepresented,includingsomequitecom-plexones.
Thealgorithmcanbeeasilymodi…edinseveralwayswhicharethesubjectofourongoingresearch.
Henceweconcludethispaperbylistingsomefutureresearchdirections.
1.
AsdiscussedinSection4,sometimesthesearchscheduleobtainedbythealgorithmcanbeimproved(and,especially,shortened)inanobviousway.
Itwillbenicetoaugmentthealgorithmsothat,aftersomeclearingscheduleisfound,thisisshortenedandotherwiseimprovedbysystematicpost-processing.
2.
Onarelatednote,thesearchforshortestlengthschedulesisofobviousimportance.
Thismaybeachievedbythepost-processingmentionedinthepreviousparagraph,oritmayrequireacompletelynewapproach.
3.
Anothermodi…cationofthealgorithmistointroducesomekindofdynamicadjustmentoftheparameters;v0;L0.
Forexample,tocontrolthesizeofthedirtysetlist,wecouldstartwithsmallvaluesofv0;L0andincreasethemincasethealgorithmgetsstuck.
Awaytocontroltherandomcomponentofthesearchbydynamicallyadjustingthevalueisalsoofinterest.
4.
Inthecurrentpaperwehavetreateddiscretizationinanadhocmanner,usinghand-crafteddiscretizations.
Optimalor,atanyrate,systematicdiscretizationoftheoorplanisatopicofgreatinterest,sinceappropriatediscretizationcanreducethenumberofpursuersnecessarytoclearthegraph.
Alternatively,anapplicationthatwouldallowtheusertointeractivelydiscretizeaoorplanwouldalsobeuseful.
185.
Averyimportanttopicistheusestationarypursuers,alsoknownasguards.
Theycanbeusedtodecomposethegraphintosmaller,easiertosearchgraphs,ortoconvertthegraphtoatree(forwhichecientsearchalgorithmsareknown–weareindebtedtoGeo¤Hollingerforthisidea).
AprincipledwaytoassigntheroleofguardstoK2outofKevadersisatopicworthyoffurtherresearch.
6.
Itiseasytomodifytheproblemformulationtohandleedgesearch(thisisdonebyintroducing"auxiliary"nodes,correspondingtoedges).
Itwillbeinterestingtoapplyouralgorithmtoedgesearch.
7.
Inarelatedvein,wehaveremarkedthat,ingraphtheoreticsearch,clearingschedulescanbeob-tainedusingtheconceptofpathdecomposition.
Infactanypathdecompositionyieldsamonotonesearchscheduleandconverselyanymonotonesearchscheduleyieldsapathdecomposition[].
Now,consideranonmonotonesearchschedule(suchastheonesobtainedbyouralgorithm).
Thiswillalsoinduceadecompositionofthegraphbutthis(becauseofnonmonotonicity)willnotsatisfyallthepropertiesofa"true"pathdecomposition.
Whatarethepropertiesofsucha"nonmonotonic"decomposition8.
Itisalsoeasytomodifythestateevolutionequationandthecostfunctiontomodelprobabilisticmovementoftheevader(seeAppendix).
ItwillbeinterestingtoapplyouralgorithmtotheprobabilisticversionofthePEproblem.
9.
Finally,wewanttomodifyouralgorithmtohandleunknownorpartiallyknownenvironments.
AAppendixA.
1TheProbabilisticCaseJ2issimilartoJ1,isagainrelatedtothedeterministiccase,andisde…nedbyJ2(u1u2:::uT)=logjdTjJ2is(likeJ1)anincreasingfunctionofthedirtysetcardinality;Iuseitbecauseitcanbeinterpretedasentropy,ifweassumethethattheevaderisequiprobablyinanyofthedirtynodes.
I.
e.
ifthedirtysetattimetisdtthentheevadercanbeinanyoneofthedirtynodes(nsuchthatdt;n=1)withprobability1jdtj.
ThentheentropyoftheevaderprobabilitydistributionisjdTjXi=11jdTjlog1jdTj=logjdTj=J2:Finally,fortheprobabilisticcaseweuseJ3(u1u2:::uT)=NXi=1pT;ilogpT;i:SincepTisatrueprobabilitydistributiononthenodes,J3isatrueentropy.
A.
2SimilaritiesandDi¤erencestoEdgeSearchApplytoedgesearch/generalizepathwidth.
.
.
AboutPathwidth19References[1]B.
Alspach.
"Searchingandsweepinggraphs:abriefsurvey".
LeMatematiche.
[2]LBarriere;PFlocchini;PFraigniaud;NSantoro;CaptureofanintruderbymobileagentsProceedingsofthefourteenthannualACMsymposiumon.
.
.
2002[3]Barriere,Lali;Fraigniaud,Pierre;Santoro,Nicola;Thilikos,DimitriosM.
;Searchingisnotjumping.
Graph-theoreticconceptsincomputerscience,LectureNotesinComput.
Sci.
288034–452003[4]LBarriere;PFraigniaud;NSantoro;DMThilikos;SearchingisnotJumping29thWorkshoponGraphTheoreticConceptsinComputer.
.
.
2003[5]Barriere;ConnectedandInternalGraphSearchingTechReportTR-03-692003[6]HLBodlaender.
"ATouristGuidethroughTreewidth".
ActaCybernetica,1993[7]HansL.
Bodlaender;EcientandConstructiveAlgorithmsforthePathwidthandTreewidthofGraphs*JOURNALOFALGORITHMS21358-4021996[8]NickD.
Dendris;LefterisM.
Kirousis;DimitriosM.
Thilikos;Fugitive-searchgamesongraphsandrelatedparametersTheoreticalComputerScience172233-2541997[9]FVFomin,DMThilikos.
"Anannotatedbibliographyonguaranteedgraphsearching".
http://www.
ii.
uib.
no/~fomin/fedor/articles1/abgs.
pdf[10]PierreFraigniaud;NicolasNisse;ConnectedTreewidthandConnectedGraphSearching2006[11]GerkeyThrunBrianP.
Gerkey;SebastianThrun;Geo¤Gordon;Visibility-basedpursuit-evasionwithlimited…eldofviewProc.
oftheNatl.
Conf.
onArti…cialIntelligence(AAAI2004)20-272004[12]BrianP.
Gerkey;SebastianThrun;Geo¤Gordon;Parallelstochastichill-climbingwithsmallteamsinMulti-RobotSystems:FromSwarmstoIntelligentAutomataIII65-772005[13]BrianP.
Gerkey;SebastianThrun;Geo¤Gordon.
;Visibility-basedpursuit-evasionwithlimited…eldofviewIntl.
JournalofRoboticsResearch25299-3162006[14]Hahn,GenaandMacGillivray,Gary.
"Anoteonk-cop,l-robbergamesongraphs".
DiscreteMath.
vol.
306,pp.
2492–2497,2006.
[15]Hollinger[16]V.
Isler;S.
Kannan;S.
Khanna;LocatingandCapturinganEvaderinaPolygo-nalEnvironmentSixthInternationalWorkshopontheAlgorithmicFoundationsofRobotics2004[17]VIsler;SKannan;SKhanna;Randomizedpursuit-evasionwithlimitedvisibilityPro-ceedingsofthe…fteenthannualACM-SIAMsymposiumon.
.
.
200420[18]V.
Isler;S.
Kannan;S.
Khanna;RandomizedPursuit-EvasioninaPolygonalEnvironmentIEEETransactionsonRobotics5864–8752005[19]V.
Isler;S.
Kannan;S.
Khanna;RandomizedPursuit-EvasionwithLocalVisibilitySIAMJournalonDiscreteMathematics126–412006[20]VIsler;DSun;SSastry;RoadmapBasedPursuit-EvasionandCollisionAvoidanceProc.
Robotics,Systems,&Science2005[21]Kirousis,LefterisM.
;Papadimitriou,ChristosH.
;SearchingandpebblingTheoret.
Comput.
Sci.
47205–2181986[22]ASLaPaugh;RecontaminationdoesnothelptosearchagraphJournaloftheACM40224-2451993[23]S.
M.
LaValle;D.
Lin;L.
J.
Guibas;J.
-C.
Latombe;R.
Motwani;FindinganunpredictabletargetinaworkspacewithobstaclesProceedingsIEEEInternationalConferenceonRoboticsandAutomation737–7421997[24]L.
J.
Guibas;J.
-C.
Latombe;S.
M.
LaValle;D.
Lin;R.
Motwani.
;Visibility-basedpursuit-evasioninapolygonalenvironmentLectureNotesinComputerScience127217–301997[25]L.
J.
Guibas;J.
-C.
Latombe;S.
M.
LaValle;D.
Lin;R.
Motwani;Visibility-basedpursuit-evasioninapolygonalenvironmentInternationalJournalofComputationalGeometryandApplications9471–4941999[26]SMLaValle.
PlanningAlgorithms[27]N.
Megiddo,SLHakimi;MRGarey;DSJohnson;CHPapadimitriou;ThecomplexityofsearchingagraphJournaloftheACM3518-441988[28]Nowakowski,Richard;Winkler,Peter;Vertex-to-vertexpursuitinagraphDiscreteMath.
43235–2391983[29]MegiddoPapadimitriou[30]TDParsons.
"Pursuit-evasioninagraph".
Theor.
Appl.
Graphs,Proc.
1976.
[31]Parsons2[32]DamienPellier;HumbertFiorino;Coordinatedexplorationofunknownlabyrinthineenvi-ronmentsappliedtothePursuit-Evasionproblem.
AAMAS,pp.
895-902,2005.
[33]SpeleoFirst[34]A.
Sarmiento;R.
Murrieta;S.
A.
Hutchinson;AnEcientStrategyforRapidlyFindinganObjectinaPolygonalWorld[35]RNowakowski,PWinkler.
"Vertextovertexpursuitinagraph".
DiscreteMathematics,1983[36]KonstantinSkodinis;Constructionoflineartree-layoutswhichareoptimalwithrespecttovertexseparationinlineartimeJournalofAlgorithms4740–592003[37]Thilikospaper21