无限规则平铺图上的任意模式形成

Serafino Cicerone$^1$, Alessia Di Fonso$^1$, Gabriele Di Stefano$^1$, Alfredo Navarra$^2$

$^1$ Dipartimento di Ingegneria e Scienze dell’Informazione e Matematica, Università degli Studi dell’Aquila, I-67100 L’Aquila, Italy. {serafino.ciceron, alessia.difonso, gabriele.distefano}@univaq.it

$^2$ Dipartimento di Matematica e Informatica, Università degli Studi di Perugia I-06123 Perugia, Italy. alfredo.navarra@unipg.it

---

摘要

给定一组位于无限规则平铺图不同顶点上的机器人 $R$，我们旨在探索任意模式形成（Arbitrary Pattern Formation, $APF$）问题。给定一个网格顶点的多重集 $F$，使得 $|R| = |F|$，$APF$ 要求设计一种分布式算法，通过移动机器人以达到与 $F$ 相似的配置。相似性意味着机器人必须按照 $F$ 的布局进行排列，而不考虑平移、旋转和反射。

迄今为止，在经典的“观察-计算-移动”（Look-Compute-Move, LCM）模型背景下，作为欧几里得平面的离散化图，仅考虑了标准方格网。然而，考虑其他规则平铺图（即三角形网格和六边形网格）也是很自然的。我们提供了一种针对 $APF$ 的解析算法，适用于初始配置为非对称且拓扑结构为任意规则平铺图的情况。

关键词： 分布式算法 · 移动机器人 · 异步性 · 模式形成 · 图

---

1 引言

在本文中，我们通过在图上移动的一群能力非常弱的机器人来考虑任意模式形成（$APF$）任务。最初，每个机器人占据图中的不同顶点。该任务要求一种分布式算法，允许一组自主移动机器人形成作为输入给出的任何特定但任意的几何模式。模式形成任务是基于机器人的计算系统背景下广泛研究的基本原语之一。

移动机器人系统能否解决给定问题通常取决于对机器人能力的假设。分布式计算中的一种常见方法是检测执行基本任务所需的最小能力。这种方法的理由有两个：回答最小化问题在理论上很有趣；假设解决任务的模型越弱，其适用性就越广，包括那些容易出错的更强大的机器人。

1.1 机器人模型

在本文中，机器人被认为是：

• 匿名（Anonymous）：没有唯一标识符；
• 自主（Autonomous）：没有集中控制；
• 无量纲（Dimensionless）：没有占用约束，没有体积，被建模为位于图顶点上的实体；
• 遗忘（Oblivious）：对过去事件没有记忆；
• 同质（Homogeneous）：它们都执行相同的确定性算法；
• 沉默（Silent）：没有直接通信手段；
• 无定向（Disoriented）：没有公共坐标系，没有公共的左右方向；

系统中的每个机器人都有感知能力，允许它确定图中其他机器人相对于其自身位置的位置。事实上，每个机器人参考一个可能因机器人而异的局部坐标系（Local Coordinate System, $LCS$）。每个机器人遵循预编程到机器人中的相同算法。每个机器人的行为可以根据四个状态的序列来描述：等待（Wait）、观察（Look）、计算（Compute）和移动（Move）。这些状态构成了机器人的计算周期（或简称周期）。

1. 等待（Wait）：机器人处于空闲状态。机器人不能无限期地保持空闲。
2. 观察（Look）：机器人通过激活其传感器来观察环境，传感器将返回相对于其 $LCS$ 的所有其他机器人的位置快照。每个机器人被视为一个点。因此，快照（即观察结果）的结果只是其 $LCS$ 中的一组坐标。
3. 计算（Compute）：机器人根据确定性算法 $\mathcal{A}$ 执行局部计算（我们也说机器人执行 $\mathcal{A}$）。该算法对所有机器人都是相同的，计算阶段的结果是一个目标点以及到达该点的路径。
4. 移动（Move）：如果目标点是 $r$ 当前所在的顶点，$r$ 执行零移动（即它不移动）；否则，它移动到沿计算路径选择的相邻顶点。

