18-642 Project 6

Updated 6/9/2024. Changelog

Learning objective: Work at the requirements & design level instead of the code level for making changes to a system.

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 do a redesign to solve arbitrary mazes that will not necessarily work using the left-hand and right-hand rules.

The learning objective for this project is to do high level design only WITHOUT contemplating detailed design and WITHOUT contemplating implementation.
Do NOT update statecharts until AFTER this project has been handed in. The point is to "think in requirements" and then "think in sequence diagrams."
Do not update your code.
Do Not Update Your Code.
DO NOT UPDATE YOUR CODE.
DO NOT UPDATE YOUR CODE.
DO NOT UPDATE YOUR CODE.

Lab Files:

• Virtualbox image; changelog) (Make sure you are using the latest version)
• VirtualBox software download
• New mazefiles for Project 6

Hints/Helpful Links:

• See the recitation notes on the course web site.
• Please follow the handin naming convention: every filename (before the file extension) must end in [FamilyName]_[GivenName]_[AndrewID].
• In this and future projects, $ECE642RTLE_DIR refers to ~/catkin_ws/src/ece642rtle (or corresponding project workspace).
• To be 100% clear, you can use a maze algorithm from a non-course related source (with attribution). Do NOT get your maze algorithm from another student (past or present), and do NOT get your maze algorithm from an 18-642 related solution source.
• See the Recitation video and slides on Canvas

Procedure:

1. Run your turtle with the new maze files:
   1. Copy p06_mazes.tar.gz over to your virtual machine and extract the mazes into $ECE642RTLE_DIR.
   2. As in Project 5, you can run the turtle with the new mazes using the command ./build_run_turtle.sh [mazefile].
   3. Watch your turtle attempt each maze. Your old turtle design is not expected to solve these mazes. By the end of the course, your turtle will need to solve all of them.
   4. Think about why these mazes aren't solvable using your current turtle robot.
2. DO NOT UPDATE YOUR CODE until after you complete statecharts in the NEXT project. Do not even look at your code.
3. Solution Strategy: Come up with a strategy so that your turtle solves the new mazes.
   • You should use 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/cell coverage algorithm as simple as possible. The project sequence will require you to create a statechart-based implementation, 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 evaluation 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 so that the emphasis is on representing an algorithm of moderate complexity in a good design process.
   • Recall the turtle behavior requirements from Project 5. You will have to demonstrate you meet these for later project phases.
     • 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 bumped for.
     • 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.
     • The turtle shall stop when it solves the maze via reaching the end square.
4. DO NOT UPDATE YOUR CODE until after you complete statecharts in the NEXT project. Do not even look at your code.
5. High level requirements: write high level requirements to describe your algorithm. 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 move.
6. Make sure your requirements use should/shall language and are numbered. If there is a particular maze following algorithm you are using it is OK to have a "compute subroutine" with some reasonable name that gets called, so you do not need to spell out each part of the algorithm if, for example, there is a complicated optimal tree search algorithm across an internal data structure. HOWEVER, each turtle movement shall be explicitly represented in the requirements, and ideally should indicate the basic logic being used to make the decision. There is some room for interpretation here, but the following examples should be helpful in providing guidance:
   1. OK: If square ahead is empty but MazeCompute() indicates this is an undesirable move the turtle shall turn right.
      Comment: This uses an algorithm to prioritize movements or override naive locally-based turtle movements
   2. Not OK: If MazeCompute() says turn right the turtle shall turn right.
      Comment: This makes the movement behavior completely opaque, and negates the point of actually having design information. You'll get no benefit at all from having a design review of this type of requirement.
   3. Better: If square ahead has a higher MazeCompute() score than the MazeCompute() score of the square to the right, the turtle shall turn right.
      Comment: This uses an algorithm to prioritize movements or override naive locally-based turtle movements
