Search
Abstract
Two mobile agents, modeled as points starting at differentlocations of an unknown terrain, have to meet. The terrain is a polygon with polygonal holes. We consider two versions of this rendezvous problem: exact RV, when the points representing the agents have to coincide at some time, and epsilon-RV, when these points have to get at distance less than epsilon in the terrain. In any terrain, each agent chooses its trajectory, but the movements of the agent on this trajectory are controlled by an adversary that may, e.g., speed up or slow down the agent. Agents have bounded memory: their computational power is that of finite state machines. Our aim is to compare the feasibility of exact and of epsilon-RV when agents are anonymous vs. when they are labeled. We show classes of polygonal terrains which distinguish all the studied scenarios from thepoint of view of feasibility of rendezvous. The features which influence the feasibility of rendezvous include symmetries present in the terrains, boundedness of their diameter, and the number of vertices of polygons in the terrains.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (3)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
LECTURE NOTES IN COMPUTER SCIENCE
no. 6281,
pages 294 - 305,
ISSN: 0302-9743 - Language:
- English
- Publication year:
- 2010
- Bibliographic description:
- Czyzowicz J., Kosowski A., Pelc A.: Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains// LECTURE NOTES IN COMPUTER SCIENCE. -Vol. 6281., (2010), s.294-305
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/978-3-642-15155-2_27
- Verified by:
- Gdańsk University of Technology
seen 60 times
Recommended for you
Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
- J. Czyzowicz,
- A. Kosowski,
- A. Pelc
Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs
- S. Das,
- D. Dereniowski,
- A. Kosowski
- + 1 authors
Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks
- D. Dereniowski,
- Ł. Kuszner,
- A. Kosowski
- + 1 authors
Rendezvous of heterogeneous mobile agents in edge-weighted networks
- D. Dereniowski,
- R. Klasing,
- A. Kosowski
- + 1 authors