CS 161 Lab A - Karol the Robot

Due Fri Sep 06 at 9:00am

Overview

In this lab you will do your first piece of programming. You will program 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, so instructions need to be based only on what is nearby.

This will give you a chance to practice thinking like a computer scientist: how we can write specific instructions in a very specific format in order to solve a problem. It will also give you a chance to practice submitting your work (in this case, the set of instructions for the robot) electronically.

Note that this lab (and all subsequent labs) will be completed in pairs. Be sure to review the pair programming guidelines before you begin!

Objectives

Necessary Files

Here is a link to the online Karol simulation (new window). Note that you will need to use the Chrome or Firefox browser to program Karol.

You will not need any additional files for this lab.

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.

For example, in the above image, Karol can see a wall to the north and a wall to the west, but sees nothing to the east or south. In order to make things easier, we can write out a list of which directions have walls by giving a list of 4 letters, such as: 

NxWx

So we don't get confused, we always list the walls in NEWS order (north, then east, then west, then south). If there is a wall, we put the appropriate letter (N, E, W or S). If there is not a wall, we put an x. This way we can write down all the possible surroundings Karol might find itself in:

Do you see how this covers all the options? Note that Karol can only see if there is a wall or not, not the gray path it leaves behind.

You can also also use an asterisk (*) as a wildcard in listing surroundings. An asterisk means "I don't care if there is a wall or not". For example, xE** means "there is no wall to the north, there is a wall to the east, and it doesn't matter if there are walls to the west and south."

In order to program Karol to explore, you'll need to tell Karol what it should do depending on its surroundings. So if the surroundings are xExx, Karol should probably go east. If the surroundings are NxxS, you'll need to choose what to do. Making these kinds of decisions ("if this is the situation, what do I do?") is one of the main steps in programming. We will define these decisions as rules. So a rule might be "if surroundings are xExx, move east." Another rule might be "if surroundings are NxxS, move south." Programming Karol simply involves coming up with a set of rules that will let it explore the environment. (See below for exactly how we specify rules).

Karol's Memory (State)

But this is where it gets complicated. Karol doesn't have a very good memory, and so can only follow one rule at a time! Remembering which rule it is following is called the state. Think of it like Karol has a bunch of different routines or "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---computer scientists start counting at 0.

Karol does know what state it is in. And knowing the state and the surroundings is all Karol needs to traverse the environment!

Rules

We specify rules for Karol in the following format: 

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, then it should move North and stay in mode 0."

The MoveDirection can be N, E, W, S or X, representing the direction to move or, in the case of X, the choice to not move at all.

If this were Karol's only rule and if Karol began (in state 0) at the bottom of an empty room, it would move up (north) one square and stay in state 0. However, Karol would then not move any further, because its surroundings would have changed to xxxx, which does not match the rule!

Try making a small change to the example ruleset in the Karol simulation and see what happens!

Karol is programmed with multiple rules, each rule on a separate line. The robot starts by looking at the top rule, and seeing if it applies (i.e., if it matches the current state and surroundings). If that rule does not applied, the robot looks at the next rule in the list, searching down the list from top to bottom. If the rule does apply, then Karol moves and changes state as specified. Karol then starts all over again, starting at the top rule and looking for one that applies..

Again, once a valid rule is found, then Karol starts at the top of the list! Rules are not like driving directions; they are a list of conditional behaviors that the robot will follow.

Comments

Note that anything after a pound sign (#) is a comment. Comments are like margin notes---as a human programmer you can read them to understand what is going on, but they don't change the program. Karol will ignore comments. Blank lines are also ignored.

An Example

Consider the following set of rules:

# state 0 goes N as far as possible
0 x*** -> N 0   # if there's nothing to the N, go N
0 N*** -> X 1   # if N is blocked, switch to state 1

# state 1 goes S as far as possible
1 ***x -> S 1   # if there's nothing to the S, go S
1 ***S -> X 0   # otherwise, switch to state 0

Remember that Karol always starts in state 0. Karol looks at the rules from top to bottom until it finds the first rule that applies. It uses that rule to make its move and enter its next state. It then starts all over again, looking at rules and finding the first one from the top that appplies.

In this case, Karol will follow the first rule up to the "top" of its environment, moving north and staying in state 0 the whole time. Eventually, it encounters a wall to its north. At this point, the topmost rule no longer applies. However, the next rule 0 N*** -> X 1 does apply now! So, Karol uses this rule which causes it to stay put (due to the X in the MoveDirection) and switch to state 1. Now that it is in state 1, neither of the first two rules will apply. Karol follows state 1's rules, which guide it back to the "bottom" of its environment. And so it continues...

Assignment Details

Your task is to design two sets of rules for Karol:

  1. A set of rules that will allow Karol to completely cover an empty square room (map 1).
  2. A set of rules that will allow Karol to completely cover a connected maze (without loops) that has corridors one square wide. This is "Map 2"---just click on the right arrow next to "MAP" on the simulator.

Your solutions must work from the any of the random starting positions within the environment.

Remember to click on the "Enter rules for Karol" before you try to run Karol!

After you have written a working solution, you will need to submit it to the submission folder on the hedwig server.

After you have submitted your solution, log onto Moodle and submit the Lab A Partner Evaluation. You should get in the habit of submitting the evaluation after each lab.

You should write as complete and correct a solution as you can in the two hour lab time. If you finish early, see if you can find solutions for any of the later maps. They get harder as they go! ;)

Helpful Hints

Extensions

You might think about how efficient your solutions are---both in terms of the number of states used and in terms of the number of rules. There are other ways to measure efficiency as well (e.g., speed). Once you have everything working, try and design a solution that will explore the environment with as few rules as possible. Can solve the empty room with 7 rules, or the maze with 8 rules?

Submission

Submit your solutions to the two maps as two separate text files (with both your names on them) to the LabA submission folder on hedwig. Make sure you upload your work to the correct folder! The lab is due at the start of class the morning after lab.

Grading

This assignment will be graded on approximately the following criteria:

Note that it is very easy to get partial credit, so turn in whatever you have at the end of the lab! Be sure and include a note about the status of your solution in a comment (that's what they're for).