# What's an efficient way to visit every reachable space on a grid with unknown obstacles?

I'm trying to create a map of the obstacles in a fairly coarse 2D grid space, using exploration. I detect obstacles by attempting to move from one space to an adjacent space, and if that fails then there's an obstacle in the destination space (there is no concept of a rangefinding sensor in this problem).

The process is complete when all the reachable squares have been visited. In other words, some spaces might be completely unreachable even if they don't have obstacles because they're surrounded. This is expected.

In the simplest case, I could use a DFS algorithm, but I'm worried that this will take an excessively long time to complete — the robot will spend more time backtracking than exploring new territory. I expect this to be especially problematic when attempting to reach the unreachable squares, because the robot will exhaust every option.

In the more sophisticated method, the proper thing to do seems to be Boustrophedon cell decomposition.

However, I can't seem to find a good description of the Boustrophedon cell decomposition algorithm (that is, a complete description in simple terms). There are resources like this one, or this more general one on vertical cell decomposition but they don't offer much insight into the high-level algorithms nor the low-level data structures involved.

How can I visit (map) this grid efficiently? If it exists, I would like an algorithm that performs better than $$O(n^2)$$ with respect to the total number of grid squares (i.e. better than $$O(n^4)$$ for an $$n*n$$ grid).

• Very interesting problem. For clarity, are you defining "efficient" as fewest repeated visits to any given cell? – DaemonMaker Feb 20 '13 at 4:50
• That might be one way to say it. Really, I'm trying to avoid algorithms that are $O(n^2)$ or worse with respect to the total number of grid squares. – Ian Feb 20 '13 at 14:23
• I guess this is a similar problem to that faced by CNC machining software which must remove material by visiting it with the cutting tool. – Rocketmagnet Feb 20 '13 at 18:21
• @Rocketmagnet: not quite, since the CNC machine knows the "obstacles" a priori, whereas I am detecting them while I move. – Ian Feb 20 '13 at 20:18
• Yes, this is an online search of a bounded environment where the robot knows its location. The quantity, locations, and shapes of the obstacles is completely unknown -- they might not be convex. – Ian Feb 20 '13 at 22:27

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.

1. From every vertex $$v_i$$ in left-to-right order,
2. Create a vertical line $$l_i$$ at each $$v_i$$, extended until the first edge or vertex it intersects
3. 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.

1. 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).

2. 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).

3. 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

• Just finding a description (in simple terms) of the Boustrophedon decomposition algorithm would be sufficient. Failing that, a simple description of an algorithm with similar performance is fine. – Ian Feb 20 '13 at 22:30
• I've added a simple boustrophedon decomposition example. – Josh Vander Hook Feb 21 '13 at 4:38

In the end, I found that the best way to do this was to employ a very simple concept: Flood Fill. I used a stack-based iterative approach instead of the recursive option, and modified it for physical space by using an A* search to find a path from the current location to the next location in the stack (using only those grid squares that have already been visited, since I'm guaranteed to have a path between them).

The efficiency seems fairly reasonable.