Computer Science – Data Structures and Algorithms
Scientific paper
2010-01-06
Computer Science
Data Structures and Algorithms
Scientific paper
Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly in?nite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerfull adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (?nite or in?nite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. While our algorithms work in a very general setting ? agents can, indeed, meet almost everywhere ? we show that none of the above few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other.
Czyzowicz Jurek
Labourel Arnaud
Pelc Andrzej
No associations
LandOfFree
How to meet asynchronously (almost) everywhere does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with How to meet asynchronously (almost) everywhere, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How to meet asynchronously (almost) everywhere will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-164267