离散与连续域中的群体覆盖研究

### 离散与连续域中的群体覆盖研究 在机器人领域，区域覆盖问题是一个重要的研究方向，尤其是在离散域中，该问题被称为探索问题。下面将详细介绍离散域中区域覆盖问题的相关研究。 #### 离散域中的区域覆盖问题 在离散域里，区域覆盖问题被定义为探索问题，即机器人随机分布在图的顶点上，任务是让机器人在图中移动，使得图的每个顶点至少被一个机器人探索。研究主要分为单机器人探索和多机器人探索两方面。 ##### 单机器人探索 单机器人探索要求机器人遍历图的所有节点和边。相关研究假设机器人具备记忆、方向感等特性，且不遵循CORDA模型。 - **Albers和Henzinger的算法**：用于探索陌生的有向强连通图，机器人具有有限的视野、记忆和方向感。从一个顶点开始，不断探索新边，直到遇到没有未访问出边的顶点，然后重新定位到有未访问出边的顶点继续探索。为减少重新定位次数，机器人会记录出边访问次数多于入边访问次数的“昂贵节点”，并尽量减少对这些节点的访问。 - **Panaite和Pelc的算法**：在无向连通图中，机器人同样具有有限视野、记忆和方向感。探索方式与上述类似，但重新定位时会遵循动态构建的探索图的生成树。探索的边遍历次数下限为|E(G)|，超出部分称为惩罚，该算法的惩罚为O(V(G))。 - **Bender等人的算法**：在强连通有向图中，除了有限视野、记忆和方向感，还假设机器人有一个可以标记节点的石子。如果机器人知道顶点数量，一个石子就足以实现探索并构建图的地图。 ##### 多机器人探索 多机器人探索有两种形式：永久探索和终止探索。 - **永久探索**：要求图的每个顶点被单个机器人无限次探索。研究涵盖了各种图拓扑结构，且机器人遵循CORDA模型，不相互通信。 - **Baldoni等人的研究**：在图中进行永久探索时添加了两个约束条件，即一个节点一次只能容纳一个机器人，且两个机器人不能同时访问同一条边，该问题被称为受限永久图探索（CPGE）。目标是找出在图中可行的最大机器人数量。通过将图转换为标记树，计算最长路径的长度q，确定最大机器人数量k。如果k > p - q（p为图的顶点数），则CPGE不可行。 - **Baldoni等人对部分网格图的研究**：考虑不同视野水平下机器人的可行性。将部分网格转换为标记树，计算最长标记路径的长度q，q是限制机器人数量的关键参数。当视野ρ = 0时，CPGE不可行；当ρ = 1或∞时，可行的最大机器人数量为p - q。 - **Bonnet等人的研究**：目标是最小化网格中机器人的数量。机器人是健忘的、异步的，没有方向感，但有无限视野。从任意初始配置开始，机器人尝试达到一个特殊配置，然后执行一系列移动，重复该过程以实现永久探索。结果表明，在网格中进行CPGE需要且仅需要3个机器人。 - **Blin等人的研究**：针对环图，使用健忘的、异步的机器人，具有无限视野但没有方向感。通过引入预定义配置，从初始配置开始，机器人先达到预定义配置，然后循环移动以实现永久探索。 - **终止探索**：要求每个节点至少被遍历一次，任务完成后所有机器人停止移动。 - **Flocchini等人对树图的研究**：使用健忘的、异步的机器人，具有无限视野和多重检测能力。通过创建一个由部分机器人组成的“大脑”作为可见计数器，指示树的探索进度，其余机器人组成探索团队进行实际探索。 - **Flocchini等人对环图的研究**：使用异步、健忘且不通信的机器人。研究表明，当机器人数量k整除节点数量n时，问题不可行。从初始配置开始，机器人尝试达到所有机器人部署在环的连续节点上的配置（块配置）或有两个这样的块的配置，然后形成塔并确定探索者进行环的探索。 - **Lamani等人的研究**：证明偶数大小的环不能由少于5个机器人探索。解决方案使用5个机器人，从随机初始配置开始，尝试获得块配置，中间的机器人形成塔，然后确定一个探索者探索环。 - **Datta等人的研究**：考虑了只能看到相邻节点的近视机器人，机器人健忘、不通信，具有多重检测能力但没有方向感。研究了同步