Bug Algorithms
Bug Algorithms
Bug Algorithms
Shmuel Wimer
Bar Ilan Univ., School of Engineering
April 2011
The robot moves along a line from qstart to qgoal until it hits
an obstacle at a hit point - q1,hit.
It circumnavigate the obstacle until it returns the hit point.
It then determines the nearest point to qgoal and traverses
along the boundary to that leave point - q1,leave.
From q1,leave it heads straight to qgoal again.
The algorithm terminates when qgoal is reached or the
planner determines that qgoal is not reachable.
April 2011
April 2011
April 2011
1 n
d qstart , qgoal i 1 ni pi
2
10
Tangent Bug
The robot has an azimuth distance sensor with infinitesimal
angular resolution. For every point of an obstacle, azimuth
distance is defined:
: R2 0,360 R..
For cos ,sin Ui WO i , .define
T
April 2011
11
R is piecewise continuous.
The tangent Bug planner
assumes that the robot can
detect discontinuities in R.
April 2011
Intervals of continuity:
[O1,O2] , [O3,O4],
[O5,O6] and [O7,O8]
12
13
14
t 1
t2
t 3
15