Distribuerade Vi föreställer oss ett scenario med robotar som rör sig på en terräng som representeras av ett plan. En mobil robot, som kallas upptäcktsresande, är ansluten genom en kommunikationskedja till ett stationärt basläger. Kedjan förväntas skicka meddelanden mellan upptäcktsresanden och baslägret. Den består av enkla, mobila robotar, så kallade reläer. Vi undersöker strategier för att organisera och underhålla kedjan, så att antalet reläer som används minimeras och ändå avståndet mellan närliggande reläer i kedjan förblir begränsad. Vi letar efter lokala och distribuerade strategier som används av begränsade reläer som måste basera sitt beslut ("Vart ska jag ta vägen?") enbart på sina grannars relativa positioner i kedjan. Vi presenterar Manhattan-Hopper och Hopper strategi som förbättrar prestandan av alla kända lösningar på detta problem avsevärt. De är de första sådana strategier som är optimala i denna miljö, dvs., som gör det möjligt för upptäcktsresanden att röra sig med konstant hastighet, oberoende av längden på kedjan, och hålla denna längd minimum upp till en konstant faktor. I detta dokument kommer vi att behandla frågan om hur man organiserar en kedja av reläer som förbinder två punkter på ett plan. En av punkterna, baslägret, står stilla medan den andra är rörlig och kallas upptäcktsresande. Vi har inget inflytande på upptäcktsresandens rörelser; de strategier vi utformar styr reläernas rörelser. Vi utformar strategier för reläer som håller kedjan kort och upprätthålla anslutning trots förflyttning av upptäcktsresanden. Den största utmaningen ligger i den begränsning som reläerna måste fatta beslut på lokal nivå och endast grunda sina beslut på mycket begränsad information. Hittills har vi informellt talat om en kedja av reläer. Härmed menar vi en beställd sekvens av reläer, betecknar med v 1,. .., v n. Av tekniska skäl inkluderar vi upptäcktsresanden och baslägret i kedjan, som respektive dess första och sista element; v 0 beskriver upptäcktsresanden och v n+1 baslägret. Element i kedjan kommer att kallas stationer, vilket innebär antingen ett relä, upptäcktsresanden eller baslägret. Den huvudsakliga begränsningen på kedjan är att vi kräver att avståndet mellan stationer som är intilliggande i kedjan inte överstiger överföringsavståndet på 1. Tack vare detta kan kedjan vidarebefordra meddelanden mellan baslägret och upptäcktsresanden. Vi vill utforma strategier för de reläer som styr deras rörelse på planet. Var och en av reläerna antas utföra sin egen kopia av denna strategi och kan känna miljön. Vi kommer att gå djupare in på detaljer om reläernas beräknings- och avkänningsförmåga när vi beskriver relämodellen senare. Den största utmaningen för detta problem är att vi söker strategier som fungerar lokalt och med mycket enkel logik. Därför måste vi utforma en lösning där varje relä beräknar sin position på egen hand, där kommunikation inte används alls, och reläer inte har något minne. Vi är intresserade av att se om man kan utforma effektiva strategier för att lösa detta problem inom denna enkla modell.
Hopper och Manhattan Hopper strategier REF lösa detta problem i tid O(n), i Euclidean planet respektive på nätet, med hjälp av robotar med ett konstant antal stater, ett konstant minne och förmågan att kommunicera stater till lokala grannar (flaggor, ljus).
Optimal strategies for maintaining a chain of relays between an explorer and a base camp
{'venue': 'THEORETICAL COMPUTER SCIENCE', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}