Asynchronous Rendezvous of Anonymous Agents in Arbitrary Graphs
Asynchronous Rendezvous of Anonymous Agents in Arbitrary Graphs
复制标题
任意图中匿名代理的异步集合
DOI：
10.1007/978-3-642-25873-2_29
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Pelc
中科院分区：
文献类型：
--
作者：
Samuel Guilbault;A. Pelc
两个相同的（匿名的）移动代理必须在任意的、可能无限的、未知的连接图中相遇。智能体被建模为点，它们从对手选择的图的节点开始，每个智能体的路径只取决于图中已经走过的部分，在随机集合的情况下，取决于抛硬币的结果。每个代理的实际行走还取决于一个异步对手，它可以任意改变代理的速度，停止它，甚至来回移动它，只要代理在其路由的每个段中的行走是连续的，不离开它并覆盖它的所有部分。相遇意味着两个代理必须同时在图的某个节点或某条边内的某个点上。在确定性场景中，我们描述了可以进行集合的智能体的初始位置，并提供了一种保证任意连通图中所有这些位置的异步集合的算法。在随机场景中，我们展示了一种算法，对于任意连通图中的任意初始位置，实现概率为1的异步会合。在这两种情况下，图可能是有限的或（可数）无限的。
Two identical (anonymous) mobile agents have to meet in an arbitrary, possibly infinite, unknown connected graph. Agents are modeled as points, they start at nodes of the graph chosen by the adversary and the route of each of them only depends on the already traversed portion of the graph and, in the case of randomized rendezvous, on the result of coin tossing. 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 means that both agents must be at the same time in some node or in some point inside an edge of the graph.In the deterministic scenario we characterize the initial positions of the agents for which rendezvous is feasible and we provide an algorithm guaranteeing asynchronous rendezvous from all such positions in an arbitrary connected graph. In the randomized scenario we show an algorithm that achieves asynchronous rendezvous with probability 1, for arbitrary initial positions in an arbitrary connected graph. In both cases the graph may be finite or (countably) infinite.
循环图和过滤的半 Gorenstein 环
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
Mitsuhiro Miyazaki;Katsuyuki Naoi;宮崎充弘
通讯作者：
宮崎充弘