C?：一种用于未知环境的覆盖路径规划算法，该算法基于快速覆盖图（Rapidly Covering Graphs）

《IEEE Transactions on Robotics》：C? : A Coverage Path Planning Algorithm for Unknown Environments Using Rapidly Covering Graphs

实时覆盖路径规划算法C?基于快速覆盖图（RCG），通过渐进式采样和高效剪枝构建最小充分图，动态跟踪覆盖进度并生成最优轨迹，有效解决覆盖孔和死胡同问题，实验验证其在实时覆盖规划中的显著优势。

　　

摘要：

本文提出了一种基于样本的新型算法，称为C，用于未知环境中的实时覆盖路径规划（CPP）。C?算法建立在快速覆盖图（RCG）的概念之上，该图通过逐步采样搜索空间在机器人导航过程中动态构建。通过使用高效的采样和剪枝技术，RCG被构建为一个“最小充分图”，其节点和边分别代表潜在的路径点以及覆盖轨迹的片段。RCG能够跟踪覆盖进度、生成覆盖轨迹，并帮助机器人避免陷入死胡同。为了最小化覆盖时间，C?算法能够生成所需的往返覆盖模式，同时适应局部孤立区域（称为覆盖空洞）的覆盖需求。这些孤立区域被障碍物包围，但周围仍有可覆盖的区域。理论分析证明，C?算法能够实现对未知环境的完全覆盖。C算法的简单性和低计算复杂度使其易于实现，非常适合实时嵌入式应用。其性能通过以下方式得到验证：1) 大规模的高保真模拟；2) 使用自主机器人的实验室实验。实验结果表明，C?算法能够生成接近最优的轨迹；与七种现有CPP方法相比，在覆盖时间、转弯次数、轨迹长度和重叠比率方面均表现出显著提升，同时有效防止了覆盖空洞的形成。最后，C?算法在两种不同的CPP应用场景中进行了对比评估：一种是能量受限的机器人，另一种是多机器人团队。