The Role of Information in the Cop-Robber Game Abs

TheRoleofInformationintheCop-RobberGameVolkanIslera,∗,NikhilKarnadbaDepartmentofComputerScience,RensselaerPolytechnicInstitute1108thStreet,Troy,NY–12180bDepartmentofComputerScience,RensselaerPolytechnicInstitute1108thStreet,Troy,NY–12180AbstractWeinvestigatetheroleoftheinformationavailabletotheplayersontheoutcomeofthecopsandrobbersgame.Thisgametakesplaceonagraphandplayersmovealongtheedgesinturns.Thecopswinthegameiftheycanmoveontotherobber’svertex.Inthestandardformulation,itisassumedthattheplayerscan“see”eachotheratalltimes.AgraphGiscalledcop-winifasinglecopcancapturetherobberonG.Westudytheeffectofreducingthecop’svisibility.Onthepositiveside,withasimpleargument,weshowthatacopwithsmallornovisibilitycancapturetherobberonanycop-wingraph(eveniftherobberstillhasglobalvisibility).Onthenegativeside,weshowthatthereductionincop’svisibilitycanresultinanexponentialincreaseinthecapturetime.Finally,westarttheinvestigationofthevariantwherethevisibilitypowersofthetwoplayersaresymmetric.Weshowthatthecopcanestablisheyecontactwiththerobberonanygraphandpresentasufficientconditionforcapture.Inestablishingthiscondition,wepresentacharacterizationofgraphsonwhichanaturalgreedypursuitstrategysufficesforcapturingtherobber.Keywords:pursuitevasiongames,limitedvisibility,greedystrategy1IntroductionASensorActuatorNetwork(SAN)isanetworkofdevicesequippedwithsens-ing,communication,actuation(e.g.mobility)andcomputationcapabilities.∗Correspondingauthor.Phone:[phone]Fax:[phone]Emailaddresses:[e-mail](VolkanIsler),[e-mail](NikhilKarnad).PreprintsubmittedtoTheoreticalComputerScience29January2008SANsarebecominganinseparablecomponentofautomationsystems.Theyareutilizedinawiderangeofautomationtaskssuchassurveillance,qualityinspection,search-and-rescueandenvironmentalmonitoring.Inapursuit-evasiongame,oneormorepursuerstrytocaptureanevaderwho,inturn,triestoavoidcapture.NumerousSANapplicationssuchassearch-and-rescue,surveillanceandtracking,canbemodeledaspursuit-evasiongames.Forexample,tracking,whichisperhapstheprimaryuseofaSAN,canbemodeledasapursuit-evasiongamewheretheobjectbeingtrackedistryingtoevadebymovinginawaythatpreventstheSANfromobservingit.TherearetwoprimaryadvantagesinmodelingSANautomationtasksaspursuit-evasiongames.First,inmostcases,theautomationsystemworksagainstanadversary.Thegame-theoreticformulationnaturallycapturestheadversarialnatureofthetask.Forexample,surveillancerobotsmustplantrajectoriestodetectburglarswhowill,inturn,developstrategiestoavoidbeingdetected.Second,pursuit-evasionstrategiesproviderobust,worst-caseguaranteesinscenarioswheretheplayersarenotnecessarilyadversarial.Forexample,asearch-and-rescueteammayutilizeapursuitstrategytofindalosthiker.Inthiscase,eventhoughthehikerisnotadversarial,ifapursuitstrategyexists,itguaranteesthats/hewillberescuedregardlessofhisorheractions.Suchsolutionsareespeciallyvaluablewheninteractingwithsystemsforwhichagoodbehavioralmodelisnotavailable(e.g.humans).Mostpursuit-evasiongamesarewellstudied.However,solvinggamesthatmodelSANapplicationsrequiresaddressingadditionalchallengeswhicharenotaddressedinstandardgameformulations.Consequently,therehasbeenrecentgrowinginterestinsolvingpursuit-evasionproblemswhichaddresscom-municationandsensingissues.Forexample,in[19]apursuit-evasiongamewhereateamofgroundandaerialvehiclestrytocaptureanevaderisstud-ied.Theauthorspresentadistributedsystemsarchitecture.Recently,Caoetal.studiedan“assetprotectiongame”whereasensornetworkteamguardsanarea[8].Theauthorsaddresscommunicationsissuessuchasdelayandpacketlosses.Inthispaper,weinvestigateanaspectofpursuit-evasiongamesthatiscrucialinSANapplications:theinformationavailabletothepursuer.Mostexistingpursuitstrategiesrequireperfectinformationaboutthestateofthegameatalltimes.Inotherwords,itisassumedthatthepursuershaveenoughsensingcapabilitiestoobservetheevader’sstateatalltimes.However,sinceSANsaretypicallymadeupofinexpensivecomponentswhichhavelimitedsensingcapabilities,solutionsobtainedforsuchmodelsarenotapplicabletoSANapplications.Inthepresentwork,weinvestigatetheroleoftheinformationavailableto2theplayersontheoutcomeofthecopsandrobbersgame.Theenvironmentinthisgameisrepresentedbyagraph.Playersmovealongtheedgesinturns.Thecopswinthegameiftheycanmoveontotherobber’svertex.Inaddi-tiontoobviousapplicationsinsurveillanceandsearch-and-rescue,variantsofthecops-and-robbersgamehavebeenusedtomodelvariousnetworksecurityproblems[9].Further,thestudyofthecopsandrobbersgameshedslightontographtheoreticpropertiessuchasvertexseparation[10]andtree-width[5].Inthispaper,wefocusonthegamewherethereisonlyasinglecop.Inthestandardformulation,itisassumedthattheplayerscanseeeachotheratalltimes.Here,westudytheeffectofreducingthepursuer’svisibility.Throughoutthepaper,weusetheterm“cop”interchangeablywith“pursuer”andtheterm“robber”interchangeablywith“evader”.2RelatedWorkInthecopsandrobbersgame,itiseasytoseethatiftherobberhasnovisibility(thatis,ifitcannotgatherinformationaboutthepositionofthecops),asinglecopcancapturetherobberonanygraphusingas