Bug Algorithms

Imagine a robot dropped into an unknown room. It cannot see. It has no map. All it can sense is whether it is touching an obstacle and which direction points toward the goal. Can it still guarantee reaching the goal?

The answer is yes — and the proof is surprisingly simple. A family of algorithms called bug algorithms (introduced by Lumelsky and Stepanov in 1987) show that touching obstacle boundaries and following a single rule is enough to reach any reachable goal in any finite environment. The robot behaves like a bug crawling along a wall: when the path is clear it walks straight; when it hits something it hugs the boundary until a well-chosen exit condition fires.

Bug algorithms are the foundation of minimal-sensor navigation — a branch of robotics that asks: what is the least information a moving agent needs to be complete? They are also a vivid illustration of the gap between having a complete algorithm and being efficient: Bug1 guarantees the goal but may trace every boundary; Bug2 is smarter; A* and its cousins are smarter still, but they demand a map.

The robot (green) starts at the top-left and must reach the goal (red star) at the bottom-right. It follows the Bug2 rule: move along the straight line from start to goal (the m-line) until you hit a wall, then hug the left side of the obstacle until you cross the m-line again at a point closer to the goal.

<!-- {{c_html_intro}} -->
<div class="hint-bar">{{hint_para}}</div>
<canvas id="maze" width="360" height="300"></canvas>
<div class="status-row">
  <span id="status" class="status">{{status_ready}}</span>
</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run"  type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint-bar { font-size: .85rem; color: #444; margin-bottom: .5rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; max-width: 100%; }
.status-row { min-height: 1.6em; margin: .4rem 0; }
.status { font-size: .95rem; font-weight: 600; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Press Step to advance one move at a time, or Run to watch it complete automatically. Notice that the robot never needs a map — it only needs to know the goal direction and whether it is touching a wall. Press Reset to start over.

The bug family reveals a beautiful tradeoff between sensor requirements and path quality:

• Bug0 — move toward goal; if blocked, follow the wall until unblocked, then head for the goal again. It uses zero memory but can loop forever in mazes where every exit leads back to the same wall.
• Bug1 — on hitting a wall, trace the entire boundary once, remember the closest point to the goal, return there and leave. Always complete, but the path length can be $O(n^2)$ where $n$ is the total obstacle perimeter — the robot may trace every boundary it touches.
• Bug2 — the robot carries an imaginary straight line (the m-line) from start to goal. On hitting a wall, hug it until you re-cross the m-line at a point strictly closer to the goal than where you left it. Path length is $O(n \cdot P)$ where $P$ is the number of obstacles the m-line crosses.
• Tangent Bug (1998) adds a thin ring sensor: the robot can see a short distance ahead. This removes wasted boundary tracing and brings the path length down to $O(n)$ over the full journey.

The key theoretical result: Bug1 and Bug2 are complete — in any connected environment with finitely many polygonal obstacles they always reach the goal or correctly declare it unreachable. Bug0 is not complete. Tangent Bug is complete and more efficient. None of them produce the shortest path; that requires global map knowledge, as studied in Dijkstra's algorithm and its variants.

The "feel the wall" strategy is not just a theoretical curiosity — it appears everywhere sensors are scarce or cheap:

• Robot vacuums: early Roombas used a direct relative of Bug1, tracing room boundaries and returning to the nearest approach to the center. The sensor required is just a bump sensor.
• Emergency robotics: in smoke-filled buildings or deep-sea wreckage where cameras fail, a robot that only needs to feel walls can still navigate to a known goal position.
• Planetary rovers: when communication lags make remote mapping impractical, onboard completeness guarantees matter more than path optimality.
• Swarm robotics: individual agents with cheap touch sensors can collectively explore an unknown environment without any agent needing a global map.
• Teaching foundations: bug algorithms are the canonical entry point for the question "what is the minimum information needed to solve a navigation problem?" — the same question that motivates complexity theory more broadly.

Bug algorithms answer one of the most basic questions in robotics: how little can a robot know and still be guaranteed to reach its goal? The answer — just a compass and a bump sensor — is surprisingly small.

The insight that completeness and optimality are separate concerns runs deep. A bug robot always arrives; it just may take the long way around. Getting a shorter path costs information: you need a map, or at least a longer-range sensor. That tradeoff — more knowledge buys better paths — echoes through A*, Dijkstra, and every planning algorithm ever designed.

So the next time a robot vacuum bumps into your sofa and starts circling the room, do not dismiss it as primitive. It is running one of the most elegant completeness proofs in all of computer science.