当机器人处于等待状态时，我们称其为非活动的（inactive），否则为活动的（active）。在文献中，计算周期简称为“观察-计算-移动”（$LCM$）周期，因为在等待阶段机器人是非活动的。最初机器人是非活动的，但一旦算法 $\mathcal{A}$ 的执行开始——除非另有说明——就没有指令停止它，即防止机器人进入它们的 $LCM$ 周期。那么，$\mathcal{A}$ 的终止属性可以表述如下：一旦机器人通过 $\mathcal{A}$ 达到了所需的目标，从那时起机器人只能执行零移动。

在观察阶段，机器人可以感知多重性（multiplicities），即同一个点是否被多个机器人占据。多重性检测能力可以是局部的或全局的，取决于多重性是仅由构成多重性的机器人检测到，还是由执行观察阶段的任何机器人检测到。此外，多重性检测可以是弱的或强的，取决于机器人是只能检测到多重性的存在，还是能感知构成多重性的机器人确切数量。在这项工作中，我们假设每个机器人都被赋予了全局强多重性检测。

关于移动，在图环境中，移动总是被认为是瞬时的。这导致在观察阶段总是感知到顶点上的机器人，而从不在边上。因此，机器人不能在移动时被看到，而只能在它们可能开始移动的时刻或它们到达时被看到。这种假设的理由是图可以模拟通信网络，而机器人模拟软件代理。

我们假设周期是根据最弱的异步调度器（$Async$）（参见 [1,6,8,9,14,19,20]）执行的：机器人被独立激活，每个阶段的持续时间是有限但不可预测的（每个机器人的激活可以被认为是对手决定的）。因此，机器人没有共同的时间概念。此外，根据观察阶段的定义，机器人无法感知其他机器人是否在移动。因此，机器人可能会基于过时的感知进行移动。事实上，由于异步性，当机器人拍摄配置快照时，一旦机器人开始移动，配置可能已经发生了巨大变化。确定周期时间的调度器被认为是公平的，即每个机器人在有限时间内且无限次地变得活跃并执行其周期。图 1 比较了 $Async$ 调度器与文献中提出的其他调度器。在图中，等待状态隐含地由机器人非活动的时间段表示。特别是，它表明在全同步（$FSync$）调度器中，所有机器人总是活跃的，并且激活阶段可以在逻辑上划分为全局轮次：对于所有 $i \ge 1$，所有机器人同时开始第 $i$ 个 $LCM$ 周期并同步执行每个阶段。

半同步（$SSync$，参见 [23,24,25]）调度器与 $FSync$ 模型一致，唯一的区别是某些机器人可能不会为某些 $i$ 开始第 $i$ 个 $LCM$ 周期（某些机器人可能处于等待状态），但所有已经开始第 $i$ 个周期的机器人都同步执行每个阶段。

半异步（$SAsync$，参见 [7]）仍然保持一种同步行为，因为每个阶段持续相同的时间，但机器人可以在不同的时间开始它们的 $LCM$ 周期。因此，当一个机器人正在执行观察阶段时，其他活跃的机器人可能正在执行计算或移动阶段。

显然，这四个同步调度器诱导了以下层次结构（参见，例如 [7,13,15]）：$FSync$ 机器人比 $SSync$ 机器人更强大（即它们可以解决更多任务），后者又比 $SAsync$ 机器人更强大，后者又比 $Async$ 机器人更强大。这仅仅通过观察到对手在 $Async$ 中比在 $SAsync$ 中控制更多的参数，而在 $SAsync$ 中比在 $SSync$ 和 $FSync$ 中控制更多的参数得出。换句话说，为 $Async$ 机器人设计的协议也适用于 $SAsync$、$SSync$ 和 $FSync$ 机器人。相反，为 $FSync$ 机器人陈述的任何不可能性结果也适用于 $SSync$、$SAsync$ 和 $Async$ 机器人。

