Coverage Planning

The goal of coverage planning is to generate a path such that a robot sweeps every part of some area with one of its sensors. I worked on this during my time at Enlighted.

Why have I never seen this concept before?

This is because usually, the planning problem that I deal with is generating shortest paths from A to B, like in F1TENTH or Self-Driving Car. However, this is about covering the entire area.

Resources

• From ipa_coverage_planning ROS1 repository:
  • Room Segmentation: Survey, Implementation, and Analysis
    • shows the different image processing techniques you can apply to automatically segment an area
  • Indoor Coverage Path Planning: Survey, Implementation, Analysis
• Fields2Cover (ROS2 Implementation)
• A Survey on Coverage Path Planning for Robotics, pretty nice visuals
• Coverage Planning with Finite Resources by CMU
• https://roboticsknowledgebase.com/wiki/planning/coverage-planning-implementation-guide/
• Boustrophedon Cellular Decomposition published in 1998

The goal of coverage planning is to generate a path such that a robot sweeps every part of some area with one of its sensors and/or end-effectors. I first had to work on this for Enlighted.

From the ipa_converage_planning paper, they introduce 6 different techniques

1. Boustrophedon Decomposition: The boustrophedon approach is an exact cellular decomposition method which divides the room area into smaller cells using a sweep line
2. Grid-based Traveling Salesman Coverage Path Planning
3. Neural Network-based Coverage Path Planning
4. Grid-based Local Energy Minimization
5. Contour Line-based Coverage Path Planning
6. Convex Sensor Placement Coverage Path Planning

You’ll notice that in these cases, the paths are only generated for each room. There is no plan to go between the rooms. This is something that I need to code up.

To do the evaluation, they divide between a footprint Coverage problem and a sensor coverage problem, though I’m not sure what sensor coverage is about.

Some common ways:

• Cellular Decomposition

Use Cases:

• drone monitoring applications, where you need the drone to follow a path such that its cameras get a view of every part of some larger field/area
• Robot lawnmower or vacuum, where we want the robot to move such that it mows or vacuums every square meter of some field or room, such as at AvidBots

There are 2 main ways to approach these:

1. Random path following (no need to generate a path)
2. Generate a path, and then have the robot follow that path

The second approach is much more interesting. We first generate the path offline on a per-room basis, and then we run a planner (ex: Nav2 Planner) to follow those waypoints in real-time.

Option 1: Random Path Following (Simplest)

If we want to explore option 1, a simple coverage planner exists: https://github.com/iRobotEducation/create3_examples/tree/galactic/create3_coverage

How to use

Build this and the create3_examples_msgs packages. Source the setup shell scripts.

Start the coverage action server

ros2 run create3_coverage create3_coverage

In a separate terminal command a coverage action

ros2 action send_goal /coverage create3_examples_msgs/action/Coverage "{explore_duration:{sec: 500, nanosec: 0}, max_runtime:{sec: 1000,nanosec: 0}}"

Option 2: Generate path + Path Following

This is made out of 3 components.

1. Run SLAM
2. Generate the waypoints offline using a notebook
3. Follow the waypoints with Nav2

Line Sweep Algorithm

The line sweep algorithm uses a simple “mowing the lawn” pattern.

The function first tries to divide the zone up into cells, and the points are the center of the cells.

The walls_only flag allows us to only select the waypoints that are at the boundaries of the zones. We noticed that this made the process of following waypoints on the robot much smoother and faster since it had to track fewer waypoints, which are all farther apart.