| |
CS 154 Homework #6 - implementing the BUG algorithms
Due 11:59 pm, Sunday, April 18, 2010
Implementing Bugs 0 1 and 2
For this part of the HW, you should start with the robot visualizer/simulator that was used
in assignment #1. It is linked from the course's Software page.
That framework provides the ability to use error-free position estimation and motor control
-- this assignment does not deal with noise in the sensors or actuators.
You may remember, as well, that that framework allows the user to click on a goal, which
then appears in the interface and its coordinates are available to the main control loop.
For this problem, you should start with this bug-friendly version of
our python simulator in order to
implement the three original "BUG" algorithms for robot navigation. Please have each
algorithm start when the 0, 1, or 2 key is pressed,
respectively.
Even if the system is already in the midst of another algorithm, it should be
straightforward to reset the starting point to the robot's current location and
begin the newly-selected approach. (Feel free to keep your old algorithm there for
comparison!)
To set the goal location, you'll need to hold down the g
key while left-clicking in the robot's environment.
You are welcome to start with your previous code (e.g., from the MCL
assignment), but the code linked above has
an extended getData function that provides range sensing in all four primary
compass directions -- this will be helpful for determining whether you should turn
left or right - or at all!
Here is a brief summary of the bug algorithms we covered more carefully in class:
- Bug 0 - heading toward the goal whenever possible, moving around obstacles when
the way is blocked. This is not guaranteed to converge, even if it's possible to drive to
the goal.
- Bug 1 - circumnavigating each obstacle encountered, remembering the minimum
distance to the goal achieved during that circumnavigation. Then, when the robot has
completed a full circuit, it returns to that minimum-distance location and continues toward
the goal.
- Bug 2 - remembers the "s-line" between the original starting point and the
goal. The robot proceeds as in Bug 1, but leaves an obstacle whenever it encounters the
s-line closer to the goal than it was when it was last on the s-line
Requirements
As the robot navigates, it should print out a message whenever it changes state, e.g.,
between "heading toward goal" and "circumnavigating obstacle." You might even have a finer
division of behvaiors into states, e.g., "turning left" or "turning right."
Simplifying assumptions
You may assume that all obstacles will be parallel to the x- or y-axis. So ninety-degree
turns should suffice in order to get around corners. Your system will have to handle other
turns after hitting an obstacle, because that might happen from any direction.
Caveats!
Keep in mind that you're controlling velocities and not positions of the robot! As a
result, you will have to allow for a margin of error in determining when the robot has
"reached the same point" or "reached the s-line" in the algorithms above.
|