|
Carnegie Mellon University |
|
The Robotics Institute. |
|
Robotic Motion Planning, 16735: Homework 2 |
|
Bug 2 Algorithm |
|
I decided to implement the bug 2 algorithm. The implementation is in Matlab. Since the bug 2 algorithm is primarily for robots with tactile only sensing I chose not to plan in the configuration space as obstacles are not sensed apriori. The implementation allows creation of any number of polygonal obstacles.
Algorithm 1. Move towards goal on the m-line 2. Follow obstacle upon hitting obstacle 3. Move towards goal on hitting the m-line and at distance closer to the goal, repeat 1-3 until goal reached. Exit with failure if 3 not possible
Implementation The user first selects the start and goal points by clicking on the figure. Then he selects the vertices for the obstacle by clicking on the figure again. The robot is modeled as a circular disc. Using the start, goal and vertices the program constructs the m-line and obstacles. The robot then moves along the m -line till the circumference of the disc intersects with an obstacle. The robot follows the algorithm and reaches the goal if possible. The program returns a message of failure when it discovers that no paths to the goal exist. In the figure below the obstacles are in red, the path followed is the collection of blue circles, the start point is in green, and end is in black).
|
|
The bug 2 algorithm is unique from both the bug 1 and tangent bug algorithm in that it is least dependent on the distance metric. The bug 1 requires considerably more memory. The tangent bug depends a lot on sensor information. |