Implementing a Complete Coverage Path Planner

[Spyros Maniatopoulos]

Hello Navigation SIG,

this is my first post. Here goes.

I'm in the (very) early stages of implementing a global planner for complete coverage of a (known) map. Quite a few people have shown interest in this capability [1-3] but I don't think anything was ever implemented (I could only find [4] from ~2012). Btw, when I say coverage I mean by the robot's footprint, not a laser/sonar sensor; think a Roomba vacuuming the floor.

In terms of the algorithm, I'm thinking Complete Coverage D* [5] or Wavefront-based Coverage [6]. Regardless of the specific algorithm though, I'm writing to ask for your advice on how to best implement it such that it fits the plugin-based philosophy of the nav stack and David Lu's layered costmaps (if appropriate). I've thought of three approaches:

1. Implement the algorithm as a global planner plugin that would plan over the (inflated) static map. Then follow the path using, e.g., DWA and replan (globally) if necessary. Keep track of (actual) coverage in a separate grid-like data structure. This is most intuitive for me, but doesn't feel very ROS-like.
2. Implement a Costmap 2D layer that corresponds to coverage. Then implement a global planner plugin such that it plans over a master costmap that includes this new coverage layer. The coverage layer gets updated not based on sensor data but instead based on the robot's pose/footprint. The local planner may also take the coverage layer into account in order to avoid unnecessary overlap.
3. Implement a Costmap 2D layer that corresponds to coverage in such a way that an existing global planner, e.g., A*, can be configured [7] such that the resulting robot behavior is that of complete coverage. The rest would be more or less like approach (2) above. If this sounds handwavy it's because it is. I'm not familiar enough with the technical details of the nav stack to say whether it makes sense or not. Hence my posting here.
   

Did any of that make sense? I'm looking forward to your thoughts.

Thanks a lot for your time :-)

Best,

Spyros

[1] http://answers.ros.org/question/66146/complete-coverage-path-planner/

[2] http://answers.ros.org/question/185718/full-coverage-path-planner/

[3] http://answers.ros.org/question/212614/complete-coverage-path-planning-ros/

[4] https://github.com/Auburn-Automow/au_automow_common/tree/master/automow_planning

[5] http://www.nt.ntnu.no/users/skoge/prost/proceedings/ifac11-proceedings/data/html/papers/3400.pdf

[6] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.7617

[7] https://github.com/ros-planning/navigation/blob/jade-devel/global_planner/cfg/GlobalPlanner.cfg

Disclosure: I'm developing this coverage path planner as part of an internship at a robotics startup. I would personally love to open-source it, but I'm not sure my employer will agree.

[David Lu!!]

I think the first solution is fine. Ultimately it comes down to what
you're optimizing (besides coverage). If its more important that you
never revisit particular locations, then it might make sense to put
the coverage in the costmap. However, if you're optimizing over
time/distance, then I'd imaging that your planning algorithm would
already take into account where the robot has already been, and
wouldn't need to track that in the costmap.

> --
> You received this message because you are subscribed to the Google Groups
> "ros-sig-navigation" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to ros-sig-navigat...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Damien]

Hi all, 

This thread is more than a year old... But I have the same necesity: a complete coverage algorithm based on an existing map generated by SLAM...

Spyros, did you achieve a good implementation of your algorithm? Any video of the real robot ?

Is it available open source? 

Thanks !

Damien

[Spyros Maniatopoulos]

Damien, unfortunately I can't say much about my implementation because it was done while working for a company (under NDA, etc.)

But search through ROS Answers; there are some good starting points like: https://answers.ros.org/question/212614/complete-coverage-path-planning-ros