This package contains implementations to compute coverage patterns and shortest paths in general polygon with holes. Please cite our accompanying publication when using it.

Bähnemann, Rik, et al.
"Revisiting boustrophedon coverage path planning as a generalized traveling salesman problem."
Field and Service Robotics. Springer, Singapore, 2021.

Watch the application video:

Install ROS noetic. Install mono.

Create a workspace and download the package.

cd ~
mkdir -p catkin_ws/src
cd catkin_ws
catkin init
catkin config --cmake-args -DCMAKE_BUILD_TYPE=Release
catkin config --extend /opt/ros/noetic
cd src
git clone [email protected]:ethz-asl/polygon_coverage_planning.git

Install all remaining dependencies:

cd polygon_coverage_planning/install
./prepare-jenkins-slave.sh

Finally, build the workspace.

catkin build

The package has a ROS interface for shortest path planning and coverage planning. First source your workspace to execute any of the nodes.

source ~/catkin_ws/devel/setup.bash

roslaunch polygon_coverage_ros coverage_planner.launch

The polygon can be set via

• ROS service call rosservice call /coverage_planner/set_polygon
• ROS parameter /coverage_planner/polygon or
• RVIZ Polygon Tool as in the video above.

The plan is generated via

• ROS service call rosservice call /coverage_planner/plan_path or
• clicking start and goal points using the RVIZ clicked_point tool as in the video above.

The resulting waypointlist is published as geometry_msgs/PoseArray on topic /waypoint_list.

roslaunch polygon_coverage_ros shortest_path_planner.launch

Setting the polygon and planning the path is the same as for Coverage Planning.

This repository is subject to GNU General Public License version 3 or later due to its dependencies.

The underlying (exact) geometric operations rely on CGAL 5.0.3 which is restricted by GNU General Public License version 3 or later. In particular the dependencies are:

• Algebraic Foundations (LGPL)
• 2D and 3D Linear Geometry Kernel (LPGL)
• 2D Polygon (LPGL)
• Geometric Object Generators (LPGL)
• STL Extensions (LGPL)
• 2D Triangulation (GPL)
• 2D Regularized Boolean Set-Operations (GPL)
• 2D Straight Skeleton and Polygon Offsetting (GPL)
• 2D Arrangement (GPL), see also

Fogel, Efi, Dan Halperin, and Ron Wein. CGAL arrangements and their applications: A step-by-step guide. Vol. 7. Springer Science & Business Media, 2012. Bungiu, Francisc, et al. "Efficient computation of visibility polygons." arXiv preprint arXiv:1403.3905 (2014).

The underlying optimization uses the memetic solver presented in

Gutin, Gregory, and Daniel Karapetyan.
"A memetic algorithm for the generalized traveling salesman problem."
Natural Computing 9.1 (2010): 47-60.

It is free of charge for non-commercial purposes only.