Bug algorithms: getting to a goal without a map
How a robot reaches a goal with no map, by driving at it and following the edge of whatever gets in the way. Bug 0, Bug 1 and Bug 2 compared, each one running on a live robot with its path drawn on the mat, next to a straight dash that gets stuck.
A bug algorithm gets a robot to a goal it cannot see a route to, using almost nothing: where it is, where the goal is, and whether something is in the way right now. There is no map, no search and no list of waypoints. The robot drives straight at the goal until it bumps into something, follows the edge of whatever it is, and at some point decides to set off for the goal again. Everything interesting is in that last decision, and the three classic answers to it are called Bug 0, Bug 1 and Bug 2, from a 1987 paper by Vladimir Lumelsky and Alexander Stepanov. The name comes from the behaviour: an insect walking into a wall and feeling its way along. On this page a robot crosses a 2 metre mat with a crate in the way, and each demo below is a real program you can change and run.
What a bug algorithm needs
Three things, and no more:
- Where it is and where the goal is. A direction and a distance to the goal is enough. On this page the robot works that out from
position(); a real robot would use odometry, a compass, tags on the wall or GPS. - A way to tell that something is in the way. Here it is the depth sensor. A bumper works too, and the original paper assumed a robot that feels its way by touch.
- A way to follow an edge. Keep the thing you have found beside you and move along it.
What it does not need is a map, which is the whole point. A robot that has one should plan with A* and get a shorter route. A robot that does not, or whose map has just turned out to be wrong, still has to get somewhere.
Straight at it
The robot starts at (30, 30) and the goal is at (170, 160), 191 cm away. A crate sits across the line between them. This mat belongs to a path following lesson, so it also has a taped route on it and a green square in the corner: the programs on this page ignore both, and draw their own goal on the mat as a yellow square. Here is the whole of the naive plan: point at the goal and drive.
The program
from bugbot import *
import math
connect()
# change these numbers and press Run
GOAL = (170, 160) # where the robot is going, cm
STANDOFF = 20 # how far off the wall it follows, cm
CRUISE = 13 # how fast it slides along the wall, cm/s
START = (30, 30) # where the robot starts, cm
HIT = 22 # a reading closer than this is "in the way", cm
SEE = 60 # the fan ignores anything further off, cm
def here():
x, y = position()
return START[0] + x, START[1] + y
def gap():
x, y = here()
return math.hypot(GOAL[0] - x, GOAL[1] - y)
def bearing():
x, y = here()
return math.degrees(math.atan2(GOAL[0] - x, GOAL[1] - y)) % 360
def face(a):
# turn on the spot until the robot points that way
for i in range(80):
e = (a - heading() + 180) % 360 - 180
if abs(e) < 2:
break
drive(0, 0, max(-60, min(60, 1.5 * e)))
wait(0.05)
stop()
def wall():
# fit a straight line to the eight depth readings in front:
# (how far it is tilted in degrees, how far off it is in cm)
pts = [(d * math.sin(math.radians(a)), d * math.cos(math.radians(a)))
for a, d in scan() if d < SEE]
if len(pts) < 3:
return None
n = len(pts)
mx = sum(p[0] for p in pts) / n
my = sum(p[1] for p in pts) / n
sxx = sum((p[0] - mx) ** 2 for p in pts)
syy = sum((p[1] - my) ** 2 for p in pts)
sxy = sum((p[0] - mx) * (p[1] - my) for p in pts)
a = 0.5 * math.atan2(2 * sxy, sxx - syy)
return math.degrees(a), abs(my * math.cos(a) - mx * math.sin(a))
def step_to_goal():
# one tick of driving straight at the goal
drive(70, 0, 1.5 * ((bearing() - heading() + 180) % 360 - 180))
wait(0.1)
def step_along_wall(w):
# one tick of sliding along the wall, facing it, holding the standoff
tilt, off = w
fwd = max(-10, min(10, 1.5 * (off - STANDOFF)))
drive(fwd * 5, -CRUISE * 100 / 15, max(-45, min(45, -3 * tilt)))
wait(0.1)
trail, went = [], 0.0
def keep_up():
# the picture on the mat and the chart under the console
x, y = here()
if trail:
global went
went += math.hypot(x - trail[-1][0], y - trail[-1][1])
trail.append((x, y))
draw("path", trail[::3], "blue", "line")
plot("to goal cm", gap())
return x, y
def arrived():
stop()
print("at the goal after", clock(), "s, having driven", round(went), "cm")
draw("goal", [GOAL], "yellow", "squares", 8)
face(bearing())
blocked = False
for tick in range(250): # 25 seconds
x, y = keep_up()
if gap() < 8:
arrived()
break
if distance() < HIT and not blocked:
blocked = True
print("something in the way at", round(x), round(y), "after", clock(), "s")
if blocked:
stop()
wait(0.1)
else:
step_to_goal()
stop()
if blocked:
print("stopped", round(gap(), 1), "cm from the goal, reading", distance(), "cm ahead")
The blue line on the mat runs about 36 cm and stops. The chart falls from 191 cm to 151.9 and then flattens, which is what being stuck looks like on a chart. Everything below is about the next line of that program.
The hit point is where the robot met the crate, at (56, 55). Every bug algorithm remembers something about it.
Following the edge
All three algorithms need the same skill in between: keep the obstacle beside you and move along it. This robot drives sideways as easily as forwards, so it does it by facing the wall and sliding.
wall() takes the eight distances from scan(), turns each one into a point in front of the robot, and fits a straight line through them. That gives two numbers: how far off the wall is, and how far it is tilted. step_along_wall() then drives three things at once, as one command: forwards or backwards to hold the gap at STANDOFF, sideways at CRUISE, and a turn to take the tilt out. When the robot reaches a corner, the readings that still see wall pull the fit round, and the robot turns the corner without any code for corners.
A robot that cannot drive sideways does the same job with a sensor pointing at the wall and a turn instead of the sideways part. The rule is the same: hold the distance, follow the edge.
Bug 0: leave as soon as the goal is clear
The simplest rule there is. Follow the edge, and the moment the way to the goal looks clear, go.
The sensor only looks forwards, so "looks clear" costs something: the robot has to turn and look. This demo only bothers once the goal has gone behind it, which means the wall it is following is no longer between the two.
The program
from bugbot import *
import math
connect()
# change these numbers and press Run
GOAL = (170, 160) # where the robot is going, cm
STANDOFF = 20 # how far off the wall it follows, cm
CRUISE = 13 # how fast it slides along the wall, cm/s
START = (30, 30) # where the robot starts, cm
HIT = 22 # a reading closer than this is "in the way", cm
SEE = 60 # the fan ignores anything further off, cm
def here():
x, y = position()
return START[0] + x, START[1] + y
def gap():
x, y = here()
return math.hypot(GOAL[0] - x, GOAL[1] - y)
def bearing():
x, y = here()
return math.degrees(math.atan2(GOAL[0] - x, GOAL[1] - y)) % 360
def face(a):
# turn on the spot until the robot points that way
for i in range(80):
e = (a - heading() + 180) % 360 - 180
if abs(e) < 2:
break
drive(0, 0, max(-60, min(60, 1.5 * e)))
wait(0.05)
stop()
def wall():
# fit a straight line to the eight depth readings in front:
# (how far it is tilted in degrees, how far off it is in cm)
pts = [(d * math.sin(math.radians(a)), d * math.cos(math.radians(a)))
for a, d in scan() if d < SEE]
if len(pts) < 3:
return None
n = len(pts)
mx = sum(p[0] for p in pts) / n
my = sum(p[1] for p in pts) / n
sxx = sum((p[0] - mx) ** 2 for p in pts)
syy = sum((p[1] - my) ** 2 for p in pts)
sxy = sum((p[0] - mx) * (p[1] - my) for p in pts)
a = 0.5 * math.atan2(2 * sxy, sxx - syy)
return math.degrees(a), abs(my * math.cos(a) - mx * math.sin(a))
def step_to_goal():
# one tick of driving straight at the goal
drive(70, 0, 1.5 * ((bearing() - heading() + 180) % 360 - 180))
wait(0.1)
def step_along_wall(w):
# one tick of sliding along the wall, facing it, holding the standoff
tilt, off = w
fwd = max(-10, min(10, 1.5 * (off - STANDOFF)))
drive(fwd * 5, -CRUISE * 100 / 15, max(-45, min(45, -3 * tilt)))
wait(0.1)
trail, went = [], 0.0
def keep_up():
# the picture on the mat and the chart under the console
x, y = here()
if trail:
global went
went += math.hypot(x - trail[-1][0], y - trail[-1][1])
trail.append((x, y))
draw("path", trail[::3], "blue", "line")
plot("to goal cm", gap())
return x, y
def arrived():
stop()
print("at the goal after", clock(), "s, having driven", round(went), "cm")
draw("goal", [GOAL], "yellow", "squares", 8)
face(bearing())
mode = "dash"
for tick in range(600): # 60 seconds
x, y = keep_up()
if gap() < 8:
arrived()
break
if mode == "dash":
if distance() < HIT:
mode = "follow"
print("in the way at", round(x), round(y), "after", clock(), "s")
continue
step_to_goal()
else:
w = wall()
if w is None: # nothing in front: creep on towards the goal
step_to_goal()
continue
# once the goal is behind the wall's face, turn and look at it
if abs((bearing() - heading() + 180) % 360 - 180) > 100 and tick % 10 == 0:
back = heading()
face(bearing())
if distance() > gap() - 10:
mode = "dash"
print("the line to the goal is clear at", round(x), round(y),
"after", clock(), "s")
continue
face(back)
step_along_wall(w)
stop()
262 cm driven against a straight line of 191, and the chart falls, flattens while the robot slides along the crate, and falls again. On this mat Bug 0 is the best of the three.
It is also the only one of the three that can fail. Bug 0 remembers nothing at all, and a shape that curls back on itself can send it round the same loop for ever: it leaves the edge because the goal is straight ahead, meets the obstacle again, follows, leaves at the same place, and repeats. Nothing in the rule notices that it has been there before.
Bug 1: go all the way round first
Bug 1 buys a guarantee by being thorough. On meeting an obstacle it walks the whole way round it, keeping note of the point on the edge that was closest to the goal. Back at the hit point, it walks round again to that closest point, and leaves from there.
The program
from bugbot import *
import math
connect()
# change these numbers and press Run
GOAL = (170, 160) # where the robot is going, cm
STANDOFF = 20 # how far off the wall it follows, cm
CRUISE = 13 # how fast it slides along the wall, cm/s
START = (30, 30) # where the robot starts, cm
HIT = 22 # a reading closer than this is "in the way", cm
SEE = 60 # the fan ignores anything further off, cm
def here():
x, y = position()
return START[0] + x, START[1] + y
def gap():
x, y = here()
return math.hypot(GOAL[0] - x, GOAL[1] - y)
def bearing():
x, y = here()
return math.degrees(math.atan2(GOAL[0] - x, GOAL[1] - y)) % 360
def face(a):
# turn on the spot until the robot points that way
for i in range(80):
e = (a - heading() + 180) % 360 - 180
if abs(e) < 2:
break
drive(0, 0, max(-60, min(60, 1.5 * e)))
wait(0.05)
stop()
def wall():
# fit a straight line to the eight depth readings in front:
# (how far it is tilted in degrees, how far off it is in cm)
pts = [(d * math.sin(math.radians(a)), d * math.cos(math.radians(a)))
for a, d in scan() if d < SEE]
if len(pts) < 3:
return None
n = len(pts)
mx = sum(p[0] for p in pts) / n
my = sum(p[1] for p in pts) / n
sxx = sum((p[0] - mx) ** 2 for p in pts)
syy = sum((p[1] - my) ** 2 for p in pts)
sxy = sum((p[0] - mx) * (p[1] - my) for p in pts)
a = 0.5 * math.atan2(2 * sxy, sxx - syy)
return math.degrees(a), abs(my * math.cos(a) - mx * math.sin(a))
def step_to_goal():
# one tick of driving straight at the goal
drive(70, 0, 1.5 * ((bearing() - heading() + 180) % 360 - 180))
wait(0.1)
def step_along_wall(w):
# one tick of sliding along the wall, facing it, holding the standoff
tilt, off = w
fwd = max(-10, min(10, 1.5 * (off - STANDOFF)))
drive(fwd * 5, -CRUISE * 100 / 15, max(-45, min(45, -3 * tilt)))
wait(0.1)
trail, went = [], 0.0
def keep_up():
# the picture on the mat and the chart under the console
x, y = here()
if trail:
global went
went += math.hypot(x - trail[-1][0], y - trail[-1][1])
trail.append((x, y))
draw("path", trail[::3], "blue", "line")
plot("to goal cm", gap())
return x, y
def arrived():
stop()
print("at the goal after", clock(), "s, having driven", round(went), "cm")
draw("goal", [GOAL], "yellow", "squares", 8)
face(bearing())
mode, hit, best, best_gap = "dash", (0, 0), (0, 0), 1e9
for tick in range(900): # 90 seconds
x, y = keep_up()
if gap() < 8:
arrived()
break
if mode == "dash":
if distance() < HIT:
mode, hit, best, best_gap = "round", (x, y), (x, y), gap()
lap = went
print("in the way at", round(x), round(y), "after", clock(), "s")
continue
step_to_goal()
else:
if gap() < best_gap: # remember the best place to leave from
best, best_gap = (x, y), gap()
draw("closest point", [best], "green", "squares", 8)
if mode == "round" and went - lap > 80 and math.hypot(x - hit[0], y - hit[1]) < 12:
mode = "back"
print("all the way round after", clock(), "s and", round(went - lap),
"cm; the closest point was", round(best[0]), round(best[1]),
"at", round(best_gap, 1), "cm from the goal")
elif mode == "back" and math.hypot(x - best[0], y - best[1]) < 10:
mode = "dash"
print("back at the closest point after", clock(), "s")
face(bearing())
continue
w = wall()
if w is None:
step_to_goal()
continue
step_along_wall(w)
stop()
The green square on the mat is the closest point, and the chart shows what Bug 1 costs: the distance to the goal falls to 60.2 cm, climbs all the way back to 170 as the robot finishes its lap, and only then comes down for good. That is 591 cm driven for a 191 cm journey, most of it over ground it had already covered.
What that buys is certainty. Once the robot has been all the way round, it knows the closest point on that edge, and it knows there is nothing better. Bug 1 always reaches the goal if a route exists, and it can say so when one does not: if the leave point takes it straight back into the same obstacle, the goal is walled in.
There is even a promise about the distance. Lumelsky and Stepanov showed that Bug 1 never drives more than the straight-line distance plus one and a half times the total perimeter of the obstacles it meets. It is not fast, but it cannot surprise you.
Bug 2: leave when you cross the line again
Bug 2 keeps the straight line from the start to the goal, the m-line, and uses it as the rule for leaving. Follow the edge until you are back on that line and nearer the goal than the hit point was, then set off along it again.
The program
from bugbot import *
import math
connect()
# change these numbers and press Run
GOAL = (170, 160) # where the robot is going, cm
STANDOFF = 20 # how far off the wall it follows, cm
CRUISE = 13 # how fast it slides along the wall, cm/s
START = (30, 30) # where the robot starts, cm
HIT = 22 # a reading closer than this is "in the way", cm
SEE = 60 # the fan ignores anything further off, cm
def here():
x, y = position()
return START[0] + x, START[1] + y
def gap():
x, y = here()
return math.hypot(GOAL[0] - x, GOAL[1] - y)
def bearing():
x, y = here()
return math.degrees(math.atan2(GOAL[0] - x, GOAL[1] - y)) % 360
def face(a):
# turn on the spot until the robot points that way
for i in range(80):
e = (a - heading() + 180) % 360 - 180
if abs(e) < 2:
break
drive(0, 0, max(-60, min(60, 1.5 * e)))
wait(0.05)
stop()
def wall():
# fit a straight line to the eight depth readings in front:
# (how far it is tilted in degrees, how far off it is in cm)
pts = [(d * math.sin(math.radians(a)), d * math.cos(math.radians(a)))
for a, d in scan() if d < SEE]
if len(pts) < 3:
return None
n = len(pts)
mx = sum(p[0] for p in pts) / n
my = sum(p[1] for p in pts) / n
sxx = sum((p[0] - mx) ** 2 for p in pts)
syy = sum((p[1] - my) ** 2 for p in pts)
sxy = sum((p[0] - mx) * (p[1] - my) for p in pts)
a = 0.5 * math.atan2(2 * sxy, sxx - syy)
return math.degrees(a), abs(my * math.cos(a) - mx * math.sin(a))
def step_to_goal():
# one tick of driving straight at the goal
drive(70, 0, 1.5 * ((bearing() - heading() + 180) % 360 - 180))
wait(0.1)
def step_along_wall(w):
# one tick of sliding along the wall, facing it, holding the standoff
tilt, off = w
fwd = max(-10, min(10, 1.5 * (off - STANDOFF)))
drive(fwd * 5, -CRUISE * 100 / 15, max(-45, min(45, -3 * tilt)))
wait(0.1)
trail, went = [], 0.0
def keep_up():
# the picture on the mat and the chart under the console
x, y = here()
if trail:
global went
went += math.hypot(x - trail[-1][0], y - trail[-1][1])
trail.append((x, y))
draw("path", trail[::3], "blue", "line")
plot("to goal cm", gap())
return x, y
def arrived():
stop()
print("at the goal after", clock(), "s, having driven", round(went), "cm")
def side(x, y):
# which side of the line from the start to the goal, and how far off it, cm
dx, dy = GOAL[0] - START[0], GOAL[1] - START[1]
return ((x - START[0]) * dy - (y - START[1]) * dx) / math.hypot(dx, dy)
draw("the line", [START, GOAL], "green", "line")
draw("goal", [GOAL], "yellow", "squares", 8)
face(bearing())
mode, hit_gap = "dash", 0.0
for tick in range(600): # 60 seconds
x, y = keep_up()
if gap() < 8:
arrived()
break
if mode == "dash":
if distance() < HIT:
mode, hit_gap = "follow", gap()
print("in the way at", round(x), round(y), ",", round(gap(), 1),
"cm from the goal, after", clock(), "s")
continue
step_to_goal()
else:
# back on the line, and nearer the goal than where it left it
if abs(side(x, y)) < 4 and gap() < hit_gap - 5:
mode = "dash"
print("back on the line at", round(x), round(y), ",", round(gap(), 1),
"cm from the goal, after", clock(), "s")
face(bearing())
continue
w = wall()
if w is None:
step_to_goal()
continue
step_along_wall(w)
stop()
The green line drawn on the mat is the m-line. The robot leaves the crate at (120, 117), where the line comes back under it, and that is 66.1 cm from the goal against the 154.7 it had when it arrived.
side() is the only new piece. It gives the signed distance from the m-line, positive on one side and negative on the other, so "back on the line" is just a small number. That same quantity has a name in path following: the cross-track error.
The "nearer the goal than the hit point" test is what makes Bug 2 safe. Without it a robot can leave the edge at a point it has already tried, go round the same loop and never finish. With it, every leave point is closer to the goal than the last, and there are only so many of those, so the robot must arrive or run out of edge and be able to say the goal is unreachable.
Which one to use
| driven | time | remembers | always gets there | |
|---|---|---|---|---|
| straight dash | 36 cm, then stuck | never arrives | nothing | no |
| Bug 0 | 262 cm | 22.9 s | nothing | no |
| Bug 1 | 591 cm | 45.4 s | the closest point so far | yes |
| Bug 2 | 296 cm | 25.5 s | the m-line and the hit point | yes |
The straight-line distance is 191 cm, so even the best of them drives 37 per cent further.
On this crate Bug 0 wins and Bug 2 is a close second, which is the usual result for a simple convex obstacle met near the middle. Bug 1's thoroughness only pays on nastier shapes: a long spiral, or an obstacle whose edge happens to run the wrong way from where the robot met it, where Bug 2 can be sent a long way round and Bug 1 finds the best leave point by construction. Neither dominates the other. What is certain is that both always arrive, and Bug 0 does not.
Change GOAL in any of the demos and watch the comparison change. A goal at (170, 40) is on the other side of the crate and the robot meets it a different way; a goal at (60, 170) is reached without meeting it at all.
Where bug algorithms turn up
They are rarely the whole navigation system on a real robot, and they are all over the inside of one.
- As the escape hatch for a local method. A potential field gets stuck in a local minimum, and following the edge of the obstacle until the line to the goal is clear is exactly the way out. The potential field page does that on the mat next door.
- As the fallback when the map is wrong. A planner works out a route with A*, the route is blocked by something the map never knew about, and the robot needs to keep going rather than stop and replan the whole thing.
- As the ancestor of the wall follower. The left hand rule for a maze is boundary following with no goal test at all. Bug 2 is the same behaviour with the m-line added, which is why it gets out of mazes that defeat the wall follower.
- As the thing to beat. Bug 1's bound, the straight line plus one and a half times the perimeter, is the standard that a planner with a map has to improve on.
Where this is taught
- Getting round things is detect, sidestep, continue: the first obstacle avoidance, and the school version of the dash and follow.
- Project: the maze puts walls, corners and a goal together in one run.
- Go to a point is the first half of every bug algorithm: a vector to the target, straight through the inverse kinematics.
- The configuration space explains why the robot can be treated as a point as long as the obstacles are grown by its radius, which is what the standoff does here by hand.
- Potential fields is the local method that a bug algorithm rescues when it gets stuck.
- A* and the heuristic is what to use instead when there is a map.
- Cross-track error is the signed distance from a line, which is how Bug 2 knows it is back on the m-line.
- Finite state machines is the shape of all three programs: two or three states and the rules for moving between them.
- Project: plan a route and drive it does the job the other way round, with a map and a search.
Questions
What is a bug algorithm?
A way of getting a robot to a goal without a map. It drives straight at the goal, and when something blocks it, it follows the edge of that obstacle until a rule says it is worth setting off for the goal again. Bug 0, Bug 1 and Bug 2 are three different rules for that last decision.
What is the difference between Bug 1 and Bug 2?
Bug 1 walks all the way round an obstacle, notes the point closest to the goal, goes back to it and leaves from there. Bug 2 leaves as soon as it crosses the straight line from the start to the goal at a point nearer the goal than where it hit. Bug 2 is usually shorter, as it was on this page, 296 cm against 591. Bug 1 is more predictable, and on awkward shapes it can be the shorter of the two.
Is Bug 0 guaranteed to work?
No. Bug 0 keeps nothing in memory, so an obstacle that curls back on itself can send it round the same loop for ever. Bug 1 and Bug 2 both always reach a goal that can be reached, and both can report that a goal cannot be.
What is the m-line in Bug 2?
The straight line from where the robot started to the goal. Bug 2 uses it as the rule for leaving an obstacle: follow the edge until you are back on the m-line and closer to the goal than the hit point was. The signed distance from that line is a cross-track error, and computing it takes one line of arithmetic.
What is a hit point and a leave point?
The hit point is where the robot met the obstacle and started following its edge. The leave point is where it stopped following and set off for the goal again. Each algorithm is a different way of choosing the leave point.
How long can a bug algorithm's path be?
Bug 1 never drives further than the straight-line distance plus one and a half times the total perimeter of the obstacles it meets, which is a worst case you can work out in advance. Bug 2 has no such simple bound: on a shape whose edge crosses the m-line many times it can be much worse than Bug 1, and on ordinary obstacles it is much better.
Do real robots use bug algorithms?
Rarely on their own, and often as a part. A robot with a map plans with a search such as A* and gets a shorter route. Bug behaviour turns up as the recovery move when the map is wrong, and as the way out of the local minimum that traps a potential field.
What sensors does a bug algorithm need?
Something that says whether the way ahead is blocked, and something that lets the robot follow an edge. A bumper is enough for the first, and the original paper assumed touch alone. On this page the depth sensor does both jobs: a single reading for the dash, and a straight line fitted to the fan for the edge following.
Are bug algorithms on the GCSE or A level specification?
Not by name. None of the GCSE or A level Computer Science specifications (AQA, OCR, Edexcel, Eduqas) name them. The programming in them, a loop with two or three states and some coordinate geometry, is on both, and a bug algorithm makes a good A level project because the difference between a rule that works and a rule that is guaranteed to work is easy to demonstrate and hard to fake.
Learn it step by step
These lessons build the same ideas one at a time, each with tasks the simulator marks.
- 2.4 Getting round things Sensing, Robot club
- 2.6 Project: the maze Sensing, Robot club
- U2.6 Go to a point Kinematics and frames, University
- U9.1 The configuration space Planning, University
- U9.4 A* and the heuristic Planning, University
- U9.5 Potential fields Planning, University
- U9.7 Project: plan a route and drive it Planning, University
- U10.3 Cross-track error Following a trajectory, University
- A6.1 Finite state machines Theory of computation, A level