论文标题
通过变质机器人系统从各种有限的2D方格电场撤离
Evacuation from Various Types of Finite 2D Square Grid Fields by a Metamorphic Robotic System
论文作者
论文摘要
变质机器人系统（MRS）由匿名，无内存和自主模块组成，这些模块执行相同的分布式算法以移动，同时保持模块的连接性。对于MRS，解决给定任务所需的模块数量是重要的复杂度度量。在这里，我们考虑通过MRS从有限的二维正方形网格场中撤离。这项研究旨在确定在几种条件下解决疏散问题所需的最少数量的模块。我们考虑一个矩形田，被至少一个出口包围的墙壁包围。我们的结果表明，如果配备了全球指南针，则需要两个模块，足以从任何矩形字段撤离，这为模块提供了常见的方向感。之后，我们将重点放在没有全球指南针的模块的情况下，并表明四个（分别为七个）模块是必需的，足以足以限制MRS的初始形状。我们还表明，当MRS以初始配置触摸墙壁时，两个模块就足够了。然后，我们阐明了撤离矩形场后停止MRS的情况。最后，我们将这些结果扩展到迷宫和凸场。
A metamorphic robotic system (MRS) is composed of anonymous, memoryless, and autonomous modules that execute an identical distributed algorithm to move while keeping the connectivity of the modules. For an MRS, the number of modules required to solve a given task is an important complexity measure. Here, we consider evacuation from a finite two-dimensional square grid field by an MRS. This study aims to establish the minimum number of modules required to solve the evacuation problem under several conditions. We consider a rectangular field surrounded by walls with at least one exit. Our results show that two modules are necessary and sufficient for evacuation from any rectangular field if equipped with a global compass, which provides the modules with a common sense of direction. After that, we focus on the case of modules without a global compass and show that four (resp. seven) modules are necessary and sufficient for restricted (resp. any) initial shapes of an MRS. We also show that two modules are sufficient when an MRS is touching a wall in an initial configuration. Then, we clarify the condition to stop an MRS after evacuation of a rectangular field. Finally, we extend these results to mazes and convex fields.
