Abstrakt. Vi anser att problemet med att utforska en anonym oorienterad ring av storlek n av k identiska, omedvetna, asynkrona mobila robotar, som inte kan kommunicera, men ändå har förmågan att känna sin miljö och fatta beslut baserat på sin lokala syn. Tidigare verk i detta svaga scenario bevisar att k inte får dela n för att en deterministisk lösning ska existera. Det är också känt att det minsta antalet robotar (antingen deterministiska eller probabilistiska) att utforska en ring av storlek n är 4. En övre gräns på 17 robotar håller i det deterministiska fallet medan 4 probabilistiska robotar är tillräckliga. I detta dokument täpper vi till komplexitetsklyftan i den deterministiska miljön, genom att bevisa att ingen deterministisk utforskning är möjlig med mindre än fem robotar när ringens storlek är jämn, och att fem robotar är tillräckliga för alla n som är coprime med fem. Vårt protokoll slutför prospektering i O(n) robot flyttar, vilket också är optimalt.
I REF, å andra sidan, har det visat sig att ingen deterministisk undersökning är möjlig med mindre än fem robotar när storleken på ringen är jämn, och att fem robotar är tillräckligt för alla n som är co-prime med fem.
Optimal deterministic ring exploration with oblivious asynchronous robots
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}