Ämnet för detta arbete är att patrullera en miljö med hjälp av ett team av autonoma agenter. Vi överväger både utformningen av open-loop banor med optimala egenskaper, och distribuerade kontrolllagar som konvergerar till optimala banor. Som prestandakriterier beaktas uppdateringstiden och latensen, dvs. tidsgapet mellan två besök i samma region och den tid som krävs för att informera varje agent om en händelse som inträffat i miljön. Vi associerar en graf med miljön, och vi studerar separat fallet med en kedja, träd, och cyklisk graf. När det gäller kedjegraf, beskriver vi först en minimal uppdateringstid och latens team bana, och vi föreslår en polynom tid algoritm för dess beräkning. Sedan beskriver vi en distribuerad procedur som styr robotarna mot en optimal bana. När det gäller trädgrafik utvecklas en polynomalgoritm för minsta uppdateringstid, under det tekniska antagandet att ett konstant antal robotar deltar i patrulleringsarbetet. Slutligen visar vi att utformningen av en minsta uppdateringstid bana för en cyklisk graf är NP-hård, och vi utvecklar en konstant faktor approximation algoritm. Den senaste tidens utveckling i autonomi och kapaciteten hos mobila robotar ökar avsevärt antalet applikationer som lämpar sig för ett team av autonoma agenter. Särskilt intresse har väckts för de uppgifter som kräver ett kontinuerligt genomförande, t.ex. övervakning av oljeutsläpp [1], upptäckt av skogsbränder [2], spår av gränsförändringar [3] och patrullering (övervakning) av en miljö [4]. Övervakningen av ett intresseområde kräver att robotarna kontinuerligt och upprepade gånger färdas i miljön, och det utmanande problemet består i att schemalägga robotarnas banor för att optimera vissa prestandakriterier. Läsaren bekant med nätverk plats, flera resande säljare, eller graf prospektering problem kan observera en nära anslutning till patrullering problem vi behandlar, t.ex., se [5], [6], [7]. Det är dock värt att notera att dessa klassiska optimeringsproblem inte fångar den repetitiva, och därmed dynamiska, aspekten av patrulleringsproblemet, eller de synkroniseringsproblem som uppstår när en tidpunkt bland besök i vissa zoner krävs. En exakt formulering av patrulleringsproblemet kräver karakterisering av robotarnas kapacitet, av miljön som ska patrulleras, och av prestandakriterierna. I detta arbete antar vi att robotarna är identiska och kapabla att känna och kommunicera inom ett visst rumsligt område, och att röra sig enligt en första ordningens integratordynamik med begränsad hastighet. Vi representerar miljön som en graf, där hörnen motsvarar fysiska och strategiskt viktiga platser, och där kanterna betecknar möjligheten att flytta och kommunicera mellan platser. Vi antar att när en robot placeras vid var och en av grafvertiklarna ger föreningen av sensoravtryck fullständig sensortäckning av miljön. När det gäller prestandakriterierna för en patrullbana, anser vi (i) tidsklyftan mellan två besök i samma region, kallas uppdateringstid, och (ii) den tid som behövs för att informera teamet av robotar om en händelse inträffade i miljön, kallas latency. Löst taget återspeglar uppdateringstid och latens effektiviteten hos ett patrullteam när det gäller att upptäcka händelser i miljön och organisera avhjälpande åtgärder. För både uppdateringstid och latensoptimering problem, vi fokuserar
Upphovsmän till REF analyserar uppdateringstiden och latensen i områdesbevakningsproblem med flera robotar med olika tillvägagångssätt.
On cooperative patrolling: optimal trajectories, complexity analysis, and approximation algorithms
{'venue': 'IEEE Transaction on Robotics, vol. 28, issue 3, pp. 592-606, 06/2012', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}