Vi använder distribuerade datorverktyg för att ge ett nytt perspektiv på beteendet hos kooperativa biologiska ensembler. Vi introducerar Mynt i närheten Treasure Search (ANTS) problem, en generalisering av den klassiska ko-pat problem [10, 20, 41, 42], som är relevant för kollektiv födosök i djurgrupper. I ANTS-problemet, k identiska (probabilistiska) agenter, ursprungligen placerade på någon central plats, kollektivt söka efter en skatt i det tvådimensionella planet. Skatten placeras på en målplats av en motståndare och målet är att hitta den så snabbt som möjligt som en funktion av både k och D, där D är avståndet mellan den centrala platsen och målet. Detta motiveras biologiskt av kooperativ, central plats födosök, till exempel utförs av myror runt deras bo. I denna typ av sökning finns det en stark preferens att lokalisera närliggande matkällor innan de som är längre bort. Vi fokuserar på att försöka hitta vad som kan uppnås om kommunikationen är begränsad eller helt frånvarande. För att undvika överlappningar måste agenterna vara mycket spridda, vilket gör kommunikationen svår att kommunicera med. Dessutom, om agenterna inte börjar sökningen i synkronisering, då även inledande kommunikation är problematiskt. Detta gäller särskilt frågan om huruvida agenterna kan kommunicera och sluta sitt totala antal, k. Det visar sig att kunskapen om k by * Stödd av Israel Science Foundation (bidrag 1694/10). † Stöds av ANR-projekten DISPLEXITET och PROSE och av INRIA-projektet GANG. Denna författares arbete stöddes delvis av franska Agence Nationale de la Recherche under referens ar 10 jcjc 0204 01. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. PoDC'12, 16–18 juli 2012, Madeira, Portugal. Upphovsrätt 2012 ACM 978-1-4503-1450-3/12/07...$10.00. de enskilda agenterna är avgörande för prestationen. Det är faktiskt en enkel iakttagelse att den tid som krävs för att hitta skatten är  och vi visar i detta dokument att denna gräns kan matchas om agenterna har kunskap om k upp till en viss konstant approximation. Vi presenterar en strikt gräns för konkurrenspåföljden som måste betalas, under löptiden, om agenterna inte har någon information om k. Speciellt är denna gräns något mer än logaritmisk i antalet agenter. Dessutom ger vi en lägre gräns för den miljö där agenterna ges en viss uppskattning av k. Informellt innebär våra resultat att agenterna kan prestera bra utan någon kunskap om deras totala antal k, men för att ytterligare förbättra, de måste använda viss information om k. Slutligen föreslår vi en enhetlig algoritm som är både effektiv och extremt enkel, vilket tyder på dess relevans för faktiska biologiska scenarier.
Mer exakt, REF presenterar en algoritm för att hitta målet i optimal förväntad tid O(D 2 /n + D), förutsatt att varje agent i algoritmen vet antalet agenter n (men inte D).
Collaborative search on the plane without communication
{'venue': "PODC '12", 'journal': None, 'mag_field_of_study': ['Computer Science']}