在 $Async$ 调度器中，机器人的激活决定了特定的有序时间点。令 $C(t)$ 为某些机器人在时间 $t$ 在其观察阶段观察到的配置，令 $\{t_i : i = 0, 1, \dots\}$，其中 $t_i < t_{i+1}$，为至少一个机器人拍摄快照 $C(t_i)$ 的所有时间实例的集合。由于每个机器人的计算阶段的相关信息是不同快照发生的顺序，而不是拍摄每个快照的确切时间，因此在不失一般性的情况下，我们可以假设对于所有 $i = 0, 1, \dots$，$t_i = i$。那么，算法 $\mathcal{A}$ 从初始配置 $C$ 开始的执行是配置序列 $E : C(0), C(1), \dots$，其中 $C(0) = C$，并且 $C(t+1)$ 是通过根据 $\mathcal{A}$ 实现的计算阶段的结果移动某些机器人而从 $C(t)$ 获得的。注意，此执行定义也适用于其他调度器。此外，给定算法 $\mathcal{A}$，在 $Async$（以及 $SAsync$ 和 $SAsync$）中，根据机器人的激活（取决于对手），从 $C(0)$ 开始存在不止一种执行。

1.2 相关工作

对于在欧几里得平面上移动的机器人，$APF$ 的一个受限版本首先在 [17] 中得到解决。事实上，所提出的算法至少需要 $n \ge 4$ 个具有手性（chirality）的异步机器人，即机器人共享一个共同的惯用手。此外，可能的模式排除了形成多重性的可能性。对 $APF$ 的这种受限设置的回答提供了一个很好的问题表征，该表征被证明等同于同一组假设下的领导者选举（Leader Election）。特别是，所提出的算法可以输出任何模式（没有多重性）的配置是所谓的领导者配置。这些是机器人配置（包括一些对称配置），从中可以选举出领导者。在 [4,26] 中可以找到消除这些限制的尝试，但使用了随机化技术。相反，在 [8] 中，$APF$ 通过确定性算法得到解决，没有手性并允许存在多重性。在 [3,18] 中可以找到关于欧几里得平面中 $APF$ 的进一步研究，涉及略有不同的模型。值得一提的是，当模式允许存在多重性时，点形成（又名聚集，Gathering）的退化情况被包含在 $APF$ 中。实际上，聚集任务已在 [11] 中得到充分表征。它构成了一个值得主要关注的非常特殊的情况。

对于在图上移动的机器人，特别是在无限方格网上的机器人，$APF$ 最近在 [2] 中得到解决。初始配置被假定为非对称的，并且允许的模式不包含多重性。因此，到目前为止考虑的 $APF$ 不包括聚集。无限或有限方格网上的聚集已在 [12,16] 中得到充分表征，同时也考虑了总移动距离的最小化。

1.3 我们的结果

我们对图上 $APF$ 的研究始于考虑也允许模式中存在多重性的方格网。然后我们意识到，该问题的自然扩展是考虑任何规则平铺图作为欧几里得平面的离散化，即三角形和六边形网格也值得研究。特别是，后者可以被认为是就可能的对称性和轨迹而言最通用的拓扑结构。在本文中，我们通过提供一种独特的算法，解决了包括多重性在内的所有三种规则平铺上的 $APF$ 问题。该算法首先在初始配置为非对称时针对三角形网格进行了详细描述。我们遵循正式的设计和分析来提供我们的算法，以及正确性证明。为此，我们使用了 [10] 中提出的设计方法。此外，我们重新审视了针对方格网和六边形网格的算法，指出了针对特定拓扑结构所需的任何可能的偏差。

1.4 大纲

本文组织如下。下一节首先正式定义了所解决的问题，然后介绍了所提供的算法 $\mathcal{A}_{form}$ 使用的符号。第 3 节提供了 $\mathcal{A}_{form}$ 的高层描述，同时也强调了算法背后的策略。第 4 节将算法形式化并提供了正确性。由于所有细节都是针对三角形网格给出的，在第 5 节中，我们重新审视了针对方格网和六边形网格的算法。第 6 节通过强调一些最终评论来结束本文。

