# Complete coverage path planning ros

Hi all,

I have a mobile robot with a Hokuyo Lidar, wheel encoders, IMU and couple of Sonar sensors. I have started working on the Complete coverage path planning and I am wondering if there is any package in ROS which can be used for this? I have searched and was not able to find anything. If there is no such package, what is the best way to proceed about it? I know this is a very general question but I am just looking for some pointers or references which might be helpful to start working on Complete coverage path planning?

Naman Kumar

Originally posted by Naman on ROS Answers with karma: 1464 on 2015-06-30

Post score: 3

Comment by Javier V. Gómez on 2015-07-01:
With full coverage you mean you are giving a map and you want the robot to move along the whole map right? I do not know any package for this. However, I guess full coverage algorithms just set partial goal points, so using any path planner and the navigation stack should be enough.

Comment by Naman on 2015-07-01:
Thanks for the reply! That should work if there are no obstacles but if there are obstacles, then the robot should go around that obstacle ("Bug Algorithm") so that it does not miss that area and setting partial goal points might not work in that case.

Comment by lucasw on 2016-02-15:
Similar to http://answers.ros.org/question/174998/path-planning-for-sensortool-coverage/ (and a few others listed there)

For anyone interested in writing a robust global planner plug-in for full coverage, the algorithm presented in the introduction of this published paper works well:

The global planner algorithm steps are:

1. Use costmap2d (costmap_->getCost(x,y) in c++) to divide the map into occupied and free cells
2. Identify the closest cells to the desired start and end pose
3. Use a wavefront algorithm to assign the distance transform value at each cell
4. Iterate through these cells in a path of slowest decent as described in the paper

Next, you can implement the teb_local_planner for path following, but be sure to shorten the prune path value to something like 0.1m (found in teb_local_planner_ros.h). Otherwise the optimizer gets stuck. Id add a picture but i dont have enough karma...

EDIT: Thank you for the karma! This image shows the full coverage path in yellow covering most of the willow garage map. I have included the z-axis to shed some light on the algorithm. the red points represent the distance transform cost of every free cell (higher=more cost), and the planner plans the slowest decent down this gradient funnel. Note the lowest area is the goal point.

Originally posted by Stephen_Z with karma: 116 on 2017-02-24

This answer was ACCEPTED on the original site

Post score: 7

Comment by spmaniato on 2017-02-25:
@Stephen_Z This setup sounds interesting. I've done something similar. Wanna upload the picture to a third party service and then post a link to it here? (Also, I just gave you some karma by upvoting the answer. See if you can upload the picture now.)

Comment by dev_arya on 2017-05-04:
Hey @Stephen_Z, is it possible for you to run your CCP algorithm over the stage simulator maze and bosch world environment and post result images here??? I need some reference for my work, I will be really thankful for your help. Cheers!

Comment by Stephen_Z on 2017-05-04:
Yes, I think I can do that. Could you attach some links that'll get me to the maps you are interested in?

Comment by dev_arya on 2017-05-04:
@Stephen_Z Thanks a lot. Here is the link https://github.com/turtlebot/turtlebot_simulator/tree/indigo/turtlebot_stage/maps There are two maps: maze and robopark. I actually need the path trace for complete coverage. Thanks again.

Comment by dev_arya on 2017-05-15:
@Stephen_z : Could you generate the maps as I requested..

Comment by Stephen_Z on 2017-05-15:
I am very sorry, but i have moved on from this project for now and it turned out to be harder then I expected to get my old code working in a reasonable amount of time. I tried, and I apologize for any inconvenience this has caused you.

Comment by dev_arya on 2017-05-16:
@Stephen_Z : np Stephen.. I can understand but thanks for your time. Cheers!

Comment by Aureus on 2017-06-13:
@Stephen_Z: How can you create such images including the red z-axis and the yellow path? And is there any possibility to have a look at your source code? Would be interesting for me.

Comment by Stephen_Z on 2017-08-28:
@Aureus: I used the rviz markers found at http://wiki.ros.org/rviz/DisplayTypes/Marker . Sorry, I can not release the source code at this time.

Comment by jjbecomespheh on 2020-08-12:
Hi @Stephen_Z, can I check you are able to release the source code?

This may not be very relevant but if you are interested in sensor planning when you have a mobile remote sensor (gas sensor, camera, laser or any other for which you can define sensing range and field of view) and you want to cover the whole environment by taking measurements at minimum number of positions then here is a possible solution.

However, the code is not available on ROS. Hopefully I will be able to release it at some point in near future.

Originally posted by AsifA with karma: 231 on 2015-08-14

This answer was NOT ACCEPTED on the original site

Post score: 1

For autonomous exploration the following packages are available:

If you require visiting every part of a floor plan with your platform (like what an intelligent robot vacuum would need to do) I'm not sure there is software available for that.

Originally posted by Stefan Kohlbrecher with karma: 24361 on 2015-08-14

This answer was NOT ACCEPTED on the original site

Post score: 1

The heatmap package (http://wiki.ros.org/heatmap) says it does coverage path planning as part of its functionality. The source code is here and looks maintained: https://github.com/eybee/heatmap/tree/jade-devel

The heatmap package itself uses the coverage path planner from the Auburn Autonomous Lawnmower stack (https://github.com/Auburn-Automow/au_automow_common), which looks out of date.

Originally posted by spmaniato with karma: 1788 on 2016-02-15

This answer was NOT ACCEPTED on the original site

Post score: 1