Abstrakt. Vi utvecklar och analyserar algoritmer för spridning av en svärm av primitiva robotar i en okänd miljö, R. Det primära målet är att minimera makespan, det vill säga tiden att fylla hela regionen. En miljö består av pixlar som bildar en ansluten delmängd av heltals rutnätet. Det finns som mest en robot per pixel och robotar rör sig horisontellt eller vertikalt vid enhetshastighet. Robotar går in i R med hjälp av k ≥ 1 dörr pixlar Robotar är primitiva finita automata, endast med lokal kommunikation, lokala sensorer, och en konstant storlek minne. Vi ger först algoritmer för single-door fallet (dvs k = 1), analysera algoritmerna både teoretiskt och experimentellt Vi bevisar att våra algoritmer har optimal makespan 2A − 1, där A är området för R. Vi ger nästa en algoritm för multi-door fallet (k ≥ 1), baserat på en väggföljande version av ledaren-följare strategi. Vi bevisar att vår strategi är O(log(k + 1))-konkurrenskraftig, och att denna gräns är snäv för vår strategi och andra relaterade strategier.
Vi arbetar i en miljö som liknar REF, där tiden är synkron och robotar har lokala sensorer och ändligt minne.
Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Engineering']}