# following a boustrophedon path in a given room with obstacles

Hi all,

I have a mobile robot which is navigating around a room, I already have the map of the room. I am using the navigation_stack of ROS. I am using rotary encoders for odometry. I am fusing the data from Rotary encoders and IMU using robot_pose_ekf. I am using amcl for localization and move_base for planning. Now, I have to write a Complete coverage Path planning algorithm and I am following this paper and I would like to ask what is the best way to generate the Boustrophedon path (simple forward and backward motions) in a cell (can be rectangular, trapezium, etc.) with no obstacles? If someone can suggest how to implement it in ROS, that will be great.

Update:
In cases like shown here (taken from here):

To come up with divisions in the 2nd or 3rd cell (center top or center bottom), I dont know whether knowing all the corner points will be enough (I might be wrong) or should we have all the boundary points (If yes, I am not sure how exactly to find it). Does anyone have any idea how to generate boustrophedon path in a cell like this?

Naman Kumar

Originally posted by Naman on ROS Answers with karma: 1464 on 2015-07-13

Post score: 0

This should be pretty simple, just divide one direction of your cell by the coverage width of the robot and create path goals at the start and end of each division along the other direction.

Originally posted by dornhege with karma: 31395 on 2015-07-13

This answer was ACCEPTED on the original site

Post score: 1

Comment by Naman on 2015-07-13:
Thanks for the answer @dornhege! but how can one find the start and end of each division in the given cell? I can see how to do it if its rectangular and you know its dimensions but how can it be generalized for any cell or division? TIA

Comment by dornhege on 2015-07-14:
Unless you have some weird forms, it's just linear interpolation.

Comment by Naman on 2015-07-16:
Thanks @dornhege! Just one more thing, are you assuming that you know all the boundary points of the cell (or division) to find the start and end of each division? TIA

Comment by dornhege on 2015-07-16:
Corners, edges, points, whatever you have. If you don't have something like that, you don't have a cell.

Comment by Naman on 2015-07-16:
Yaa..but in cases like shown in the updated question, I dont know whether knowing only the corners is enough or do we need all the boundary points. Can you please have a look at the updated question. TIA :)

Comment by dornhege on 2015-07-16:
You need to know the boundary. That should come out of your decomposition algorithm.

Comment by ssohin on 2019-02-21:
Using a DCEL is one way to define the polygons: Doubly Connected Edge List Were you able to implement this @Naman?