18-642 Project 5

Updated 8/26/2022. Changelog

Learning objectives: (1) A gentle introduction to how software algorithms interact in a simulation with models of the real world. (2) Experience a change of requirements that results in refactoring code to separate concerns (in this case, environmental model vs. robot model). (3) Experience harmonizing a SD, statechart, and code for this simple version of your turtle robot to prepare you for doing that with more complicated project code later.

NOTE: Students in previous semesters have said that this project is more technically challenging, and wish they'd started sooner. We recommend an early start!

This project has you split the turtle maze solver into two separate files. One file keeps track of the turtle as it sees the world, and the other translates the turtle coordinates to a turtle position. This project also has the turtle keep track of its knowledge of the world in its own local array. (Technically: a file static array.)

In the real world, a robot does not know in advance what the map looks like. Splitting apart the map and the robot allows you to work with the notion of the robot having to figure out its surroundings without being able to "cheat" by asking the map where it is and what's around the corner. This is what you'd expect in both real robot software and robot software running in a simulated world. Put another way, robots need to build a model of the world as they go. Think of this as a really gentle, simple introduction. For serious robots, you use SLAM. (Yes, some self-driving cars use high definition maps to help. But still someone has to build the maps, which amounts to building a model of the world, and at run-time the cars can only use the maps as strong hints, since the world might have changed since the last map update.)

NOTE: this project includes the outputs of homework assignments on Sequence Diagrams and Statecharts. We strongly recommend you complete those lectures and homeworks BEFORE you start working on this lab.


Lab Files:


Hints/Helpful Links:


