Implementing Bug Algorithms with a simulated mobile robot

• Bug algorithms are inspired by ants                                                                 04/21/2019
• Bug algorithms do not assume global knowledge, they only assume local knowledge of the environment and a global goal
• Behaviors are
  • Follow a wall
  • Move in a straight line toward a goal
• Blog post borrows from motion planning lecture slides of Howie Choset

Assumptions

• Known direction to goal. Robot can measure distance d(x,y) and between points x and y
• Local sensing: walls/obstacles, encoders for odometry
• Reasonable world
  • finitely many obstacles in any finite area
  • a line will intersect an obstacle finitely many times
• Workspace is bounded
  • The world has a finite area

Routines

1. follow_wall():
   1. Move along the length of the obstacle til you get to the end of it. There will be free space at the end of the wall
2. go_to_point(p):
   1. Move in a straight line to point p.

Flavors

1. Bug 0
   1. Robot orients itself to face goal position
   2. If there are no obstacles between robot and goal (or in the robot’s locale), go_to_point(goal)
   3. If there is an obstacle, turn left and follow_wall()
   4. Go to (a)

Fails in this world. Algorithm is not complete.

2. Bug 1

1. Robot orients itself to goal position.
2. go_to_point(goal)
3. If there is an obstacle, follow_wall() along entire obstacle til you get to start position. On your way, store your coordinate closest to goal
4. Move from start position to that coordinate. Make current position start position
5. Go to (a)

Bug 1 basically first scouts the environment to find a way around the obstacle that gets the robot closer to the goal. It then goes back to its start position and moves to that position.

 

3. Bug 2

1. Draw m-line, a straight line from start to goal position.
2. Orient robot in m-line direction and go_to_point(goal)
3. If there is an obstacle, follow wall til robot intersects m-line again at a point closer to goal than start position. Update current position as start position
4. Go to (b)

Bug 2 illustration

Bug 1 vs Bug 2

• Both are complete algorithms
• Bug 1 is an exhaustive search algorithm. It looks at all choices before commiting.
• Bug 2 is a greedy algorithm. It takes the first thing that looks better.
• Bug 2 outperforms Bug 1 in many cases.
• Bug 1 has a more predictive performance overall.