Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains - Publication - Bridge of Knowledge

Search

Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains

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

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 63 times

Recommended for you

Meta Tags