Bug algorithm is a class of
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
that helps robots deal with
motion planning
Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used ...
.
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
In mathematics, the Euclidean distance between two points in Euclidean space is the length of the line segment between them. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, and therefore is o ...
) it is from the goal.
Algorithm
The most basic form of Bug algorithm (Bug 1) is as follows:
#The robot moves towards the goal until an obstacle is encountered.
#Follow a canonical direction (clockwise) until the robot reaches the location of 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.
See also
*
Pathfinding
Pathfinding or pathing is the search, by a computer application, for the shortest route between two points. It is a more practical variant on Maze-solving algorithm, solving mazes. This field of research is based heavily on Dijkstra's algorith ...
*
Motion planning
Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used ...
References
{{reflist
Robot kinematics