18-642 Project 7

Released for 2019
Page last updated 9/29/2018 10 AM (changelog)

This project has you take your implementation from Project 6 and treat it as a prototype. In other words, going through the project 6 process gave you insight into the application domain, but the resulting code is not necessarily what you'd really want for a commercial product.

For this project we want you to do a more rigorous design process including: sequence diagrams, product requiremnents, statecharts, code, and traceability. It is perfectly fine to re-use portions of your existing work if you like, but we caution you not to make this an exercise in "documenting" the code you already have. While it is possible you'll end with the exact same code if you start with a clean design, in many cases this process will result in a better, more understandable, and more maintainable piece of software. We urge you to treat this as a clean sheet design process as you would do for a second-generation project rather than trying to force-fit the documentation into the code you already have. ("Clean sheet" means you still retain your experience and domain knowledge, but you don't try to simply edit previous pieces to fit the new design.) Remember, if you do the design right, then coding is the easy part. You'll be carrying this new code base forward for the rest of the project phases, so it's worth your while to get it right.

This project spans two weeks and should be about two weeks of project work. We are assigning it as a two-week chunk to give you more mid-semester time management flexibility as you complete work for other courses. We strongly recommend you try to get ahead and take a first pass through as much as you can on week 1 so you don't have a time crunch on week 2. There is a week 1 checkpoint deliverable that is most likely LESS than half the total work to give you some flexibility. We recommend that if possible you try to do MORE than the minimum in the first week so you aren't crunched at the deadline for week #2. But, if you are overwhelmed with another course it's up to you how you prioritize and manage your time. Note that here are TWO peer reviews (one per week). Make sure that for the second peer review you bring the materials from the first review so that the second review can compare detailed design information against requirements

Lab Files:

Hints/Helpful Links:


  1. Sequence Diagrams: Create a set of sequence diagrams for your turtle. Create as many as you think you need to describe the beaviors you were trying to design in to the turtle in the previous project. 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. 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.
    2. 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)
    3. Have enough preconditions for each sequence diagram so it is unambiguous which sequence diagram should be executed next for any given turtle situation
    4. 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.
    5. Number each sequence diagram for traceability (e.g., SD-1, SD-2). We strongly urge numbering 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)
  2. System Behavior Requirements: Create a set of requirements that capture all the non-trivial aspects of the sequence diagrams. Make them descriptive in terms of the common properties of the sequence diagrams. Make sure the 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. 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 MazeComput() 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. 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).
    Note that at this point in principle you can do the first peer review. HOWEVER, you might want to work on some of the later steps to find holes in this initial part of your design that are reflected back up into the sequence diagrams and requirements. We strongly recommend you schedule this review no later than during the day on Friday (even better: during the day on Thursday) and use any extra time before the Friday night hand-in deadline to work on the statechart and fix any issues found in review.
  4. State chart: Draw a state chart for student_turtle based on the requirements. (If it makes sense to break the design down into multiple state charts that is OK. Make sure each statechart has unique labels and numberings for traceability.)
    1. Define the inputs, outputs, and internal variables in a table:
      Name Type Range Description
      bumped input {TRUE, FALSE} Tells the turtle whether it has just bumped a wall
      move output {turn_left, turn_right, move_forward} The next move the turtle shall make
      ... ... ... ...
    2. Follow the conventions set forth in class and the homeworks to make a state chart. In particular, all output variables you described in the table must have an output at all states, and transitions shall only occur on checks on input variables or internal variables defined in the table. Make sure the initial state is indicated with an arrow, and that all states and transitions are numbered. You are allowed to use sub-states if it makes sense for your design. (Look up a tutorial on advanced state chart notation if you like.)
  5. Compute Functions: If you used a compute function of some sort in your sequence diagrams, then that compute function should be showing up as more or less a macro in your statechart (e.g., as a guard condition). For all such compute functions create an appropriate design description. Depending upon the compute function this might be a state chart, a flowchart, control equations, or a pseudocode algorithm. Each compute function should have its own design. (If there is no compute function of this type simply say "no compute function" and you will receive full credit assuming that statement is actually true.
  6. Reqs to Detailed Design Traceability: Perform traceability of requirements to statechart and compute function using a table. (If you have multiple state charts use either one bigger table or multiple smaller tables to trace all of them.) Each state and transition shall be a row in the table (compute functions should be one or more rows as well), and each requirement shall be a column:
    R1 R2 ..
    S1 x

    Because your requirements are product-level requirements, and your statechart is low-level design, it is possible that a requirement might trace to more than one state or vice versa. That is allowed and expected, as long as you achieve full traceability: each row and each column must have at least one cell checked off. If a row has zero cells checked off, that means the corresponding state or transition does not meet any requirements and is extraneous. If a column has zero cells checked off, that means the corresponding requirement is not being fulfilled by any states or transitions. Revise your requirements and statechart until you achieve full traceability. (If there is a compelling reason not to have full traceability, explain specifically why.)
    Note that at this point you can hold review #2, which does NOT include code. you shall fix any review defects found.
  7. Implementation: Implement your design (i.e., statechart + compute function(s)) in student_turtle.cpp
    1. Your top-level statechart implementation shall be a function in ANDREWID_student_turtle.cpp, which shall contain a switch statement with cases for every state. See the point below for details. Since your statechart implements the turtle movement logic, no part of your statechart implementation shall be in ANDREWID_student_maze.cpp.
    2. Define a current state variable, and use a switch statement to switch between current states. (For the following writeup items, we use the term "the state's block" to refer to the case of the switch statement that handles the current state.)
    3. Make sure all outputs are being set in all state blocks.
    4. Put transition logic at the end of the state's block. This should check internal variables and input variables and set the current state variable accordingly.
    5. Comment each state and transition with its label ("S1" or "T1") in the code. You will be graded on the traceability of statechart to code, so make sure you have an accurate label for each state and transition. Refer to the recitation for an example.
    We highly recommend that you write this implementation from scratch, instead of manipulating your existing student_turtle code. This way, it will be clear that your turtle movement code implements your statechart.
  8. System Test: Verify that your implementation still works on mazes m1-m3. Remember you can run the code with a given maze file by providing it as an argument to build_run_turtle.sh: ./build_run_turtle.sh [mazefile]
    to give some time management flexiblity, this code shall compile and execute, causing the turtle to move at least one square. It shall also conform to the statechart. HOWEVER, if it does not actually solve the maze you will still get full credit for this project. (You'll want to fix that in the next project phase, and we suggest you try to fix it now, but this prevents there being an all-nighter debugging session between you and a hand-in. Caution -- if you take this as license to ignore writing code, the next project phase will have a high workload.)
  9. Peer Review #1: Perform the first peer review. This will be due at the first week checkpoint. You only need to review the sequence diagrams, requirements, and traceability between them.
    1. Your groups are assigned on canvas.
    2. BEFORE the review, create a brief checklist of items to look for in this review. They should include items specifically relevant to sequence diagrams, items specifically relevant to requirements, and items specifically relevant to traceability. You can manage this however you like, including having each group member proposing a specific part of a checklist, merging proposals from the team members to create a unified checklist, or having each team member reviewed according to a checklist they propose (i.e., use the author's checklist). A good checklist should have perhaps 12-25 items on it covering all the elements that are to be reviewed. You'll individually hand in whatever checklist was used to review your code regardless of who wrote it. You are responsible for ensuring that the checklist used is reasonable for the purposes. You can update or substitute checklists before you are reviewed if you think the group is going to use an inadequate checklist.
    3. As in previous reviews, assign a scribe and a leader for each review. Allocate 30 minutes per review. The person whose artifacts are under review should be the scribe. By the end of all reviews in your group, everyone should have taken a turn being the leader.
    4. Remember the peer review guidelines: inspect the item, not the author; don't get defensive; find but don't fix problems; limit review sessions to two hours; keep a reasonable pace; and avoid "religious" debates on style.
    5. Fill out the usual peer review recording spreadsheet (or something similar) for each review. Fix any defects you can before handing in the checkpoint. Defer any major rework by writing "deferred" or similar wording to the review issue log spreadsheet as appropriate.
    6. To make sure this is completely clear, this review DOES NOT INVOLVE CODE AT ALL -- it is a review of the high level design (sequence diagrams and requirements).
  10. Peer Review #2: Perform the second peer review. Use the same procedure as the first peer review, including making checklist(s) for the review. You can change how you do the checklist based on any lessons learned from the first review. The difference is that this review covers detailed design review (statechart, compute functions, traceability from requirements to detailed design). It does not re-review sequence diagrams, requirements, or actual implementation (source code).
  11. Writeup: Answer the following questions in a writeup:

Checkpoint Handin Checklist:

Final Project Handin Checklist:

Use the usual project naming conventions with a prefix of "p07" for items other than source code.

We would strongly prefer that everything except the code shows up in a single acrobat file for ease of navigation. If you really must, it is OK to have each handin item typebe a separate file (e.g., all sequence diagrams in one file different from all the other files.)

The rubric for the project is found here.