Different Speeds Suffice for Rendezvous of Two Agents on Arbitrary Graphs
Different Speeds Suffice for Rendezvous of Two Agents on Arbitrary Graphs
复制标题
不同的速度足以满足任意图上两个智能体的会合
DOI：
10.1007/978-3-319-51963-0_7
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Felipe Ramírez
中科院分区：
文献类型：
--
作者：
E. Kranakis;D. Krizanc;Euripides Markou;Aris Pagourtzis;Felipe Ramírez
本文研究了任意n个顶点且边长为1的连通图上的两机器人交会问题。两个机器人最初位于图的两个不同顶点上，并且可以以不同但恒定的速度遍历其边缘。机器人不知道自己的速度。在它们的移动过程中，允许它们在图的顶点或边上相遇。根据反映机器人知识的一定条件，我们证明了一般连通图上的交会算法总是可能的，更具体地说，我们给出了两个机器人的新交会算法如下。(1)In未知的拓扑结构。我们提供了一个多项式时间会合算法的基础上普遍的探索序列，假设已知的机器人。(2)In已知的拓扑结构。在这种情况下，我们证明了更有效的会合算法的存在，通过考虑二维环面的特殊情况。
We consider the rendezvous problem for two robots on an arbitrary connected graph withnvertices and all its edges of length one. Two robots are initially located on two different vertices of the graph and can traverse its edges with different but constant speeds. The robots do not know their own speed. During their movement they are allowed to meet on either vertices or edges of the graph. Depending on certain conditions reflecting the knowledge of the robots we show that a rendezvous algorithm is always possible on a general connected graph.More specifically, we give new rendezvous algorithms for two robots as follows. (1)In unknown topologies.We provide a polynomial time rendezvous algorithm based onuniversal exploration sequences, assuming thatnis known to the robots. (2)In known topologies.In this case we prove the existence of more efficient rendezvous algorithms by considering the special case of the two-dimensional torus.
循环图和过滤的半 Gorenstein 环
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
Mitsuhiro Miyazaki;Katsuyuki Naoi;宮崎充弘
通讯作者：
宮崎充弘