I arbetet med att förstå algoritmiska begränsningar dator av en svärm av robotar, forskningen har fokuserat på de minimala kapaciteter som gör att ett problem kan lösas. Den svagaste av de vanliga modellerna är Asynch där de autonoma mobila robotarna, utrustade med siktsensorer (men annars oförmögna att kommunicera), fungerar i Look-Compute-Move cyklerna utförs asynkront för varje robot. Robotarna antas ofta (eller måste vara) omedvetna: de håller inget minne av observationer och beräkningar gjorda i tidigare cykler. Vi betraktar inställningen när robotarna är utspridda i en anonym och omärkt graf, och de måste utföra den mycket grundläggande uppgiften att utforska: inom ändlig tid måste varje nod besökas av minst en robot och robotarna måste gå in i ett tyst tillstånd. Det komplexa måttet på en lösning är antalet robotar som används för att utföra uppgiften. Vi studerar fallet när grafen är ett godtyckligt träd och fastställer några oväntade resultat. Vi bevisar först att det finns n-node träd där  ska(n) robotar är nödvändiga; detta håller även om den maximala graden är 4. Å andra sidan visar vi att om den maximala graden är 3, är det möjligt att utforska med endast O( log n log n ) robotar. Beviset på resultatet är konstruktivt. Slutligen visar vi att storleken på teamet är asymptotiskt optimal: vi visar att det finns träd av grad 3 vars utforskning kräver  och ( log n logg n ) robotar.
Ett extremt fall i denna svaga modell är uppsättningen av trädformade nätverk, som i allmänhet,  och (n) robotar är nödvändiga och tillräckliga för att utforska ett träd nätverk av n noder deterministiskt REF.
Remembering Without Memory: Tree Exploration by Asynchronous Oblivious Robots
{'venue': 'SIROCCO 2008, VILLARS-SUR-OLLON: SUISSE', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}