Bug 1 Algorithm

About

Perhaps the most straightforward path planning approach is to move toward the goal, unless an obstacle is encountered, in which case, circumnavigate the obstacle until motion toward the goal is once again allowable. Essentially, the Bug1 algorithm formalizes the “common sense” idea of moving toward the goal and going around obstacles.

Thanks to CS Columbia

Check out more from Robotics Caltech

Basic Assumptions

• The robot is treated as a point inside a 2D world.
• The obstacles (if any) are unknown and non-convex.
• Clearly defined starting point and goal.
• The robot can detect obstacle boundaries from a distance of known length.
• The robot always knows the direction and how far (in terms of Euclidean distance) it is from the goal.

Thanks to Wikipedia

Algorithm

• The robot moves towards the goal until an obstacle is encountered.
• Follow a canonical direction (clockwise) until the robot reaches the location of the initial encounter with the obstacle (in short, walking around the obstacle).
• The robot then follows the obstacle's boundary to reach the point on the boundary that is closest to the goal.
• Go back to step 1. Repeat this until the goal is reached.

Thanks to Wikipedia

Working Demo

• The first click on the grid shows the initial position of the robot in the environment
• The second click on the grid shows the goal position that the robot will attempt to reach.
• The rest of the clicks will create obstacles.
• Finally, once the environment is custom-created, click the space bar to see the algorithm in action.

demo.mp4