---

2 问题定义和基本符号

机器人放置的拓扑结构由一个简单的、无向的、连通的图 $G = (V, E)$ 表示，具有顶点集 $V$ 和边集 $E$。函数 $\lambda : V \to \mathbb{N}$ 表示 $G$ 每个顶点上的机器人数量，只要 $\sum_{v \in V} \lambda(v)$ 有界且大于零，我们就称 $C = (G, \lambda)$ 为一个配置。满足 $\lambda(v) > 0$ 的顶点 $v \in V$ 被称为被占据的，否则为未被占据的。多重性发生在任何满足 $\lambda(v) > 1$ 的顶点 $v \in V$ 上。

2.1 平铺图上的配置

在这项工作中，我们将 $G$ 视为由平面平铺生成的无限图。平铺是用多边形对平面进行无重叠的覆盖。规则平铺是一种仅由一种边长为 1 的规则多边形形成，且多边形角排列相同的平铺。根据 [21]，只有三种规则平铺，它们由正方形、等边三角形或正六边形生成（见图 2）。规则平铺的无限晶格是通过将平铺中规则多边形的顶点作为晶格点而形成的晶格。图 $G$ 由点集 $S$ 诱导，如果 $G$ 的顶点是 $S$ 中的点，并且其边连接距离为 1 的顶点。规则平铺的平铺图是嵌入欧几里得平面中，由该平铺形成的无限晶格诱导的无限图 [22]。我们用 $G_S$（分别为 $G_T$ 和 $G_H$）表示由正方形（分别为等边三角形和正六边形）生成的规则平铺诱导的平铺图。在这项工作中，我们考虑配置 $C = (G, \lambda)$，其中 $G \in \{G_S, G_T, G_H\}$。

定义 1. 给定图 $G \in \{G_S, G_T, G_H\}$，任何平行于 $G$ 边子集的线称为规范方向。由可用规范方向形成的最小角度称为规范角。

根据定义 1，在 $G_S$ 中只有两个规范方向，规范角为 $90^\circ$。在 $G_T$ 和 $G_H$ 中都有三个规范方向，规范角为 $60^\circ$。

2.2 配置自同构和对称性

两个无向图 $G = (V, E)$ 和 $G' = (V', E')$ 是同构的，如果存在从 $V$ 到 $V'$ 的双射 $\phi$，使得 $\{u, v\} \in E$ 当且仅当 $\{\phi(u), \phi(v)\} \in E'$。图 $G$ 上的自同构是从 $G$ 到其自身的同构，即 $G$ 顶点的排列，将边映射到边，非边映射到非边。在复合运算下，$G$ 的所有自同构集合形成一个群，称为 $G$ 的自同构群，记为 $Aut(G)$。如果 $|Aut(G)| = 1$，即 $G$ 仅承认恒等自同构，则称 $G$ 是非对称的，否则称其为对称的。如果存在自同构 $\phi \in Aut(G)$ 使得 $\phi(u) = v$，则两个不同的顶点 $u, v \in V$ 是等价的。

图自同构的概念可以自然地扩展到配置：(1) 两个配置 $C = (G, \lambda)$ 和 $C' = (G', \lambda')$ 是同构的，如果 $G$ 和 $G'$ 通过自同构 $\phi \in Aut(G)$ 同构，并且对于 $G$ 中的每个顶点 $v$，$\lambda(v) = \lambda'(\phi(v))$；(2) 配置 $C = (G, \lambda)$ 的自同构是从 $C$ 到其自身的同构，以及 (3) $C$ 的所有自同构集合在复合运算下形成一个群，我们称之为 $C$ 的自同构群，记为 $Aut(C)$。此外，如果 $|Aut(C)| = 1$，我们说 $C$ 是非对称的，否则它是对称的。配置 $(G, \lambda)$ 中的两个不同机器人 $r$ 和 $r'$ 是等价的，如果存在 $\phi \in Aut(C)$ 使得它们所在的顶点等价。注意，只要 $u$ 和 $v$ 等价，$\lambda(u) = \lambda(v)$。此外，如果 $u$ 和 $v$ 等价，机器人 $r$ 无法将其在顶点 $u$ 的位置与位于顶点 $v = \phi(u)$ 的机器人 $r'$ 区分开来。因此，没有任何算法可以区分两个等价的机器人。

