Abstract-The main contribution of this paper är en förbättrad algoritm för GRAPH-CLEAR-problemet, en ny NP-komplett grafteoretisk problem vi nyligen introducerade som ett verktyg för att modellera multi-robot övervakning uppgifter. Den föreslagna algoritmen kombinerar två tidigare utvecklade lösningstekniker och producerar strategier som kräver mindre robotar att utföras. Vi tillhandahåller en teoretisk ram som är användbar för att identifiera förutsättningarna för en optimal lösning under speciella omständigheter, och en uppsättning matematiska verktyg som kännetecknar det problem som studeras. Slutligen identifierar vi också en rad öppna frågor som förtjänar fler undersökningar. Användningen av multirobotsystem för övervakning av vidsträckta regioner är ett av de väletablerade områdena inom multirobotforskning. Fram till nu har det dock fortfarande varit mycket få utplaceringar på fältet av dessa system för verkliga tillämpningar i världen. Förutom den uppenbara kostnadsfrågan är en annan orsak till deras måttliga användning det faktum att många grundläggande frågor om en effektiv samordning av dessa system fortfarande är obesvarade. En stor del av den tidigare teoretiska forskningen utvecklade modeller där robotar var utrustade med sensorer abstraktioner ganska långt från realistiska tillämpningar, t.ex. sensorer med oändlig räckvidd och lika. I det här dokumentet utökar vi istället våra tidigare resultat som syftar till att undersöka övervakningsuppgifter av multi-robotsystem där enskilda agenter använder sensorer med begränsad kapacitet. Vi startade denna forskningstråd med två papper [5] [6] som syftade till att utvidga CMOMMT (Cooperative Multi-robot Observation of Multiple Moving Targets) problem som ursprungligen ställdes av Parker [11]. En av de viktigaste begränsningarna med dessa algoritmer är kravet på att robotar fungerar i öppna områden. Våra följande insatser har därför ägnats åt scenarier där robotar verkar i belamrade miljöer [7]. I synnerhet modellerade vi problemet med att upptäcka flera inkräktare i en komplex miljö med hjälp av ett nytt grafteoretiskt problem, dubbade GRAPH-CLEAR. Informellt frågar sig problemet vilket minsta antal robotar som behövs för att upptäcka alla möjliga inkräktare i en given komplex miljö som kan modelleras som en graf. [8] visade vi att det tillhörande beslutsproblemet är NP-fullständigt. Som klargörs senare, ett sätt att kringgå intractability av problemet på grafer, är att utföra vissa vaktoperationer som förvandlar grafer till träd. Under [7] och [8] har vi tillhandahållit två algoritmer som producerar sökstrategier för träd, dvs. åtgärder för ett robotteam som säkerställer att varje inkräktare kommer att upptäckas. Båda algoritmerna är kända för att vara suboptimala. I detta dokument
Kolling och Carpin REF presenterar en algoritm för att hitta det minsta antal robotar som behövs för att upptäcka eventuella intrång, i inomhusmiljöer med många rum anslutna via flera dörrar.
Multi-robot surveillance: An improved algorithm for the GRAPH-CLEAR problem
{'venue': '2008 IEEE International Conference on Robotics and Automation', 'journal': '2008 IEEE International Conference on Robotics and Automation', 'mag_field_of_study': ['Computer Science']}