Abstract-Vi presenterar Graph-Clear: ett nytt problem med jakt-evasion på grafer som modellerar upptäckt av inkräktare i komplexa inomhusmiljöer av robotteam. Miljön representeras av en graf, och ett robotteam kan utföra svep och blockera åtgärder på hörn och kanter, respektive. En svep åtgärd upptäcker inkräktare i en vertex och representerar förmågan hos robotteamet att upptäcka inkräktare i regionen som är associerad med vertex. På liknande sätt hindrar en blockering inkräktare från att korsa en kant och representerar förmågan att upptäcka inkräktare när de rör sig mellan regioner. Båda åtgärderna kan kräva att flera robotar utförs. En strategi är en sekvens av block och sopa åtgärder för att upptäcka alla inkräktare. När instanser av Graph-Clear löses är målet att bestämma optimala strategier, dvs. strategier som använder minst antal robotar. Vi bevisar att för det allmänna fallet av grafer, problemet med beräkning av optimala strategier är NP-hård. Därefter, för specialfallet av träd, tillhandahåller vi en polynom-tidsalgoritm. Algoritmen ser till att alla clearade hörn bildar ett uppkopplat underträd under hela genomförandet av strategin, och vi visar att det producerar optimala strategier.
På senare tid presenterar REF en grafbaserad metod för att hantera problemet med förföljelse genom att agenter använder blockerande eller svepande åtgärder för att upptäcka alla inkräktare i miljön.
Pursuit-Evasion on Trees by Robot Teams
{'venue': 'IEEE Transactions on Robotics', 'journal': 'IEEE Transactions on Robotics', 'mag_field_of_study': ['Mathematics', 'Computer Science']}