Motion Planning HW #2

Due : Sept/12/2007

Problem

On your web page, show at least two movies - one that illustrates a successful planning episode, and one that fails. Include on your web page a brief description (pdf file or html ONLY) of your approach. This report should include all relevant equations and algorithm descriptions, along with a description of any parameters used by your algorithm.

In addition to the required explanations, explain why you chose this particular bug algorithm.

Solution

I implemented three algorithm which are Bug1, Bug2, Tangent Bug Algorithm using MATLAB GUI that I made as HW #1.

Workspace Description : Workspace has 2-Dimension and bug has 2 DOF which is position. Although I implemented 3 DOF in HW #1, Bug Algorithm does not concern of orientation so much thus I did not implement in HW #2. However, as a future works, if I use configuration space technique, orientation control is also possible.

- Bug1 Algorithm

Bug1 Algorithm is the most simple algorithm among Bug Algorithm. It goes toward goal and if it faces obstacles then it follows boundary of the obstacle as measuring distance between current position and goal. After getting back to initial position, it finds the shortest points and goes that point. It does this process until getting to goal.

• WHILE
  • REPEAT
    • from q_L(i-1), move toward q_goal
  • UNTIL q_goal is reached OR an obastacle is encountered at q_H(i)
  • IF goal is reached
    • ENDIF
  • ENDIF
  • REPEAT
    • follow the obastacle boundary
  • UNTIL q_goal is reached OR q_H(i) is re-encountered
  • determine the point q_L(i) on the perimeter that has the shortest distance to the goal
  • go to q_L(i)
  • IF the robot were to move toward the goal
    • conclude q_goal is not reachable and EXIT
  • ENDIF
• ENDWHILE

This algorithm is quite exhausted because robot should all perimeters of obstacles and in worst case 1.5 times of all perimeters of the obstacles robot faces. This makes robot exhausted and sometimes it can fall in infinite loop. Below examples show how the Bug1 algorithm works and mission completion. And failed situtation is also when the goal position is in obstacle.

BUG1 SUCCESS (Right direction)

BUG1 FAILED (Right direction)

- Bug2 Algorithm

Bug2 Algorithm is improved algorithm in some sense because it does not have to follow all perimeters of the obastcle it faces. It leaves the obstacles when it meets intersection between line from start point to goal point and obstacles if possible. So it leaves the points as close as goal but sometimes this technique cause serious problem. As I mentioned, if bug selects wrong direction in escaping spiral obstacle, it has to take a walk even much more than Bug1 algorithm. Example shows how it works and situation when exhausted and when failed.

• WHILE
  • REPEAT
    • from q_L(i-1), move toward q_goal along m-line
  • UNTIL q_goal is reached OR an obastacle is encountered at hit point q_H(i)
  • IF goal is reached
    • ENDIF
  • ENDIF
  • REPEAT
    • follow the obastacle boundary
  • UNTIL
    • q_goal is reached OR
  • q_H(i) is re-encountered OR
  • m-line is re-encountered at a point m such that (m != q_H(i)), (d(m, q_goal) < d(m, q_H(i))
  • q_L(i+1) = m
  • i++
• ENDWHILE

BUG2 SUCCESS (Left direction)

BUG2 SUCCESS BUT EXHAUSTED (Right direction)

BUG1 FAILED (Left direction)

- Tangent Bug Algorithm

Tangent Bug Algorithm takes more realistic idea. It has range sensor which can detect distance from current position to obstacles or goal. The scope of range sensor is limited so it does not know how workspace looks like unlike Bug2 algorithm which bug can figure out where m-line meet with obstacles. Thus this is more realistic and tough to complete mission. However, since it adopts still basic idea of motion to goal and boundary following but smarter way, the path becomes shorter and desirable.

Key idea of Tangent Bug algorithm is using raw distance function

Raw distance function has discontinuous when obstacles faces. When bugs faces obstacles, it two end points which are boundary of raw distance function and blocking goal. Then bug choose shorter path which connects current position to end points and end points to goal. So when end point exist, bug's target changes whenever it moves. Finally the trajectory of bug is generated tangential with respect to boundary of obstacle locally. However, sometimes there is local minimum points no longer distance is diminished. At that situation, bugs goes in direction of it used and following boundary. Also it memorize the local minimum distance and it leaves obstacle when distance is smaller than local minimum if possible.

• WHILE
  • REPEAT
    • continuously move toward the point n belong to [T, O(i)] which minimizes d(x, n) + d(n, q_goal)
  • UNTIL
    • the goal is encountered OR
    • the direction that minimizes d(x, n) + d(x, q_goal) begins to increase d(x, q_goal) - local minimum
  • choose a boundary following directino which continues in the same direction as the most recent motion-to-goal direction
  • REPEAT
    • continuously update d_reach, d_followed, and [O(i)]
    • continuously moves toward n belong to [O(i)] that is in the chosen boundary direction
  • UNTIL
    • q_goal is reached OR
  • the robot completes a cycle around the obstacle in which case the goal cannot be achieved.
  • d_reach < d_followed
• ENDWHILE

I implemented this algorithm without thinking of boundary of robot. Below examples show how Tangent Bug algorithm works and fails. This algorithm returns fail when the goal is in obstacles. At first it keeps track end point of range sensor and follows the boundary. However, since there is no connection between current position and goal, the algorithm returns fail.

TANGENT BUG SUCCESS 1

TANGENT BUG SUCCESS 2

TANGENT BUG FAILED

- Program implementation

This program has several features and user oriented graphic interface which makes easy to utilize

Frame structure

- Future works

As I mentioned before, this algorithm does not contain checking contact with boundary and orientation control. These should actaully be implemented in this HW but I ran out of time. In order to be robust my program, also I think I have to experiment it on unexpectable situation.

- Reference

H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki and S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations,
MIT Press, Boston, 2005.