分布式移动机器人：同步vs异步光增强模型比较研究

可在www.sciencedirect.com在线获取理论计算机科学电子笔记322（2016）169-180www.elsevier.com/locate/entcs同步机器人vs异步光增强机器人在图1MattiaGran Sasso Science Institute（GSSI），Viale Francesco Crispi，I信息工程系，计算机科学和数学，拉奎拉大学Daniele Frigioni3信息工程系，计算机科学和数学，拉奎拉大学阿尔弗雷多·纳瓦拉4数学和计算机科学系，佩鲁贾大学，Via Vanvitelli，1，I-06123，佩鲁贾，意大利。摘要在本文中，我们考虑分布式设置的计算移动实体，称为机器人，在没有全球协调的情况下执行任务。根据环境以及机器人特别是，我们专注于众所周知的情况下，机器人驻留在一个图形的节点上，并在查找-计算-移动周期操作。 在一个周期中，机器人感知当前的配置，机器人的位置（看），决定是否向图的某个边缘移动（计算），并在在肯定的情况下，它沿着计算的边缘执行瞬时移动（移动）。然后，我们比较了两个基本模型：在第一个模型中，机器人是完全同步的，而在第二个模型中，机器人是异步的，并且增强了灯光，也就是说，每个机器人都配备了恒定数量的灯光，所有其他机器人都可以看到。 一个模型是否比另一个模型更强大的问题在[Das et al.，Int.“l确认。分布式计算系统，2012年]，但机器人在欧几里德平面上移动，而不是在图上我们提供了两个不同的任务，并表明，在图上的一个任务可以解决在完全同步的模型，但不是在异步的光增强模型，而另一个任务的相反情况下举行。因此，我们可以断言，完全同步模型和异步光增强模型在图上是不可比较的。这开辟了具有挑战性的方向，以了解哪些特性使模型如此不同。保留字：分布式算法，同步性，移动机器人，发光机器人http://dx.doi.org/10.1016/j.entcs.2016.03.0121571-0661/© 2016作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。170M.1介绍在过去的几年中，在分布式计算领域中，相当大量的研究已经致力于研究所谓的基于机器人的计算系统的模型和算法方法，这是由于它们在广泛的现实世界应用中的重要性。在这种系统中，一组移动实体，通常被称为机器人，必须在取决于所考虑的场景的各种假设下执行任务和/或实现目标[6，14]。特别的研究致力于机器人自主的模型，即它们的行动没有中央控制，并在一个看-计算-移动（LCM）操作模式（参见[1，2，3，19，22]和其中的参考文献在这样一个模型，这已成为一个突出的一个在该地区的分布式算法的机器人为基础的计算系统，机器人在所谓的LCM周期。 在每个周期中，机器人获取周围环境的快照（观察阶段），然后通过使用所获得的快照作为输入（计算阶段）来执行适当的算法，该算法对所有机器人都是相同的，并且最终朝着期望的目的地移动（如果有的话）（移动阶段）。几个建模假设也被认为是可以一个campectual的机器人的计算能力特别地，在某些情况下，机器人可能具有不同的身份，即每个机器人与可以在计算阶段期间使用的不同标识符相关联。如果机器人没有标识符，那么它们被称为匿名的。在其他一些情况下，机器人可能有一个有限但持久的存储设备，其内容从一个LCM周期保存到下一个;如果机器人没有，则被称为遗忘，这意味着它们开始每个周期时没有关于过去发生的任何信息。在这个研究领域中，许多不同的问题和任务已经被研究过：机器人可能被要求在某些特定的位置聚集[20]（也称为聚集问题），形成所需的几何图案[21]（也称为图案形成问题），或者探索未知区域[17]（也称为探索问题）。此外，还调查了几种不同的环境机器人可以在欧几里得平面上移动[16]，或者它们被约束在给定的输入图上移动，该输入图可以预先已知[9]或未知[4]。机器人可以进行通信，例如通过令牌[15]或不[18]。最后，可能存在或不存在与问题相关联的待优化的目标函数（参见[3，11，12，13]和其中的参考文献）。例如，可以要求最小数量的机器人、由所有机器人执行的最小数量的步骤、或由单个机器人执行的最大数量的步骤的最小化，以实现某个目标。查找-计算-移动循环可能受到不同的时间约束1这项工作得到了意大利教育、大学和研究部（MIUR ）在国家研究项目PRIN 2010 N5 K7 EB“ARSTechnoMedia - Algoritmica per le Reti Sociali Tecno-Mediate”和国家科学计算小组（GNCS-INdAM）的部分支持2 电子邮件：mattia. univaq.it3电子邮件：daniele. univaq.it4电子邮件：alfredo. unipg.itM.171MMFSYN CMMSSYN C FSYN CASYN CM ∈{FSYNCSSYNCASYNC}由所考虑的时间表决定。文献中最常见的模型如下：全同步（）[8]：所有机器人的激活阶段可以逻辑地划分为全局轮，在每一轮中，机器人都被激活，获得相同的环境快照，计算并执行它们的移动。请注意，这个假设在计算上等同于一个完全同步的系统，其中机器人被同时激活，所有操作都是瞬间发生的。半同步（Semi-synchronous ）[10]：它与模 型 一 致 ，唯一的区别是并非所有机器人都必须在每一轮中激活。Asynchronous（）[5]：机器人是独立激活的，每个计算、移动和不活动阶段的持续时间是有限的，但不可预测。因此，机器人没有共同的时间概念。此外，它们可以在移动时被看到，并且可以根据关于位置的过时信息进行计算最近，Das等人在[6]中引入了进一步的模型，扩展了上述模型。 详细地说，给定一个模型，作者定义了模型k，其中每个机器人在模型配备了一盏灯，在观察阶段，它自己和其他机器人都可以看到。 与机器人相关联的光可以呈现k种不同的颜色，并且可以在其计算阶段由机器人更新。假设光是持久的，即尽管机器人可以被遗忘，但它们的光不会自动地在周期结束时复位。因此，机器人光增强型机器人通常被称为发光机器人。请注意，根据所考虑的场景，机器人可能对所有其他机器人的灯或仅对它们的子集具有在[6]中引入的另一个模型考虑了遗忘机器人，这些机器人“稍微”被 更准确地说，对于某个整数常数j> 0，每个机器人被允许在内部存储器中存储来自先前观看阶段的最多j个快照。当机器人在特定模型中运行时，被赋予记住k个快照的能力，我们将修改后的模型称为k，将机器人称为部分遗忘机器人。1.1论文动机我们的工作是受启发的文件Das等人。[6]，其中涉及的问题比较的计算能力的机器人在LCM模型中运行，并在欧几里德平面内移动，在不同水平的同步，与发光的机器人和部分遗忘的机器人。详细地说，[6]的作者提供了一系列结果，证明了经典模型和它们的变体之间的优势关系，这些变体考虑了使用灯光或快照或两者组合的能力。在图1中，我们总结了[6]的主要贡献，并显示了这种关系-172M.O（1）O（1）O（1）FSYN CASYN C → ASYN C ASYN CO（1）FSYN C ASYN CFSYN C ASYN CFSYN C ASYN CASYN CO（1）ASYN CO（1）ASYN CO（1）？SSYN C图1. 模型之间的关系统治地位的船只。我们用两个模型之间的一个直接箭头表示，假设A和B，事实上，在A中可解的每个问题也在B中可解。此外，我们用一个三重横杠符号表示这样一个事实，即在A中可解的每个问题也在B，反之亦然。特别是，[6]的作者表明：• ASYN C O（1）→ SSYN C O（1）→ SSYN C：在ASYN C中操作并被赋予恒定数量的灯（即在ASYN C O（1）中操作）的 机 器 人 在 计算上与在SSYN C中操作并被赋予恒定数量的灯（即在SSYN C O（1）中操作）的机器人一样强大;此外，ASYN C O（1）和SSYN C O（1）模型在计算上都比SSYN C更强大。•O（1）O（1）：机器人在恒定数量的灯光下工作，并具有记住恒定数量快照的数目（即，在ASYNCO（1）中操作比在A SYNCO（1）中运行的robot。更进一步，ASYNCO（1）更有效比FSYN C.在图1中，我们还报告了已经众所周知的优势关系从文献中，例如， FSOY（1N）C→SSYNC。注意，在[6]关系中，FSYN C和ASYN C之间的关系尚未建立。1.2文件的贡献在本文中，我们试图回答的问题，找到的关系，在可计算的任务，存在和O（1）。在这方面，我们提供了两个不同的分布式任务的机器人在图环境中移动，而不是在欧几里德平面[6]，并表明，一个任务可以解决，但不是在O（1），而另一个反之亦然。所以我们证明了O（1）和O（1）在图上是不可比的。这打开具有挑战性的方向，以了解哪些特点使模型如此不同。1.3本文结构在第2节中，我们描述了机器人运行的分布式系统。在第3节中，我们定义了一个分布式问题，它可以在FSYN C中解决，但不能在M.173ASYN C FSYN CASYN C时间复杂度为O（1）。在第4节中，我们定义了一个分布式问题，它可以在O（1）内解决，但不能在O（1）内解决 。最后，在第五部分，我们总结了本文，并提出了一些可能的未来研究方向。2预赛在本文中，如前所述，我们考虑了一个系统组成的一组移动实体，称为机器人，运行在看，计算，移动周期。特别是，每个机器人被建模为一个独立的计算单元，具有自己的本地存储器，并能够执行本地计算。机器人被放置在空间环境中，该空间环境可以被假设为无向图G=（V，E），即机器人被放置在图的节点上。 因此，每个机器人对周围环境都有自己的局部感知，这意味着它可以检测同构于G的图，并了解节点是否被占用是不是机器人每个机器人都配备了传感能力，可以返回所有其他机器人相对于其在感知图上的位置的相对位置的快照在本文的其余部分，我们假设机器人是匿名和相同的，即它们的外观无法区分，并执行相同的算法。他们是健忘的，也就是说，他们没有记忆。此外，我们认为机器人在没有中央控制的情况下行动，即它们被假设为自主的，并且不能直接与其他机器人进行信息通信（例如通过无线接口），即它们是沉默的。每个机器人都被赋予了电机能力，可以在G上自由移动。然而，沿着G的一条边的运动被认为是瞬时的，因此每次机器人感知到当前配置的快照时，它看到的所有其他机器人总是在G的节点上。当上下文不清楚时，我们将指定不同的假设。在任何时间点，机器人都是活动的或不活动的。当处于活动状态时，机器人执行一个查找-计算-移动（LCM）循环，依次执行以下三个操作，每个操作与不同的状态相关联看：机器人通过激活它的传感器来观察世界，这些传感器返回所有机器人相对于它自己感知的位置计算：机器人执行其算法，使用在观察阶段感测到的数据作为输入。此阶段的结果是一个目标（目的地）节点。移动：机器人向计算的目标移动：如果目的地是当前位置，机器人只是保持静止，即它执行我们所说的空移动。相反，当不活动时，机器人是空闲的。所有机器人最初都是不活动的。完成一个完整LCM周期的时间量被假设为有限但不可预测。174M.ASYN CFSYN CFSYN C3ASYN CO（1）并不比 FSYN C更强大在本节中，我们定义了一个分布式问题，即模式序列追踪（PSC）问题，并证明它可以在O（1）中解决，但不能在O（1）中解决。PSC问题可以被认为是在[7]中定义的模式序列形成问题的变体，其中：i）在[ 7 ]中没有模式重复。提供的序列; ii）机器人移动的图形，而不是一个欧几里德平面。问题定义如下：作为输入，我们考虑一组k个机器人，放置在一个非匿名的无向完全图G上（即G的每个节点都与一个唯一的标识符相关联），以及一个n维数组A，其条目是成对的不同模式。模式P是G的节点的k个不同标识符的有序阵列，其表示k个机器人在标识的节点上的放置通过P. 最初，根据模式A[0]来布置机器人。 随后，委员会注意到，k个机器人必须移动以形成图案A[1]，等等，从图案A[i]移动到图案A[（i+1）modn]，例如参见图2。请注意，由于机器人是相同的和匿名的，假设G的节点可以被唯一识别，这对问题的可行性至关重要。事实上，在匿名图中，如果两个机器人占据同一个节点，那么对手可以使两个机器人总是同时移动。这样，他们将永远不会到达不同的目的地，因此问题变得无法解决。为了简单起见，我们认为A有有限个大小n。因此，不失一般性，要求机器人从模式A[imodn]移动到模式A[（i+1）modn]。在本文的其余部分，我们用A[i][j]表示模式A[i]的第j个条目。模式序列追踪（PSC）问题输入：一个非匿名无向完全图G。一个由n个模式组成的数组A，每个模式涉及G的k个节点，使得A[i]/=A[j]，对于每一个0≤i/=j n。一组k个机器人在G中形成A[0]。解决方案：一种分布式算法，确保机器人形成模式A[（i+1）]modn]，i∈ N.在下文中，我们提供了一种算法，即算法PatternChaser（参见算法1），它通过利用由数组A的条目定义的序列中当前模式的唯一性来求解PSC。该算法如下工作：在每个注视阶段，每个机器人感知位置的快照s图的节点的ID）。这种快照对应于序列中的某个图案A[i]，其可以通过扫描A容易地找到（最初快照明显等于A[0]）。然后，给定A[i]，每个机器人通过顺序扫描它，将他所处的图的节点id（比如v）与A[i]中的节点id进行比较。最终，每个机器人找到索引j，使得A[i][j] =v，并且可以执行从位置A[i][j]到位置A[（i+1）mod n][j]的移动。M.175//ASYN CASYN C算法1在FSYN C下求解PSC的算法。一曰： 程序PatternChaser（快照）d在查看阶段采集的快照inti = 0;3：whileA[i]=sdo4：i++;5：结束时6：让我的p是我在模式A[i]中的位置;0=0;8：whilemyp=A[i][j]do9：j++;10：结束时11：新位置是A[（i+1）modn][j];十二： 结束程序定理3.1算法 PatternChaser正确 解决 PSC问题FSYNC.由于机器人是完全同步的，每次新的Look-Compute-Move循环开始时，所有机器人都会感知到相同的快照s（开始时，s等于A[0]）。因此，在每个计算阶段，每个机器人可以：i）在序列A中唯一地找到当前模式，比如A[i]; ii）在数组A[i]中找到索引j，使得A[i][j]与其位置匹配。由于所有这些条目都是不同的，它们中的每一个都唯一地定义了机器人在后续步骤中应该放置的下一个位置，即数组A[（i+1）modn]的第j个条目，即A[（i+1）modn][j]。移动是通过让所有机器人同时移动以到达所需的位置来完成的。Q相反，一般来说，在O （1 ）下操作不允许解决PSC，除非提供的灯的数量是O（n），这不一定是常数。定理3.2 在ASYN C O（1）中无法解决PSC问题。证明为了证明这一说法，我们必须证明至少有一种情况，其中恒定数量的灯不指向机器人以推断当前模式A[i]，因此移动到正确的后续模式A[（i+1）modn]。特别是，我们证明了任何算法都需要机器人配备一定数量的灯，这些灯相对于输入数组A的大小n不是常数，从而使问题在O （1 ） 中 不 可 解。事实上，如果灯的数量允许对当前索引i进行编码，则机器人可以使其自身同步以从A [ i ]获得A[（i+1）modn]。为了证明这种说法对k机器人的一般情况是正确的，我们使用了一个可以很容易地扩展到更高维度的例子。作为输入，我们考虑一组k=3的机器人，一个非匿名的完全图G=（V，E），其中V={v1，...，v7}和模式A的序列（其一部分在图2中示出）。我们176M.O（1）vASYN CvvvvvvvvΣ Σ ΣΣΣΣΣΣΣΣΣ Σ ΣΣΣΣΣΣA[0] A[1] A[2] A[3] A[4]1 4v2→v5v3v61→v5v34→v2v31→v2v6A[5] A[6] A[7] A[8]···4 1v5→v5v3v64→v2v61→v5v7→···图2.在ASYNCO（1）中无法通过k= 3发光机器人求解的实例的示例现在表明，这种情况下的PSC不能解决异步机器人配备了恒定数量的灯。让我们假设，在步骤i=0，3个机器人被正确地放置在输入图G上，即，它们中的每一个都精确地位于所需模式的节点之一，比如A[0]={v1，v2，v3}，如图2所示。从A[0]机器人必须移动到A[1]。灯光不允许所有机器人同时移动，并且假设灯光不支持索引i。关于机器人从A[0]的运动，可能出现三种情况：（i）所有机器人都运动;(ii)只有一个机器人移动;（iii）只有两个机器人移动。 在情况（i）中，正确地达到配置A[1]。 在（ii）情况下，可以达到配置A[2]、A[3]或A[4]。 在情况（iii）中，可以达到配置A[5]、A[6]或A[7]因此，如果机器人不能编码索引i，那么在某些情况下，它们可能会对必须实现的模式感到“困惑”。灯光可以用来推断是否所有的机器人都移动了。然而，例如，根据模式A[6]，第三个机器人不足以知道其他两个机器人已经移动，以便理解先前的模式是A[1]还是A[7]。克服这种限制的一种可能的方法是使用移动来中介模式，这可以帮助推断目标模式。然而，这种方法也不是有效的。事实上，由于对A的大小n没有限制，我们可以认为A由所有可能的模式组成，因此每个中间模式与A的一个条目重合。 同样，机器人可能会必须实现哪种模式。Q如上述定理的证明所示，PSC问题不能在O（1）中解决，因为没有办法通过利用恒定数量的灯或机器人的一些战略定位来编码当前配置。然而，如果我们假设机器人也被赋予能够存储一个快照的恒定持久存储器，那么当前模式的索引可以从快照中推导出来，因此可以陈述以下推论推论3.3问题P SC可在A SYNCO（1）中求解.M.177类似于上面的推论，如果我们增加灯的数量以足以编码当前模式的索引，而不是添加持久存储器，则可以陈述以下推论推论3.4 PSC问题可以在ASYN C O（log n）中解决。4FSYN C并不比 ASYN CO更强大（1）在本节中，我们定义了一个分布式问题，即Forth and Back（FB）问题，并证明它可以在ASYN CO（1）中解决，但不能在FSYN C中解决。Forth and Back（FB）问题输入：两个机器人，分别命名为r1和r2，以及一个图G，它是一条路径P，至少6个节点。这两个机器人位于P的不同节点，它们既不是P的端点，也不是P的端点的邻居。 设d为两个机器人之间的初始距离，即边缘数解决方案：一种分布式算法，确保机器人在d+2和d之间交替移动距离。FB问题与我们之前的PSC问题有一些相似之处，但是模式（距离）的序列不是根据节点的id定义的，而是根据机器人总是开始躺在不同内部节点的初始配置来定义的。此外，请注意，在这种情况下，图被假设为匿名的。定理4.1问题FB不能在FSYN C中解决。每当一个“看-计算-移动”循环开始时，机器人无法推断出必须扩大或限制当前距离。事实上，这些信息需要知道机器人已经执行了多少次运行周期，或者至少知道这个数字是奇数还是偶数。这些信息根本无法从在观察阶段期间获取的快照Q在下文中，我们提供了一种算法，即算法ForthBack（参见算法2），该算法假设机器人被赋予两种不同的光，每种光假设两种不同的颜色。算法2使用白色、黑色作为光1，使用红色、蓝色作为光2，具有以下含义：• 白色：表示机器人已准备好进行下一步;• 黑色：表示机器人已经移动，准备进行下一步;• 红色：表示必须增加前一距离的偶数步;• 蓝色：表示必须减少前一距离的奇数步。一开始，两个机器人都将灯光设置为白色和红色。 正如我们将看到的，算法ForthBack确保，当两个机器人的第一个光设置为白色时，它们也有第二个光一致，这意味着它们当前是同步的。也就是说，算法2通过下式求解ASYN CO（1）中的FB：178M.∧∧∧∧−利用光对当前步骤进行奇偶校验编码。当然，同样的结果也可以通过只使用一个光假设四种不同的颜色来获得。算法2ASYN CO（1）下求解FB的算法。1：为未获取的另一个机器人的Back（颜色l1J和l2J）d灯提供保护在查看阶段2：让l1和l2为我的两个灯的当前颜色3：设d是来自另一机器人的边的数量4：如果l1=白色l2=红色l2J5：l1：=黑色;=红色然后6：设v是距离另一个机器人d+1的邻居7：新位置为v;8：退出;9：如果结束10：如果l1=白色l2=蓝色l2J11：l1：=黑色;=蓝色然后12：设v是与另一个机器人距离为d1的邻居13：新位置为v;14：退出;15：如果结束16：如果l1=black，则l2=redk（（l1J=白色l2J=blue）（l1J=黑色l2J=red）），则17：l1：=白色;18：l2：=蓝色;19：退出;20：如果结束21：如果l1=black，则l2=blue，则（（l1J=白色l2J=red）（l1J=黑色l2J=蓝色）），然后22：l1：=白色;23：l2：=红色;24：退出;25：如果结束二十六： 结束程序定理4.2算法ForthBack正确地解决了FB问题，ASYNC O（1）.设r1（r2）的配体分别记为l1，l2（l1j，l2j）. 如果l1是白色的，那么r1准备完成一个移动，它要么必须扩大前一个放置的距离，要么限制它。这分别取决于l2是红色还是蓝色。 此外，为了了解正确在示例NT中，R1还考虑R2的两条线，即L1J和L2J。如果它们相同，即l1=l1J和l2=l2J，则这是机器人当前同步化。若l1=L1J=black且l2与L2J不一致，则r1M.179ASYN CFSYN C等待R2以便与其同步。如果l1J是black且l2=l2J，则r1断定r2已经移动，所以现在轮到它了。要做的移动是根据r2的当前灯光进行评估的。详细地说，如果l2是红色的，那么r1必须远离一边的r2事实上，正如我们所注意到的，r2已经终止了它的运动。因此，它在等待r1。如果d是两个机器人移动之前两个机器人之间的距离，那么d+2必须定义两个机器人在当前步骤中的最终位置由于它们都贡献一个边缘，当只有一个机器人移动时，当前距离DJ为DJ=d+1，因此，通过移动一个边缘，两个机器人将达到距离d+2。类似地，如果l2是蓝色的，则r1必须移动到更靠近一边的r2最后，如果l1是黑色的，那么r1已经终止了一个步骤，它必须开始下一个步骤，或者它必须等待r2，以便暂时与了 这是通过考虑r2的光来实现的。如果L1J是白色的，并且l2j=L2J，则r1c将l1变为白色，l2变为l2j。如果L1J是白的，l2=L2J，那么r1必须是白的对于R2，移动到E。如果L1J是black且l2=L2J，则r1c将l1变为white且makesl2与l2j不一致。 l1J是blac且l2j=l2J的情况不成立. 这实现了机器人之间的同步。Q5结论我们已经证明了在基于机器人的计算系统中研究的两个重要模型的不可比性。特别是，我们已经考虑过，其中所有机器人同步执行其算法，并且O （1 ），其中机器人是异步的，但它们被赋予恒定数量的灯。通过提供两个不同的机器人在内部移动的分布式任务，一个图形环境，并表明一个任务可以解决在FSYN C，但不是在ASYN CO（1），而对于另一个，反之亦然。机器人在欧几里德平面上运动的情况仍然是开放的。事实上，定理3.1、4.1和4.2的论证可以很容易地扩展，在Euclidean的情况下也是如此。主要的挑战仍然是定理3.2，其中困难主要在于证明污名策略不能有效。也就是说，在欧几里德平面中，机器人可以计算中间位置，而不是直接向由当前模式指示的位置移动。 这开辟了具有挑战性的方向，以了解哪些特点使FSYN C和ASYN CO（1） 如此不同的模式。另一个有趣的方向是，当机器人在图形环境中移动时，重新审视图1引用[1] Chatterjee，A.，S. G. Chaudhuri和K.Mukhopadhyaya，在非均匀有限可见度下收集异步群机器人 ， 在 ： 第 11 届 分 布 式 计 算 和 互 联 网 技 术 国 际 会 议 （ ICDCIT ） ， 计 算 机 科 学 讲 义 8956（2015），pp.174-180。[2] Cicerone，S.，G. Di Stefano和A. Navarra，在给定的会议点上遗忘机器人的最小行进距离聚集，在：第10届传感器180M.系统，无线网络和分布式机器人（ALGOSENSORS），计算机科学讲义8847（2014年），pp。57比72[3] Cicerone，S.，G. Di Stefano和A.Navarra，给定集合点的最小距离聚集，在：第九届算法和复杂性国际会议（CIAC），计算机科学讲义9079（2015），pp.127比139[4] Czyzowicz ， J. ， A. Kosowski 和 A. Pelc ， How to Meet When You Forget ： Log-Space Rendezvous inArbitrary Graphs，Distributed Computing25（2012），pp. 165-178[5] D'Angelo，G.，G. Di Stefano和A. Navarra，Gathering on Rings under the look-compute-move model，Distributed Computing27（2014），pp. 255-285[6] 达 斯 ， S. ， P. Flocchini ， G. Prencipe ， N. Santoro 和 M. Yamashita ， The Power of Lights ：Synchronizing Asynchronous Robots Using Visible Bits ， 第 32 届 IEEE 分 布 式 计 算 系 统 国 际 会 议（ICDCS），2012年，第32页。506-515[7] 达 斯 ， S.， P. Flocchini， N. Santoro 和 M. Yamashita ， On the computational power of obliviousrobots ： Forming a series of geometric patterns ， in ： 29th ACM SIGACT-SIGOPS Symposium onPrinciples of Distributed Computing（PODC）（2010），pp. 267-276。[8] Degener，B.，B. Kempkes，T.Langner，F.Meyer auf der Heide，P.Pietrzyk和R.Wattenhofer，一个严格的运行时约束，用于同步收集自主机器人，能见度有限，在：第23届ACM研讨会。算法和架构中的并行性（SPAA），2011年，pp. 139-148。[9] D’Emidio, D. Frigioni 和 A.Navarra ， Exploring and making safe dangerous networks using mobileentities，in：12th International Conference on Ad Hoc Networks and Wireless（ADHOC-NOW），Lecture Notes in Computer Science7960（2013），pp.136-147。[10] Devismes，S.，F. Petit和S. Tixeuil，半同步遗忘机器人的最佳概率环探索，在：第16届结构信息和通信复杂性国际学术讨论会（SIROCCO），计算机科学讲义5869，2009年，第16页。195-208.[11] Di Stefano，G.和A. Navarra，在无限网格上以最小旅行距离收集遗忘机器人，信息和计算。出现。[12] Di Stefano，G.和A. Navarra，匿名图中遗忘机器人的最佳收集，在：第20届结构信息和通信复杂性国际学术讨论会（SIROCCO），计算机科学讲义8179，2013年，pp.213-224。[13] Di Stefano，G.和A.Navarra，无限网格上的最佳聚集，在：Proc. 第十六届国际Symposium on Stabilization，Safety，and Security of Distributed Systems（SSS），Lecture Notes inComputer Science8756，2014，pp. 211-225[14] Dieudonné，Y.，A. Pelc和D.Peleg，尽管恶作剧，ACM算法交易11（2014），p. 1.一、[15] Dobrev ，S.，P. Flocchini ，R. Královic 和N. Santoro ，Exploring an unknown dangerous graph usingtokens，Theoretical Computer Science472（2013），pp. 28比45[16] Flocchini，P.，D. Ilcinkas，A. Pelc和N. Santoro，Remembering without Memory：Tree exploration byasynchronous oblivious robots，Theoretical Computer Science411（2010）. 1583-1598年。[17] Flocchini ， P. ， D. Ilcinkas ， A. Pelc 和 N. Santoro ， Computing without communicating ： Ringexploration by asynchronous oblivious robots，2013年，第65页。562-583.[18] Flocchini ， P. ， D. Ilcinkas ， A. Pelc 和 N. Santoro ， Computing without communicating ： Ringexploration by asynchronous oblivious robots，2013年，第65页。562-583.[19] Flocchini，P.，G. Prencipe和N. Santoro，Distributed Computing by oblivious mobile robots，SynthesisLectures on Distributed Computing Theory3（2012），pp. 1-185[20] Flocchini，P.，G. Prencipe，N. Santoro和P. Widmayer，《具有有限可见度的异步机器人的聚集》，理论计算机科学337（2005），第100页。147-168.[21] Fujinaga，N.，Y. Yamauchi，S. Kijima和M. Yamashita，匿名遗忘移动机器人的异步模式形成，在：分布式计算，计算机科学讲义7611，Springer，2012页。312-325[22] Kamei，S.，A. Lamani，F. Ooshita和S. Tixeuil，在没有全局多重性检测的情况下，在奇数环中收集偶数个机器人，在：计算机科学的数学基础（MFCS），Springer，2012页。542-553.