Vi föreslår optimal (w.r.t. Antalet robotar) lösningar för deterministiska avslutande prospektering (utforskning för kort) av ett rutnätsformat nätverk av ett team av k asynkrona omedvetna robotar i den asynkrona icke-atomiska modellen, så kallad CORDA. I fler detaljer tar vi först hänsyn till ATOM-modellen. Vi visar att det är omöjligt att utforska ett rutnät med minst tre noder med mindre än tre robotar. Därefter visar vi att det är omöjligt att utforska en (2, 2)-Grid med mindre än 4 robotar, och en (3, 3)-Grid med mindre än 5 robotar, respektive. De två första resultaten gäller både deterministiska och probabilistiska miljöer, medan de senare endast gäller i det deterministiska fallet. ATOM är strikt starkare än CORDA, och alla dessa omöjlighetsresultat håller också i CORDA. Sedan föreslår vi deterministiska algoritmer i CORDA för att visa det optimala antalet robotar som gör det möjligt att utforska ett givet rutnät. Våra resultat visar att förutom i två särskilda fall, 3 robotar är nödvändiga och tillräckliga för att deterministiskt utforska ett rutnät med minst tre noder. Det optimala antalet robotar för de två återstående lådorna är: 4 för (2, 2)-Grid och 5 för (3, 3)-Grid, respektive.
Det andra extrema fallet är uppsättningen rutnätsformade nät REF, där tre robotar är nödvändiga och tillräckliga för att deterministiskt undersöka alla rutnät med minst tre noder (utom rutnät av storlek 2 × 2 och 3 × 3, där fyra respektive femrobotar är nödvändiga och tillräckliga).
Optimal grid exploration by asynchronous oblivious robots
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}