18-642 Project 6
Page last updated 9/7/2018 (changelog)
This project gives you new maze files to solve. These files are not
solvable by the left hand or right hand rule. The objective of this project is
to lay ground-work for writing new requirements for your turtle, which you will
implement as a state chart in future projects.
- See the recitation notes on the course web
- Please follow the handin naming convention: every filename (before the
file extension) must end in [AndrewID]_[FamilyName]_[GivenName].
- In this and future projects, $ECE642RTLE_DIR refers to
~/catkin_ws/src/ece642rtle (or corresponding project workspace).
- Run your turtle with the new maze files:
- Copy p06_mazes.tar.gz over to
your virtual machine and extract the mazes into $ECE642RTLE_DIR.
- As in Project 5, you can run the turtle with the new mazes using the
command ./build_run_turtle.sh [mazefile].
- For Project 6, you are required to solve m1.maze, m2.maze, and m3.maze. In
future projects, you will be required to solve the other mazes.
- Come up with an algorithm so that turtle solves the new mazes.
- Leverage the visit count array you implemented in Project 5.
- Instead of thinking about this as a maze-solving problem, you can think of
it as a cell coverage problem: if your turtle tries to visit every cell in the
maze, it will eventually visit the end cell. A greedy algorithm based on
examining adjacent cell visit counts is a good place to start.
- We strongly suggest you make the maze-solving algorithm as simple as
possible. The next projects will require you to create a statechart-based
design, create complete unit tests, and so on. The more complicated your code,
the more work you will be making for yourself to show that your turtle design
is correct. In particular, you might wish to avoid using global data-structure
based algorithms such as depth-first search or breadth-first search. (If you
want to use these approaches, we suggest you have a brief chat with the course
instructor to make sure you don't get overwhelmed with workload downstream.)
- Your algorithm shall not use a random/pseudorandom number generator.
This is explicitly intended to dis-allow solutions that depend upon random
walks to eventually solve the maze. We want a deterministic (non-random)
approach to solving the maze.
- A good solution algorithm will not visit any cell more than 3 times. If you
visit a cell more than 3 times you will still receive full credit for this
project, but we suggest you reconsider your algorithm if you see this
happening. Be sure to check the grading rubric for how this item is treated.
- Recall the turtle behavior requirements from Project 5:
- The turtle shall not move more than one adjacent square per call to tick.
- The turtle shall rotate at most 90 degrees per tick.
- The turtle shall only move in the direction it is facing.
- The turtle shall be facing the potential wall segment that it is calling
- The turtle shall make at most one call to bumped per tick. (You
can make it before or after movement, but you should make the call at a
consistent point in the move cycle.)
- The turtle shall not move through walls.
- Write down requirements for this new algorithm. You will turn these
requirements in as part of the checkpoint handin. These should be functional
requirements from the software point of view (i.e., high level software
requirements).They should not refer to internal state variables. As an
example, requirements for the Project 2 left-hand rule could be:
- R-1: If the turtle is obstructed by a wall, the turtle shall turn right.
- R-2: If the turtle is not obstructed by a wall, the turtle shall move one
square in the direction it is facing.
- R-3: If the turtle has just completed a move forward, it shall turn left
regardless of obstruction.
- R-4: If the turtle has reached the end square of the maze, it shall not
- Implement your algorithm. Revise your requirements if you need to.
Remember, you must solve mazes m1, m2, and m3 for Project 6. The other mazes
are optional for this project, but you must attempt them.
This will give you a feel for how much work will be required when you need to
solve these and other similar mazes in future projects.
- Answer the following questions in a writeup:
- Your name. (If they are printed out, the file name info is lost.)
- Q1. Briefly describe the algorithm you implemented.
- Q2. Include the final requirements you used from steps 4 and 5. Number the
requirements starting from R-1.
- Q3. Include screenshots of the turtle solving m1, m2, and m3.
- Q4. Did your turtle succeed in solving all of the other mazes? Name any
mazes your implementation did not solve. If your turtle did not solve the
mazes, why (give us your best guess as to algorithm problem, or describe the
behavior that seemed to result in not solving the maze)? How would you change
your algorithm so that it could solve the mazes (it's OK to be pretty high
level here; we just want you to show you've started thinking about this)?
- Q5. What difficulties did you encounter in this project?
- Your $ECE642RTLE_DIR directory, compressed and named
p06_ece642rtle_[AndrewID]_[FamilyName]_[GivenName].zip (.tar.gz is also
- Your writeup, named
Zip the two files and submit them as Project6_[Andrew
ID]_[Family name]_[First name].zip. Yes, this means you'll have a
zip file inside another zip file.
The rubric for the project is found here.
- 9/7/2018 5:00PM: Released