Bug Algorithms
A bug robot knows where the goal is but has no map. It drives straight toward the goal, and when it bumps into something it follows the obstacle edge until it can head for the goal again. Two simple rules for when to leave the edge give two different robots.
The two rules
Bug 1 goes all the way around each obstacle it hits, remembers the point closest to the goal, returns there, and leaves. Bug 2 uses the straight line from start to goal, called the m-line. It follows the obstacle only until it meets the m-line again at a point closer to the goal than where it hit.
For a start-to-goal distance \(D\) and obstacles with perimeters \(p_i\), the worst-case path lengths are:
where \(n_i\) is how many times the m-line crosses obstacle \(i\).
What to notice
Bug 1 is slow but predictable: it always circles each obstacle once. Bug 2 is usually much shorter, because it leaves as soon as it can. On some obstacle shapes, Bug 2 can be worse, since it may cross the same obstacle many times. Both are complete: if a path exists they will find it, and if the goal is enclosed they will report that.
Bug algorithms show the trade-off at the heart of planning: with no map you can still guarantee success, but not a short path.