How to meet asynchronously (almost) everywhere
From MaRDI portal
Abstract: Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, 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 (finite or infinite) 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.
Recommendations
Cited in
(39)- On asynchronous rendezvous in general graphs
- Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
- On deterministic rendezvous at a node of agents with arbitrary velocities
- Gathering of robots in a ring with mobile faults
- Use of information, memory and randomization in asynchronous gathering
- Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
- Verification of agent navigation in partially-known environments
- Byzantine gathering in polynomial time
- Meeting in a polygon by anonymous oblivious robots
- Leader election for anonymous asynchronous agents in arbitrary networks
- Time versus space trade-offs for rendezvous in trees
- Asynchronous approach in the plane: a deterministic polynomial algorithm
- Rendezvous in planar environments with obstacles and unknown initial distance
- Deterministic rendezvous with different maps
- Deterministic polynomial approach in the plane
- Distributed graph searching with a sense of direction
- Anonymous meeting in networks
- Rendezvous in networks in spite of delay faults
- Price of asynchrony in mobile agents computing
- Deterministic meeting of sniffing agents in the plane
- Rendezvous problem
- Asynchronous deterministic rendezvous in bounded terrains
- Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
- Tell Me Where I Am So I Can Meet You Sooner
- Almost optimal asynchronous rendezvous in infinite multidimensional grids
- Byzantine gathering in polynomial time
- Beyond rings: gathering in 1-interval connected graphs
- How to meet asynchronously (almost) everywhere
- Mathematical Foundations of Computer Science 2005
- Near-gathering of energy-constrained mobile agents
- Gathering in dynamic rings
- Time versus cost tradeoffs for deterministic rendezvous in networks
- Almost universal anonymous rendezvous in the plane
- Meeting in a polygon by anonymous oblivious robots
- Asynchronous deterministic rendezvous in bounded terrains
- A further study on weak Byzantine gathering of mobile agents
- Want to gather? No need to chatter!
- Symmetry breaking in the plane. Rendezvous by robots with unknown attributes
- Fast rendezvous with advice
This page was built for publication: How to meet asynchronously (almost) everywhere
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189080)
