Boustrophedon cell decomposition is simply sub-dividing an environment into areas which can be efficiently covered by a boustrophedon path. A trapezoidal decomposition will do, and can be accomplished using a line-sweep algorithm.
See [Choset 2000], This web site
, or (I recommend!) the excellent book "Computational Geometry" by Mark de Berg, et. al, for a complete description of the data structures and algorithms required.
Choset, Howie. "Coverage of Known Spaces: The Boustrophedon Cellular Decomposition" Autonomous Robots, 2000.
For example, consider the set of obstacles as edges and vertices. Let's say the environment is also bounded by a special polygon. We have something like the following. To decompose this space, we simply add vertical edges between every vertex and the nearest line or vertex.
To accomplish this in code, you need only a line-segment intersection test, a sorted list of edges, and a sorted list of vertices.
- From every vertex $v_i$ in left-to-right order,
- Create a vertical line $l_i$ at each $v_i$, extended until the first edge or vertex it intersects
- At each intersection, create a new vertex.
When this is done, the set of new edges and vertices encloses only trapezoids. But I emphasize, you can't do this online (without prior knowledge of the obstacles). If you want to do robust coverage without prior knowledge, you might look at "bug algorithms." In particular, here's a simple algorithm, assuming the environment is bounded.
From the start position, move up and left until you reach the upper-left corner of the environment. If you encounter an obstacle first, you must travel around it. You know something is an obstacle if it can be circumnavigated (bump and move).
From the upper left, move right until you encounter the boundary. Then move down and left (We're doing a boustrophedon of the entire space).
When you are on a left-right line and encounter an obstacle, you have two options. (i) We can circumnavigate until we reach the left-right line we are trying to cover, then continue. (ii), We can turn around and cover a new left-right line until we find our way past the obstacle or end up in this situation again. I'll illustrate.
On the left, we move around the obstacle until we can return to the "line" we were trying to follow. On the right, we continue covering the (smaller) area on the one side of the obstacle.
The advantage of the first method is you always map out the obstacle completely before you make a decision about how to get around it, thus you can take the shorter path. The advantage of the second method is you don't have to get around the obstacle at all, you can just proceed to cover the area you are in.
Note that this defines your boustrophedon decomposition in an online way: You cover the area between the obstacles or between the obstacles and the boundary.
However, as far as I know, the first method is easier to analyze. The more complicated algorithms (like BFS, etc), are chosen either because the environment is unbounded (you don't want to spend forever looking for a boundary), or there is a really nasty obstacle in the way that basically partitions the environment. Why is this bad? look at this example:
Moving left-right, then circling each obstacle produces way too many covers of the small parts between each obstacle. In fact, without global path planning, you can make this as bad as the resolution of your grid by placing these columns 1 px wide, as tall as the entire environment and 1 px apart. Then you'd have to move around the obstacle each time you hit it.
This is why I asked if you had some idea of where you were in the environment or could do global path planning. But the online vs offline discussion and optimal algorithms for this is not what you really wanted.
Update: I had to remove the images (not https), and will post this which is often used in practical real-world applications. http://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1/yamauchi_frontiers.pdf
