Computational Power of Mobile Robots in Synchronous Environment: Discrete Version

在移动机器人的分布式计算中，机器人被部署在一个连续或离散的区域内，通过一系列的“观察-计算-移动”循环运行。已经进行了广泛的研究，以了解不同机器人模型的计算能力。这些模型的能力不同，包括：1）记住恒定大小的信息；2）传递恒定大小的信息。根据这些能力，不同的模型分别是：1）$\mathcal{OBLOT}$（机器人是无意识和无声的）；2）$\mathcal{FSTA}$（机器人具有有限状态但无声）；3）$\mathcal{FCOM}$（机器人无意识但可以传递恒定大小的信息）；4）$\mathcal{LUMI}$（机器人具有有限状态且可以传递恒定大小的信息）。另一个影响计算能力的因素是决定机器人激活时间的调度程序。主要的三种调度程序是完全同步、半同步和异步。将模型（$M$）与调度程序（$K$）相结合，我们有$M^K$的十二种组合。在欧几里得域中，透明机器人、不透明机器人和具有有限可见性的机器人之间进行了这十二个变体的比较。当机器人在像网络这样的离散区域上运行时，类似的研究工作还有待开展。这需要单独的研究关注，因为已经有一系列的工作表明，当机器人在连续域和离散域上运动时存在根本性的差异。本文通过给出所有模型与两个同步调度程序（完全同步和半同步）的完整比较表，为填补这一空白做出了贡献。

比较不同机器人模型在离散网络中的计算能力

通过在离散网络中比较四种机器人模型和两种调度器的计算能力，填补了这一领域的研究空白

实验设计详细，使用了离散网络数据集，提供了所有模型和调度器的计算能力比较表格，为离散网络中机器人的计算能力研究提供了基础

该领域最近的相关研究主要集中在连续领域中机器人的计算能力研究，如透明机器人、不透明机器人和有限可见度机器人等，具体论文包括《Distributed Computing by Oblivious Robots in Continuous Spaces》、《Distributed Computing by Opaque Robots in Euclidean Spaces》等