Invited Paper: One Bit Agent Memory is Enough for Snap-Stabilizing Perpetual Exploration of Cactus Graphs with Distinguishable Cycles
Invited Paper: One Bit Agent Memory is Enough for Snap-Stabilizing Perpetual Exploration of Cactus Graphs with Distinguishable Cycles
复制标题
特邀论文：一位智能体内存足以对具有可区分循环的仙人掌图进行快速稳定的永久探索
DOI：
10.1007/978-3-031-21017-4_2
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Masuzawa Toshimitsu
中科院分区：
文献类型：
--
作者：
Shimoyama Kohei;Sudo Yuichi;Kakugawa Hirotsugu;Masuzawa Toshimitsu
本文考虑了在节点没有存储空间的限制下，单个移动的agent对具有可区分圈的匿名仙人掌图的永久探索（例如，白板或令牌位置）。具有可区分的循环的仙人掌允许代理在每个节点处区分每个循环中包含的两个事件边缘与其他事件边缘。本文将瞬变稳定的概念引入到永久探索中，证明了当主体具有1比特持久记忆时，瞬变稳定的永久探索是可能的。所提出的算法的探索时间完全符合平凡的下限。本文还显示了一位代理内存的必要性，任何健忘（或无记忆）代理不能探索仙人掌图，即使它只有一个可区分的周期。最后，本文证明了当具有可区分圈的仙人掌图具有方向感时，遗忘代理的快照稳定永久探索是可能的。
This paper considers perpetual exploration of anonymous cactus graphs with distinguishable cycles by a single mobile agent under the restriction that nodes have no storage (e.g.,whiteboards or token places). A cactus with distinguishable cycles allows the agent to distinguish at each node the two incident edges contained in each cycle from other incident edges. This paper introduces the concept of snap-stabilization into the perpetual exploration and shows that snap-stabilizing perpetual exploration is possible when the agent has one-bit persistent memory. The exploration time of the presented algorithm exactly matches a trivial lower bound. This paper also shows the necessity of one-bit agent memory by showing that any oblivious (or memory-less) agent cannot explore a cactus graph even when it has only a single distinguishable cycle. Finally, this paper shows that snap-stabilizing perpetual exploration by an oblivious agent is possible when a cactus graph with distinguishable cycles has a sense of direction.