7. DO NOT UPDATE YOUR CODE until after you complete statecharts in the NEXT project. Do not even look at your code.
8. Sequence Diagrams: Create a set of sequence diagrams for your turtle. Create as many as you think you need to describe the behaviors in your algorithm.We do NOT want source code or native files for the sequence diagrams; just legible images (be careful of tiny font sizes that are illegible). Depending upon your turtle design, you might find the following hints helpful, but ultimately do what you think makes sense:
   1. Follow the Sequence Diagram style requirements listed below on this page.
   2. Some sequence diagrams might be only part of the total action taken to ultimately move the turtle between squares. It is OK to have to execute multiple sequence diagrams to handle a particular geometric situation. Often it is a good strategy to make small building block sequence diagrams to avoid a combinatorial explosion of complex long sequence diagrams.
   3. Having a different set of sequence diagrams for each starting orientation of the turtle is probably a bad idea; make them more generic (e.g., relative turtle position, not absolute turtle position)
   4. Have enough preconditions for each sequence diagram so it is unambiguous which sequence diagram should be executed next for any given turtle situation
   5. Start with a fairly small set of sequence diagrams for basic situations and only add a new sequence diagram if you encounter a hole in requirements or design that needs to be filled. Don't go crazy with huge numbers of sequence diagrams up front.
   6. Number each sequence diagram for traceability (e.g., SD-1, SD-2). Number each arc on each sequence diagram as well to make it easy in a review to say which arc is being talked about (e.g., arc #3 in SD-4 is simply SD-4.3)
   7. Do NOT use "Alternate," "optional," or "if/else" structures in your sequence diagrams.
9. SD to Reqs Traceability: Create a traceability table between the sequence diagrams and the requirements. The rows of this table shall be the SDs, and the columns shall be the requirements. We recommend you give each arc in each SD a row, but if you want one row to be then entirety of an SD that's OK too. (You'll find that for small SDs it doesn't matter much, but for large SDs you'll want multiple rows per SD.) This will result in ONE SD-to-requirements traceablity table for your whole project. You should have complete traceability here. (No empty rows, no empty columns.) If you think there is a compelling reason for an empty row or column then use a comment to explain why you think this is OK (these should be only a few special cases, if any).
   

   	R1	R2	..
   SD1	x
   SD2
   ..

10. Iterate: It will be no surprise if you find disparities between your SD and your requirements. Iterate until the Requirements and Sequence Diagrams are both talking about the same algorithm, and your traceability table is fully populated (with no blank rows; no blank columns).
11. DO NOT UPDATE YOUR CODE until after you complete statecharts in the NEXT project. Do not even look at your code.
12. Questions: Answer the following questions in a writeup:
    • Your name. (If the writeups are printed out, the file name info is lost, so put your name and Andrew ID in the document text as well)
    • Q1. In one or two sentences, why did your turtle fail at the more complicated mazes?
    • Q2. Briefly describe your solution strategy (your high level algorithmic approach). We have in mind 50-100 words, but shorter or longer is OK. This should be how you'd explain it to a friend, not a detailed algorithmic step-by-step description.
    • Q3. What difficulties did you encounter in this project?
    • Q4. The final version of your high level requirements after iteration. Start numbering at R1.
    • Q5. The final version of your sequence diagrams. SD1.
    • Q6. The final version of your traceability table for SD to Requirements.
    • (Note that all the design documents are handed in; we just didn't write questions for each one of them.)

Handin checklist:

1. Your writeup, named p06_writeup_[FAMILYNAME_[GivenName]_[AndrewID].pdf.
2. We want a SINGLE acrobat file, not a shower of small files that the TAs have to go through individually.
   • Fonts for all diagrams and text shall be rendered at no smaller than 10 point font. Smaller fonts will require a resubmission
3. There is no code hand-in this week.

• DO NOT UPDATE YOUR CODE until after you complete statecharts in the NEXT project. Do not even look at your code.

The rubric for the project is found here.

Sequence Diagram Style requirements:

• Do NOT use "return" arcs in the sequence diagram. Some of you might have seen a particular style of using SDs that requires every arc to paired with a "return" arc. DO NOT DO THIS! That style is commonly used for enterprise/transaction type computing explanations (and often has procedure calls on the arcs). It also skips the statechart part of the design process, because it amounts to turning the sequence diagram into a multi-object flowchart. While that can be a valid use for transaction systems, it is NOT the design process we are going to follow. Similarly, do not use "optional" or "alternate" boxes in your SD. That leads to SDs that are too complex, and defeats the method we are using that will end with statecharts (again, those SDs have their place, but they lead off the path we are trying to follow in this course). There is no one single "right" way to use SDs in the real world, but there are many ways that lead away from the path we'd like you to follow for the learning exercises in this course.
• Use of "alt" is strictly forbidden in SDs, along with "if/else" and other similar logical alternative structures for SD notations. Multiple SDs should be submitted instead showing each alternative as a separate SD.
• Use of "loop" is strictly forbidden in SDs. Smaller SDs that can be executed multiple times should be used with no explicit "loop"/"while"/etc. structure
• For the turtle project you should NOT be setting explicit state variables in SDs because there is no user-visible mode of operation.

Changelog:

• 6/9/2024: Released