Procedure Part 1 -- file split

  1. Split the scope of your code between two files, ANDREWID_student_maze.cpp and ANDREWID_student_turtle.cpp. Refer to the function skeletons in ANDREWID_student_maze.cpp to get you started. You should also modify student.h to include any data structures or helper methods you need. You can create new functions and modify things in general in other files as seems reasonable to you -- but we recommend restraint to avoid making things harder than they have to be. If you think changing something is necessary to meet the spirit and intent of splitting things up, do it. If in doubt check with a TA in office hours. (Do not change the file name of student.h because that will break your build.)
  2. At a high level, [..]_turtle.cpp keeps track of how the turtle should move with no knowledge of the world, while [..]_maze.cpp translates these turtle moves to absolute coordinates and provides a model of the outside world so that the turtle code can be exercised via simulation. (If you had a real physical turtle bot, and a real physical maze, you wouldn't need the maze code, but you'd still need the turtle code.):
    ANDREWID_student_maze.cpp (maze coordinates)
    1. The code in this file shall keep track of the absolute coordinates (for example, x=3 and y=9) and orientation (north, east, south, or west) of the turtle.
    2. It is responsible for translating any relative move request (i.e. "move forward" or "turn left")) from student_turtle.cpp into absolute coordinates and calling appropriate helper functions.
    3. This file shall NOT contain the logic of the turtle algorithm, but instead it shall translate the move requests from student_turtle.cpp to an absolute position to display the turtle.
    4. This file shall NOT contain the local map used by the turtle for recording how many times it has visited the square. However, it SHALL execute the call to displayVisits(int visits) to update the map display based on a number of visits sent to it by the turtle. (This means that the turtle is no longer calling displayVisits(), but instead the map display update happens as part of tracking the movement of the turtle within the maze simulation.)
    5. This file shall contain the function moveTurtle(..), as defined in student.h, which is the main interface of your code to the ece642rtle_student ROS node. It shall call a function such as studentTurtleStep(...) in ANDREWID_student_turtle.cpp to get the next move the turtle will make based on whether the turtle is facing a wall (passed using the bool bumped argument). It shall then use helper functions such as translatePos to translate this move into an absolute coordinates position. Bare-bones code of these functions exist in ANDREWID_student_maze.cpp to get you started. (Again, you can modify things beyond this if you need to, but suggest you consult with a TA if you are making things that seem like big modifications not discussed here.)
  3. ANDREWID_student_turtle.cpp (turtle coordinates): This is code that runs the turtle within the simulation environment provided by the maze code just described.
    1. This file shall keep track of the world as seen by the turtle.
    2. No references to the turtle's absolute position shall be made. For example, this file cannot make a call to bumped(x1,y1,x2,y2), but rather needs to obtain information regarding whether it has bumped into a wall via interacting with the maze function.
    3. The file shall keep an array that has the turtle's current understanding of the world as previously described, and send the number of visits to the maze display functions just described. This array is in terms of coordinates relative to the turtle's starting position, and does not "know" what the absolute coordinates are. Similarly it does not "know" what its absolute orientation is.
    4. The array shall keep track of how many times the turtle has entered a given cell. An entry in the array shall only be incremented when the turtle enters the cell for the first time, or after having left it and then re-entering it. (This means that a rotation in place or stopped turtle shall not increment the entry). Call a function you design in the maze module to display the turtle direction and number of visits after every turtle movement, which ultimately calls displayVisits(). You should re-use as much of that code as you can from the previous project, but it's up to you how to best do this.
    5. You should replace the studentMoveTurtle(...) that is currently in the file, and factor out its contents into functionality in both ANDREWID_student_turtle.cpp and ANDREWID_student_maze.cpp. You can modify the existing studentTurtleStep(..) function in this file, or write your own functions. (By "factor" we mean reorganize by splitting into two different pieces in this case, and then adding or modifying code as appropriate.)
    Recitation notes go through a pictorial example of how the files are meant to interact.
    After splitting your code across these files, be sure you can still build and run you code using build_run_turtle.sh
  4. Make sure your turtle functionality obeys the following guidelines, first mentioned in Project 3 (this is not going to be strictly enforced for this project, but will be important when you write invariants later). Recall that a "tick" means one call to moveTurtle.
  5. If you add any files other than ANDREWID_student_turtle.cpp and ANDREWID_student_maze.cpp:
  6. Make sure your code runs and solves the maze. Make sure your code preserves good style. Save your progress by compressing the ece642rtle folder -- this will be one part of your handin.
  7. Run with a new maze file:
    1. build_run_turtle.sh in $ECE642RTLE_DIR can be run with a command line argument to a maze file: ./build_run_turtle.sh [mazefile] . Make sure [mazefile] is just the name of the maze file, without the path (for example: m1.maze is fine, but src/ece642rtle/m1.maze is not).
    2. Run the following command: ./build_run_turtle.sh m2.maze
    3. Your turtle does not have to solve this maze to get credit for the project, but it must accurately display how many times each cell has been visited. Take a screenshot of the turtle that shows that the turtle has visited at least 20 cells, and has visited at least five cells at least twice. (You'll need to solve mazes like this in future projects. Consider this forewarning.)

Procedure Part 2 -- Match SD, Statechart, and code

  1. Create one or more sequence diagrams showing the interactions between the turtle and the maze.
  2. Create a statechart showing the design of the turtle. The statechart should be for the turtle code, not the maze code. (It is expected you'll probably use the statechart from this week's homework assignment for this, but you can make a new one if you choose.)
  3. Update the SD, turtle statechart, and code to match up to each other in the sense that the turtle code implements the statechart, and the statechart behaves in the way specified by the sequence diagram.
  4. You do not have to hand in the updated turtle code. And you don't have to get any modified code running for full credit, but we want you to try to get things both aligned and running so it at least solves the old maze.
  5. We suggest you start with your homework solution, but it is OK to throw that away and start over if you choose to do so. If your hand-in is the same as your homework solutions, that's fine. If you had to change them, also fine.
  6. In future projects we'll be increasing the emphasis on SD <=> statechart <=> code all matching up, so the more work you put into getting these to line up now, the more of a head start you'll have on being able to complete future projects where this is strictly required.

Procedure Part 3 -- Writeup

  1. Answer the following questions for your writeup:

Handin checklist:

  1. Your final code. (This code must build and successfully solve m1.maze. It probably will not solve m2.maze, and solving m2.maze is not required in this project.). This should be the project directory ( ~/catkin_ws/src/ece642rtle/), compressed and named p05_ece642rtle_[FAMILYNAME]_[GivenName]_[AndrewID].zip (.tar.gz is also accepted). Remember, any files that you modified in this directory must start with your Andrew ID! (except CMakeLists.txt, student.h)
  2. Your writeup, named p05_writeup_[FAMILYNAME]_[GivenName]_[AndrewID].pdf.

Zip the two files and submit them as P05_[FAMILYNAME]_[First name]_[Andrew ID].zip.

Other requirements:

Please do NOT put these files inside a subdirectory. When the hand-in is unzipped they should not have any directory associated with the file name, and should just unzip into the current directory. (The file name convention will retain whose work it is.) It is OK to put the code inside the code zip file inside a code a directory (i.e., the code, when unzipped, can be in a directory, but the .pdf and .zip file from the checklist must unzip without directory info.

The rubric for the project is found here.


Changelog: