Obstacle avoidance is an indispensable behavior in mobile robots. If a robot has no sensors, it’s a blind robot. If it has proximity sensors but still it keeps hitting whatever comes in its way, then it’s a ‘’brainless’’ robot. Imagine an ant or any insect walking on the ground. The insect is heading towards a particular direction and it encounters an obstacle in its way. What the insect does is, it circumnavigates the obstacle until motion in the initial direction is no more obstructed. The situation is very similar to a car at a cross road. To go straight from a traffic crossing, the car has to circumnavigate the cross-road circle and go straight.
Assumptions and initialization
Essentially, the Bug-1 algorithm formalizes the “common sense” idea of moving towards the goal and going around obstacles. Certain assumptions have to be made while implementing the Bug-1 algorithm, they are:
- The robot is assumed to be a point with perfect positioning (no positioning error)
- The robot is equipped with a contact sensor that can detect an obstacle boundary if the robot “touches” it.
- The robot can also measure the distance d(p, q) between any two points p and q.
- Finally, assume that the workspace is bounded. That is, we're not working in infinite space.
We assume the following symbols:
- qstart: start point
- qgoal: target point
Let qL0 =qstart m-line - line segment that connects qLi to qgoal. Initially i = 0
The Bug-1 Algorithm
The Bug1 algorithm exhibits two behaviors:
- Motion to goal
- Boundary following
During motion-to-goal, the robot moves along the m-line toward qgoal until it either encounters the goal or an obstacle. If the robot encounters an obstacle, let qH1 be the point where the robot first encounters an obstacle and call this point a hit point. The robot then circumnavigates the obstacle until it returns to qH1.
Then, the robot determines the closest point to the goal on the perimeter of the obstacle and traverses to this point. This point is called a leave point and is labeled qL1. From qL1, the robot heads straight toward the goal again, i.e., it re-invokes the motion-to-goal behavior.
If the line that connects qL1 and the goal intersects the current obstacle, then there is no path to the goal; note that this intersection would occur immediately “after” leaving qL1 .
Otherwise, the index i is incremented and this procedure is then repeated for qLi and qHi until the goal is reached or the planner determines that the robot cannot reach the goal. Finally, if the line to the goal “grazes” an obstacle, the robot need not invoke a boundary following behavior, but rather continues onward towards the goal.
Here's a pseudo code implementation of this algorithm:
Input: A point robot with a tactile sensor
Output: A path to the qgoal or a conclusion no such path exists
while Forever do
From qLi−1, move toward qgoal.
until qgoal is reached or an obstacle is encountered at qHi .
if Goal is reached then
Follow the obstacle boundary.
until qgoal is reached or qHi is re-encountered.
Determine the point qLi on the perimeter that has the shortest distance to the goal.
Go to qLi .
if the robot were to move toward the goal then
Conclude qgoal is not reachable and exit.
(adopted from: Principles of Robot Motion: Theory, Algorithms, and Implementations (Intelligent Robotics and Autonomous Agents))
You learned about a very basic obstacle avoidance algorithm. The idea is to navigate the entire circumference of the obstacle and figure out the best position to leave towards the goal. Then, the robot moves to this best leaving position and goes towards the object. It is easy to determine if an object is unreachable by this method or not.