通常，没有任何算法可以避免两个等价的 $Async$ 机器人同时开始计算周期。在这种情况下，可能会出现所谓的挂起移动（pending move）或挂起机器人（pending robot），即其中一个机器人执行其整个计算周期，而另一个尚未开始或尚未完成其移动阶段。形式上，如果机器人 $r$ 在配置 $C(t)$ 中是活跃的，拍摄了快照 $C(t') = C(t)$（其中 $t' < t$），并且正计划移动或正在以非零轨迹移动，则称机器人 $r$ 在配置 $C(t)$ 中是挂起的。显然，任何其他机器人 $r'$ 都不知道是否存在挂起机器人 $r$，即它无法从观察阶段获取的快照中推断出此类信息。这一事实极大地增加了为对称配置设计算法的难度。注意，如果算法总是产生平稳配置，所有这些困难都会被完全消除：如果 $C(t)$ 中没有挂起机器人，则配置 $C(t)$ 被称为平稳的。产生平稳配置的一种方法是保证算法一次只移动一个机器人。

关于这项工作中考虑的配置，不难看出任何 $C = (G, \lambda)$（其中 $G \in \{G_S, G_T, G_H\}$）仅承认两种类型的自同构：反射（由作为镜子的反射轴定义）和旋转（由旋转中心和旋转角度定义）。所有反射轴分为两类：所考虑的规则多边形的反射轴和与规则多边形任何边重合的反射轴。可能旋转的中心只能位于规则多边形的特定点上：中心、一个顶点或一边的中点。旋转角度是每个给定平铺图特有的。

2.3 任意模式形成（$APF$）问题

配置 $C = (G, \lambda)$（其中 $G = (V, E)$）是初始的，如果满足以下两个条件：(1) 每个机器人都是空闲的并放置在不同的顶点上，即对于每个 $v \in V$，$\lambda(v) \le 1$；(2) $C$ 是非对称的。包含所有初始配置的集合记为 $\mathcal{I}$。

$APF$ 问题的目标是设计一种分布式算法 $\mathcal{A}$，引导机器人从任何配置 $C = (G, \lambda)$（其中 $G \in \{G_S, G_T, G_H\}$ 且 $C \in \mathcal{I}$）开始形成固定的任意模式 $F$。模式 $F$ 是顶点的多重集，以任何坐标系给出，指示平铺图 $G$ 中的相应目标顶点。它构成了所有机器人的输入。由于缺乏公共全局坐标系，机器人决定当当前配置相对于平移、旋转、反射变得与 $F$ “相似”时，模式就形成了。该问题可以形式化如下：算法 $\mathcal{A}$ 为初始配置 $C$ 解决了 $APF$ 问题，如果对于 $\mathcal{A}$ 的每个可能的执行 $E : C = C(0), C(1), \dots$，存在一个有限时间点 $t^* > 0$，使得 $C(t^*)$ 与 $F$ 相似，并且在 $t^*$ 之后没有机器人移动，即对于所有 $t \ge t^*$，$C(t) = C(t^*)$ 成立。

2.4 符号

这里我们介绍用于描述所提算法的一些概念和符号。给定配置 $C = (G, \lambda)$，我们使用 $R = \{r_1, r_2, \dots, r_n\}$ 来表示包含位于 $G$ 上的所有 $n$ 个机器人的集合（我们回想一下机器人是匿名的，这种符号仅用于演示目的）。两个顶点 $u, v \in V$ 之间的距离 $d(u, v)$ 是连接 $u$ 到 $v$ 的最短路径的边数。我们将距离的概念扩展到机器人：$d(r_i, r_j)$ 表示机器人所在的两个顶点之间的距离。符号 $D(r)$ 用于表示 $r \in R$ 与任何其他机器人的距离之和，即 $D(r) = \sum_{r_i \in R \setminus \{r\}} d(r, r_i)$。

给定平面上的一组点 $P$，$mbr(P)$ 表示 $P$ 的最小边界矩形，即包围 $P$ 中所有点的矩形，定义如下：其边平行于笛卡尔轴，并且每对平行边尽可能靠近。根据定义，我们得到 $mbr(P)$ 是唯一的。这个定义可以很容易地扩展到放置在平铺图 $G_S$ 上的机器人集合 $R$，其中规范方向只有两个，它们可以自然地扮演笛卡尔轴的角色。不幸的是，当 $R$ 放置在诸如 $G_T$ 或 $G_H$ 之类的平铺图上时，它不起作用。为了概括它，我们转向边界平行四边形 $bp(R)$ 的概念，定义为包围所有机器人的任何平行四边形，其边平行于三个可用规范方向中的两个，并且每对平行边尽可能靠近。由于 $G_T$ 或 $G_H$ 承认三个规范方向，可以观察到 $R$ 的边界平行四边形不是唯一的。事实上，有三种可能的边界矩形（例如，见图 3）。

给定任何 $bp(R)$，我们用 $h(bp(R))$ 和 $w(bp(R))$（其中 $h(bp(R)) \le w(bp(R))$）分别表示 $bp(R)$ 的宽和高。类似地，$h(bp(F))$ 和 $w(bp(F))$ 用于表示关于 $bp(F)$ 的相同值。

令 $bp(R)$ 为 $R$ 的任何边界平行四边形。我们将整数序列与 $bp(R)$ 的每个规范角相关联（例如，图 3 中的角 $A$ 和 $C$）。与规范角 $A$ 相关的序列定义如下。从 $A$ 沿 $h(bp(R))$（例如，从 $A$ 到 $B$）扫描 $bp(R)$ 包围的有限网格，并按顺序扫描平行于 $AB$ 的所有网格线。对于每个网格顶点 $v$，将 $\lambda(v)$ 放入序列中。将获得的序列记为 $s(AB)$。在示例中，由于 $h(bp(R)) = w(bp(R))$，从 $A$ 也可以获得序列 $s(AD)$，因此总共可以定义四个序列，两个用于角 $A$，两个用于角 $C$。如果其中任何两个序列相等，则意味着该配置承认（反射或旋转）对称性。我们用 $LSS$ 表示字典序最小的序列。它根据定义是唯一的。

$LSS$ 开始的规范角称为引导角（leading corner）；从引导角用于创建 $LSS$ 的规范方向称为引导方向（leading direction）。给定 $bp(R)$ 的 $LSS$ 记为 $\ell(bp(R))$，或者当 $bp(R)$ 可以从上下文中推断出来时简称为 $\ell$。

定义 2. 令 $C = (G, \lambda)$ 为具有 $G \in \{G_S, G_T, G_H\}$ 和机器人集合 $R$ 的配置。最小边界平行四边形 $mbp(R)$ 定义为任何边平行于 $G$ 的两个规范方向、$h(bp(R))$ 最小，且在平局情况下 $LSS$ 最小的平行四边形 $bp(R)$。

任何非对称配置恰好承认一个 $mbp(R)$，而对称配置承认多个 $mbp(R)$。然而，与此类 $mbp(R)$ 相关的 $LSS$ 都是相同的。

---

3 算法描述

在本节中，我们提供算法 $\mathcal{A}_{form}$ 的高层描述，该算法旨在为任何由 $n$ 个 $Async$ 机器人组成的初始配置 $C = (G_T, \lambda)$ 解决 $APF$ 问题，这些机器人被赋予全局强多重性检测以及第 1.1 节中回顾的所有最小能力。我们假设 $n \ge 3$，因为对于 $n = 1$，$APF$ 问题是平凡的，而对于 $n = 2$，我们得到 $C$ 是对称的。关于模式 $F$，它可能包含多重性。

3.1 策略

通常，单个机器人相对于它被要求与其他机器人一起解决的一般问题具有相当弱的能力（我们回想一下机器人没有直接的通信手段）。因此，任何解析算法都应基于初步分解方法：问题应划分为一组子问题，以便每个子问题足够简单，可以被认为是（机器人子集）要执行的“任务”。这种细分可能需要几个步骤才能获得此类简单任务的定义，从而生成一种层次结构。

遵循这种方法，$APF$ 最初被划分为四个子问题，分别称为参考系统（Reference System, $RS$）、部分模式形成（Partial Pattern Formation, $PPF$）、最终化（Finalization, $Fin$）和终止（Termination, $Term$）。其中一些子问题被进一步细化，直到相应的任务可以根据机器人的假设能力适当地形式化。这导致了以下分解：

• 参考系统（$RS$ = 如何在 $G_T$ 上嵌入 $F$）。这个子问题涉及解决一般模式形成问题时出现的主要困难之一：$F$ 在 $G_T$ 上缺乏唯一的嵌入，这使得每个机器人能够唯一地识别其目标（形成模式的最终目标顶点）。特别是，$RS$ 可以描述为将某些（最少数量的）机器人移动或匹配到特定位置的问题，以便它们可以被任何其他机器人用作公共参考系统。这些机器人被称为守卫（guards）。实现的参考系统应暗示从机器人到目标的唯一映射，并且该映射应在机器人的所有移动过程中保持。在我们的策略中，$RS$ 被进一步划分为三个子问题，分别称为 $RS_{1a}$、$RS_{1b}$ 和 $RS_2$。这些子问题足够简单，可以分别与三个任务 $T_1$、$T_2$ 和 $T_3$ 相关联。前两个致力于放置第一个守卫 $r_1$，而第三个固定第二个守卫 $r_n$ 的位置。一旦两个守卫达到这些位置，请求的参考系统就由穿过守卫占据的顶点并形成规范角的两条线给出。当参考系统创建时，除守卫外的所有机器人都位于一个称为 $Q^-$ 的特定象限中。
• 部分模式形成（$PPF$ = 如何形成 $F$ 的一部分）。这个子问题与任务 $T_4$ 相关联，并且仅在 $RS$ 解决后才处理。它涉及通过仅使用 $R'' = R \setminus \{r_1, r_n\}$ 中的机器人形成类似于 $F$ 的一部分的模式。多亏了公共参考系统，所有机器人都可以同意将 $F$ 嵌入到一个称为 $Q^+$ 且不同于 $Q^-$ 的象限中。在任务期间，$R''$ 中的所有 $n-2$ 个机器人将从 $Q^-$ 移动到 $Q^+$。机器人一次移动一个，以便不会产生不必要的碰撞。
• 最终化（$Fin$ = 如何最终移动 $r_1$ 和 $r_n$ 以形成 $F$）。它指的是所谓的最终化任务，发生在唯一没有根据 $F$ 良好定位的机器人是守卫时。值得一提的是，在移动守卫 $r_1$ 和 $r_n$ 时，公共参考系统丢失了。然而，我们能够保证机器人总是可以检测到它们正在解决 $Fin$，并且这两个机器人通过执行特定移动，可以到达它们的目标，从而正确完成模式 $F$。$Fin$ 被划分为三个任务：$T_5$ 涉及 $r_n$ 的移动，而 $T_6$ 和 $T_7$ 与 $r_1$ 的移动有关。
• 终止（$Term$）。它指的是让机器人识别模式已经形成的要求，因此不需要更多的移动。在我们的策略中，设计了一个任务 $T_8$ 来解决这个问题。显然，只允许零移动，并且不可能切换到任何其他任务。

在本节的其余部分，我们提供每个设计任务的详细信息。

---

(注：由于篇幅限制，以上为论文前 8 页的翻译。后续内容将继续按照此格式进行翻译。)