CS 161: Introduction to Computer Science • Spring 2015 • University of Puget Sound

Quick Links: Home • Calendar • Labs • Homeworks • Project • Resources

CS 161 Homework 4 - Karol the Robot

Due Wed Feb 25 Thu Feb 26 at 11:59pm

Overview

In this assignment, you will be programming a simple "robot" named Karol with a mission to completely explore its environment--no matter what the environment looks like. The challenge is that Karol is very near-sighted, so you will only be able to use local sensing to determine what is nearby. You will be implementing methods that allow Karol to decide how to walk through environments based on this sensing.

The programming in this homework will give you a chance to practice working with if statements and booleans. The more difficult part of the assignment though involves practicing thinking through a logical problem like a computer scientist: how can you come up with a specific set of decisions that will work in a more general case (e.g., perform abstraction)? You'll need to come up with the logical solution for how to move the robot, and then convert that logic into the formal language of code.

This assignment should be completed individually. I encourage you to try and think through the logical problems on your own (it's good practice for future assignments and exams), but you are welcome to discuss algorithmic ideas with others--just remember the Gilligan's Island Rule.

Objectives

To practice working with conditionals (if/else statements)
To practice using methods and constants
To practice writing comments
To practice with logical thinking

Necessary Files

You will need a copy of the Hwk4.zip file. The BlueJ project in this file includes two classes for you:

Karol is a class representing the Karol bot. The basic outline of the class has been provided for you, but you will need to fill in most of the methods. More details on the Karol class can be found below.
- To "start" your program, just use BlueJ to instantiate a new Karol object!
Environment is a class representing the environment that Karol is exploring. It also creates the GUI (graphical user interface, e.g. the window and buttons) for the program. You will not need to modify this class--you won't even need to look at its code, though you are welcome to if you wish. An Environment object is instantiated by Karol when the bot is first created, via the constructor.
- The control button should self-explanatory, but if there are any questions let me know!

The project also contains the README.txt that you will need to fill out and turn in along with your assignment.

Remember to extract the files from the zip folder before proceeding!

Background: Karol

It may not look like much, but Karol (see below) is a robot. Karol's job is to search every inch of its environment--the exact same way a Roomba tries to automatically vacuum the entire floor.

Karol is the green square. The walls of the room are blue; and the empty area (the floor) is white. Each time Karol takes a step, it leaves a gray trail behind it. Karol stops automatically when it has completely explored the room, content in a job well done. Note that Karol starts at a random location in the room---you can't assume anything about the initial location!

Sensing Surroundings

But to match it's simple shape, Karol is a very simple robot. It doesn't have a map of its environment, so it can't plan ahead to figure out where to go (think about this!) It also can't see very far--only one square to the north, east, south, and west of it:
Karol can perform this sensing by calling methods on the object representing its Environment. These methods have already been created, and have the signatures:
```
public boolean hasWallNorth()
public boolean hasWallSouth()
public boolean hasWallEast()
public boolean hasWallWest()
```
Note that each method returns a boolean of whether or not there is a wall in the appropriate direction (true if there is a wall, false if there is not).
- Remember to call these methods on Karol's Environment object (which is saved as an instance variable for you)!
By combining the results of these methods, you can determine which of the 16 possible surroundings Karol may find itself in:

Karol's Memory (State)

But this is where it gets complicated. Like a Roomba, Karol doesn't have a very good memory, and suffers from a severe form of the doorway effect. Karol can only remember one thing between each "step" it takes: a single int that is called the state. You can think of it like Karol has a bunch of different "modes" that it can be in. So it might be in "go north" mode, or it might be in "go south" mode. We represent each mode with a number (starting at 0), so we have mode 0, mode 1, mode 2, etc. (This is also refered to as state 0, state 1, state 2, etc). Karol always begins in state 0---remember, computer scientists start counting at 0!
- It can help to think of the state as something like a traffic light. If the state is "green", then cars should go. if the state is "yellow", then cars should slow down. If the state is "red", then cars should stop.
Karol does know what state it is in--the state is saved as an instance variable. And this is in fact the only instance variable Karol can have (besides remembering which Environment it is in)! Nevertheless, just this simple memory is enough to give Karol the intelligence to traverse its environment.
- Fun fact: Karol is an example of a finite state machine, a theoretical computer you'll learn about more in future courses (specifically, MA 210)!

Moving Around

Like a computer algorithm, Karol moves through its environment one step (one square) at a time. It can only move in one of the cardinal directions: north, south, east or west.
Based only on the information it can sense from its environment and on its current state, Karol needs to make a decision about what direction to move for each step. This decision is written as a method that tells karol how to step through a particular map. For example
public int stepEmptyMap()

determines how to take a step while navigating the "empty" map (the first map), while

public int stepMazeMap()

determines how to take a step while navigating the "maze" map (the second map).
Each of these maps returns an int representing what direction to move. The actual values of these directions are unimportant: you should instead use constants provided by the Environment class to represent what direction. For example, Environment.NORTH represents the "north" direction, while Environment.WEST represents the "west" direction (the other two are Environment.SOUTH and Environment.WEST. There is also an Environment.NONE if Karol shouldn't move at all).
In addition to returning what direction to move, remember that you can also have Karol decide to change state after every step. Thus each time the "step" method is called, Karol should determine what number state to change to (if any), and what direction to move (if any).
- You can think of Karol as obeying a number of "rules" like:
  If Karol is in mode 0, and sees a wall to the South (but no other walls), then it should move North and stay in mode 0.

Online Version

You can play with an browser-based version of Karol here. Note that this version has you specify "rules" (rather than if statements), in the form of
```
StateNow   Surroundings   ->   MoveDirection   NewState
```
For example:
```
0   xxxS   ->   N   0
```
is a rule that says "if Karol is in mode 0, and sees surroundings xxxS [as described above], then it should move North and stay in mode 0."
This may be useful for thinking about a set of rules to work with, though you will need to implement your solution in Java.

Assignment Details

Your task is to complete the provided Karol class so that the robot is able to successfully navigate the "empty room" (map 0), the "maze" (map 1), and the "diamond" (map 2):

Remember that Karol will always begin in a random location, and your solution will need to account for that!

The first thing you should notice is that the provided Karol class is completely without comments! You should remedy this shortcoming.
1. Add in complete and properly formatted JavaDoc comments for the class comment and for each method, including the constructor. JavaDoc format is described on page 90 of the textbook.
2. Also add inline comments for the provided code (e.g., the instance variables and the constructor). Remember that comments should explain the why of the code, not the what. Try to explain what the code is doing at a higher level of abstraction!
You'll need to implement the stepEmptyMap() method so that Karol is able to navigate the empty map (map 0). To get you started, some hints are below:
1. Start by just trying to make Karol move at all each step. You should be able to just change the returned value (use one of the provided constants).
2. Next, can you add in logic (e.g., using if statements and the values of the state and the surroundings) to make Karol fill in a single grey line from top to bottom? You'll want to go all the way to the North, and then turn around and go all the way to the South.
  - Consider using two different state values: one for if you are going north, and one for if you are going south. You'll need to have your algorithm make a decision (e.g., with an if statement) about whether you should change state. You'll want to return one value if you want to go north, and a different value if you want to go south!
  - Helpful hint: Try printing out the state variable at different points in your method, and then use the provided "step" button to have Karol take a single step. This can help you trace what is going on!
3. Finish up by adding further "rules" so that Karol can cover the entire map. Again, think about what states or "modes" Karol should have, what you should do in those states and with different surroundings, and when you want to change states.
4. Be sure and test your method with different starting points for Karol (hit the "Reset" button to try again).
5. Include a lot of comments explaining your logic. Why are you moving to each state? What are the "rules" you are following? A good rule of thumb would be to include a comment for each if statement explaining what condition that represents.
You'll need to implement the stepMazeMap() method so that Karol is able to navigate the maze map (map 1). Hint: think about using a wall-following process, such as where you always turn to the right to explore the maze.
- Think about "exploring" passages in a spiral manner--always going to the "right" first. That is, if Karol is "facing" north, it would like to explore "east" passages; if it's facing east, it would like to explore south passages, and so forth.
- The trick is: you don't want to go as far in one direction as possible (you might miss a branching path!), but to always take the left-hand turn if you can. Use the state to represent Karol's current "facing" (e.g., 0 is north, 1 is east, etc), and think about taking the "left" path (relative to that facing) each time if you can. If you can't, go forward; if you can't, go right; if you can't, go back.
- The maze is one of those pieces that you need to have most of the parts implemented in order to feel like you're making progress :(
Hint
You'll need to implement the stepDiamondMap() method so that Karol is able to navigate the diamond map (map 2). Hint: can you use a similar process to clearing the empty map?
You'll need to implement the stepStalactiteMap() method so that Karol is able to navigate the stalactite map (map 3). Note that this is a much harder map the than previous three!

Hint: you might try thinking about alternating between "sweeping" over the whole map from north to south, and "sweeping" over the whole map from east to west, so that you can get into each nook and cranny!
And that's it! I have provided additional maps if you want the challenge, but solving them is not required. You can complete the stalactite map for extra credit.

Extensions

As mentioned above, you can view Karol's logic as being made up of a number of "rules" (each of which might corresponds to a single "return" statement). How many "rules" do your solutions take? Can you come up with a more "efficient" solution? (that takes less rules--has fewer if statements?)
- The records are 6 rules for the empty map and 8 rules for the maze map. Can you match those?
For extra credit, you can also try to make Karol look more interesting by writing your own drawing function. To do this, add a method with the signature:

public void draw(Graphics brush)
Inside this method, you can call methods on the provided Graphics object in order to draw your Karol bot.
- When this method is called, Karol's "square" has its upper-left corner at graphical coordinates (0,0).
- Karol should be drawn within a 20x20 pixel rectangle (with upper-left corner (0,0)) for best results.

Submitting Your Assignment

There are a couple of details to keep in mind before you submit your assignment.

Double-check that your methods are completed and work correctly.
- If your program doesn't compile, I can't give you credit for it!
Make sure that your code is commented. Give lots of inline comments: I should be able to understand your robot's logic just from the comments, without really reading the code itself!
You will also need to fill out the README.txt file. You can open this file in BlueJ by double-clicking on the white paper icon in the upper left corner of the class window. You should place the answer to each question below the question box, replacing the "<Replace this with your response!>". Remember to save your changes (select "Class > Save" from the menu).
You should compress the entire Hwk4 folder into a single zip file (like you did for Lab A), and then submit it to the Hwk4 Submission page on Moodle.
- Be sure an upload the ENTIRE project folder--that is what includes all your work!
This assignment is due at midnight on ~~Wed, Feb 25~~ Thu, Feb 26. Important note: we have an exam the next day, so getting this done earlier will make your life less stressful!

Grading

This assignment will be graded out of 40 points (again, same worth as other homeworks, just higher precision). Map explorations are worth multiple points: you will earn partial credit depending on how much of the map you can explore!

Map Exploration (28pt)
You have not used any extraneous instance variables (Karol has only a single state) //required to get full credit for map exploration
[6pt] Karol is able to completely explore the empty map
[12pt] Karol is able to completely explore the maze map
[10pt] Karol is able to completely explore the diamond map
Style & Documentation (12pt)
[1pt] You utilize the constants provided by the Environment class
[1pt] Your code is properly formatted (indentation, etc) and methods/variables are properly named
[1pt] Your code includes a JavaDoc class comment that includes your name
[1pt] The provided instance variables and constructor contains explanatory inline methods
[1pt] Each method (including the constructor) has a descriptive JavaDoc comment
[2pt] JavaDoc comments are properly formatted, with correctly used @param and @return tags
[2pt] Each "step" method includes descriptive inline comments explaining your logic
[2pt] Inline comments explain the why, not the what of the code
[1pt] You have completed the included README.txt file

Joel Ross • jross@pugetsound.edu

Based on assignment by Zach Dodds and Wynn Vonnegut (HMC).

Page Last Modified: 2015-02-25 10:08:22 -0800

Mathematics and Computer Science Department • University of Puget Sound