# 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

edit retag close merge delete

Sort by ยป oldest newest most voted

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.

more

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

( 2015-07-13 15:16:58 -0500 )edit
1

Unless you have some weird forms, it's just linear interpolation.

( 2015-07-14 04:22:35 -0500 )edit

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

( 2015-07-16 07:18:57 -0500 )edit
1

Corners, edges, points, whatever you have. If you don't have something like that, you don't have a cell.

( 2015-07-16 08:15:23 -0500 )edit

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 :)

( 2015-07-16 08:53:14 -0500 )edit
1

You need to know the boundary. That should come out of your decomposition algorithm.

( 2015-07-16 08:56:34 -0500 )edit

Using a DCEL is one way to define the polygons: Doubly Connected Edge List Were you able to implement this @Naman?

( 2019-02-21 10:18:03 -0500 )edit