# Bug algorithm

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Bug_algorithm
> Markdown URL: https://mediated.wiki/source/Bug_algorithm.md
> Source: https://en.wikipedia.org/wiki/Bug_algorithm
> Source revision: 1355423761
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

**Bug algorithm** is a class of [algorithm](/source/Algorithm) that helps robots deal with [motion planning](/source/Motion_planning).[1][2]

## Basic assumptions

- The robot is treated as a point inside a 2D world.
- The obstacles (if any) are unknown and nonconvex.
- There are clearly defined starting point and goal.
- The robot is able to detect obstacle boundary from a distance of known length.
- The robot always knows the direction and how far (in terms of [Euclidean distance](/source/Euclidean_distance)) it is from the goal.

## Algorithm

The most basic form of Bug algorithm (Bug 1) is as follows:

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

## See also

- [Pathfinding](/source/Pathfinding)
- [Motion planning](/source/Motion_planning)

## References

1. [BUG Algorithms](http://msl.cs.uiuc.edu/~lavalle/cs497_2001/book/uncertain/node3.html).

1. Choset, Howie. [*Robotic Motion Planning: Bug Algorithms*](https://www.cs.cmu.edu/~motionplanning/lecture/Chap2-Bug-Alg_howie.pdf). Carnegie Mellon University.

---
Adapted from the Wikipedia article [Bug algorithm](https://en.wikipedia.org/wiki/Bug_algorithm) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Bug_algorithm?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.