Abstrakt. Två anonyma mobila agenter (robotar) som rör sig på ett asynkront sätt måste mötas i ett oändligt rutnät av dimension δ > 0, med början från två godtyckliga positioner på avstånd som mest d. Eftersom problemet är klart ogenomförbart i en sådan allmän miljö, antar vi att rutnätet är inbäddat i ett δ-dimensionellt Euclidean utrymme och att varje agent känner till Cartesian koordinater för sin egen ursprungliga position (men inte den ena av den andra agenten). Vi utformar en algoritm som tillåter agenterna att mötas efter att ha kört en bana av längd O(d δ polylog d). Detta är bundet för 2d-grids subsumes huvudresultatet av [12]. Algoritmen är nästan optimal, eftersom den lägre gränsen är okomplicerad. Vidare tillämpar vi vår mötesplats metod för följande nätverksdesign problem. Hamnarna i det δ-dimensionella rutnätet måste ställas in så att två anonyma agenter som startar på avstånd som mest d från varandra alltid kommer att mötas, rör sig på ett asynkront sätt, efter att ha passerat en O(d δ polylog d) längdbana. Vi kan också tillämpa vår metod på en version av det geometriska mötesproblemet. Två anonyma agenter rör sig asynkront i det δ-dimensionella Euklideiska rummet. Agenterna har synlighetsradierna r1 respektive r2. Varje agent vet bara sin ursprungliga position och sin egen siktradie. Agenterna träffas när en agent är synlig för den andra. Vi föreslår en algoritm som utformar banan för varje agent, så att de alltid träffas efter att ha rest ett totalt avstånd av O(( )), där r = min(r1, r2) och för r ≥ 1.
Bampas m.fl. Ref överväga insamling av två mobila agenter med ett begränsat synfält som rör sig asynkront i det δ-dimensionella Euclidean rummet, och föreslå en algoritm för deras banor som garanterar deras möte inom ett bestämt avstånd rest.
Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids
{'venue': 'DISC 2010, UNITED STATES', 'journal': None, 'mag_field_of_study': ['Computer Science']}