ethz-asl/polygon_coverage_planning

Coverage planning in general polygons with holes.

polygon_coverage_planning 是一个由苏黎世联邦理工学院（ETH Zurich）自动系统实验室（ASL）开发的开源路径规划工具包，专注于解决带孔洞复杂多边形区域内的全覆盖路径规划与最短路径计算问题。该项目将经典的“牛耕式”覆盖路径规划问题重新建模为广义旅行商问题（GTSP），通过将覆盖路径生成转化为优化问题，显著提升了规划效率与路径质量。其核心功能包括：在任意多边形（含孔洞）中自动生成覆盖整个区域的作业路径，以及计算任意两点间的最短欧几里得路径。技术栈方面，项目基于ROS Noetic框架，底层依赖CGAL库进行精确的几何运算（如多边形布尔运算、三角剖分、可见性计算），并集成了专用的GTSP求解器（memetic算法）来优化路径顺序。用户可通过RVIZ可视化工具交互式设置多边形、选择起止点，并实时查看规划结果。该工具主要解决了农业无人机喷洒、地面机器人清洁、工业表面检测等场景中的全覆盖路径规划难题——传统方法在处理复杂边界或障碍物时往往效率低下或路径冗余，而本项目通过数学优化保证了路径的全局最优性。项目提供了完整的ROS接口，支持通过服务调用或参数配置灵活部署，并附有详细的安装脚本与演示视频，适合机器人领域的研究者与工程师直接使用或二次开发。