How to meet asynchronously almost everywhere - Computer Science > Data Structures and AlgorithmsReport as inadecuate

How to meet asynchronously almost everywhere - Computer Science > Data Structures and Algorithms - Download this document for free, or read online. Document in PDF available to download.

Abstract: Two mobile agents robots with distinct labels have to meet in an arbitrary,possibly infinite, unknown connected graph or in an unknown connected terrainin the plane. Agents are modeled as points, and the route of each of them onlydepends on its label and on the unknown environment. The actual walk of eachagent also depends on an asynchronous adversary that may arbitrarily vary thespeed of the agent, stop it, or even move it back and forth, as long as thewalk of the agent in each segment of its route is continuous, does not leave itand covers all of it. Meeting in a graph means that both agents must be at thesame time in some node or in some point inside an edge of the graph, whilemeeting in a terrain means that both agents must be at the same time in somepoint of the terrain. Does there exist a deterministic algorithm that allowsany two agents to meet in any unknown environment in spite of this verypowerfull adversary? We give deterministic rendezvous algorithms for agentsstarting at arbitrary nodes of any anonymous connected graph finite orinfinite and for agents starting at any interior points with rationalcoordinates in any closed region of the plane with path-connected interior.While our algorithms work in a very general setting ? agents can, indeed, meetalmost everywhere ? we show that none of the above few limitations imposed onthe environment can be removed. On the other hand, our algorithm alsoguarantees the following approximate rendezvous for agents starting atarbitrary interior points of a terrain as above: agents will eventually get atan arbitrarily small positive distance from each other.

Author: Jurek Czyzowicz, Arnaud Labourel LaBRI, Andrzej Pelc


Related documents