Synchronous Rendezvous for Location-Aware Agents
Synchronous Rendezvous for Location-Aware Agents
复制标题
位置感知代理的同步集合点
DOI：
10.1007/978-3-642-24100-0_42
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Martin
中科院分区：
文献类型：
--
作者：
Andrew Collins;J. Czyzowicz;L. Gąsieniec;A. Kosowski;R. Martin
我们研究了两个匿名代理的会合，其中每个代理都知道自己在环境中的初始位置。他们的任务是尽快见面。交会的时间是通过代理在最坏的情况下需要使用的同步轮次来衡量的。在每一轮中，代理人可能会做出简单的移动，也可能保持不动。我们考虑两种环境，有限或无限图和欧几里得空间。一个简单的移动遍历一条边(在图中)或至多一个单位距离(在欧几里得空间中)。交会是指两个智能体同时(在同一轮)访问环境中的同一点，本文提出了几种渐近最优交会算法。特别地，我们证明了在直线和树以及多维欧氏空间和网格中，智能体可以在时间上交会，其中智能体初始位置之间的距离是智能体的初始位置之间的距离。我们指出，与异步情况相反，在异步情况下，交会成本由潜在大邻域的大小控制，代理能够在时间几乎线性的IND的所有图中相遇，即，。我们还确定了同步交会花费时间Ω(D)的无穷图族。
We study rendezvous of two anonymous agents, where each agent knows its own initial position in the environment. Their task is to meet each other as quickly as possible. The time of the rendezvous is measured by the number of synchronous rounds that agents need to use in the worst case in order to meet. In each round, an agent may make a simple move or it may stay motionless. We consider two types of environments, finite or infinite graphs and Euclidean spaces. A simple move traverses a single edge (in a graph) or at most a unit distance (in Euclidean space). The rendezvous consists in visiting by both agents the same point of the environment simultaneously (in the same round).In this paper, we propose several asymptotically optimal rendezvous algorithms. In particular, we show that in the line and trees as well as in multi-dimensional Euclidean spaces and grids the agents can rendezvous in time, wheredis the distance between the initial positions of the agents.The problem of location-aware rendezvous was studied before in the asynchronous model for Euclidean spaces and multi-dimensional grids, where the emphasis was on the length of the adopted rendezvous trajectory. We point out that, contrary to the asynchronous case, where the cost of rendezvous is dominated by the size of potentially large neighborhoods, the agents are able to meet in all graphs of at mostnnodes in time almost linear ind, namely,. We also determine an infinite family of graphs in which synchronized rendezvous takes time Ω(d).
循环图和过滤的半 Gorenstein 环
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
Mitsuhiro Miyazaki;Katsuyuki Naoi;宮崎充弘
通讯作者：
宮崎充弘