CS5 - PicobotProgrammingGold

Week 0, Problems 3 and 4: Picobot

[20 points each; individual or pair, e.c. up to +8]

Introduction to Picobot

This problem explores a simple "robot," named "Picobot," whose goal is to completely traverse its environment.

Picobot starts at a random location in a room—you don't have control over Picobot's initial location. The walls of the room are blue; Picobot is green, and the empty area is white. Each time Picobot takes a step, it leaves a grey trail behind it. When Picobot has completely explored its environment, it stops automatically.

Surroundings

Not surprisingly, Picobot has limited sensing power. It can only sense its surroundings immediately to the north, east, west, and south of it.

In the above image, Picobot sees a wall to the north and west and it sees nothing to the east or south. This set of surroundings would be represented as follows:

NxWx

The four squares surrounding Picobot are always considered in NEWS order: an x represents empty space, while the appropriate direction letter (N, E, W, and S) represents a wall blocking that direction. Here are all of the possible Picobot surroundings:

State

Picobot's memory is also limited. In fact, it has only a single value from 0 to 99 available to it. This number is called Picobot's state. In general, "state" refers to the relevant context in which a computation takes place. Here, you might think of each "state" as one piece—or behavior—that the robot uses to achieve its overall goal. Or you could think of as state from Picobot's point of view: "I (Picobot) am doing action" or "I am moving direction" or even "I am moving direction while knowing fact".

Picobot always begins in state 0.

The state and the surroundings are all the information that Picobot has available to make its decisions!

Rules

Picobot moves according to a set of rules of the form

StateNow Surroundings -> MoveDirection NewState

For example,

0 xxxS -> N 0

is a rule that says "if Picobot starts in state 0 and sees the surroundings xxxS, it should move North and stay in state 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 Picobot's only rule and if Picobot began (in state 0) at the bottom of an empty room, it would move up (north) one square and stay in state 0. However, Picobot would not move any further, because its surroundings would have changed to xxxx, which does not match the rule above.

Wildcards

The asterisk * can be used inside surroundings to mean "I don't care whether there is a wall or not in that position." For example, xE** means "there is no wall North, there is a wall to the East, and there might or might not be a wall to the West or South."

As an example, the rule

0 x*** -> N 0

is a rule that says "if Picobot starts in state 0 and sees any surroundings without a wall to the North, it should move North and stay in state 0."

If this new version (with wildcard asterisks) were Picobot's only rule and if Picobot began (in state 0) at the bottom of an empty room, it would first see surroundings xxxS. These match the above rule, so Picobot would move North and stay in state 0. Then its surroundings would be xxxx. These also match the above rule, so Picobot would again move North and stay in state 0. In fact, this process would continue until it hit the "top" of the room, when the surroundings Nxxx no longer match the above rule.

Comments

Anything after a pound sign (#—you might think of it as a "hashtag" but computer scientists usually call it a pound sign) on a line is a comment (as in Python). Comments are human-readable explanations of what is going on, but are ignored by Picobot. Blank lines are ignored as well.

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

Recall that Picobot always starts in state 0. Picobot now consults 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 the rules and finding the first one from the top that applies.

In this case, Picobot 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 Picobot uses this rule, which causes it to stay put (due to the "X") and switch to state 1. Now that it is in state 1, neither of the first two rules will apply. Picobot follows state 1's rules, which guide it back to the "bottom" of its environment. And so it continues….

The assignment

For this assignment, your task is to design two different sets of Picobot rules:

Problem 3: one set of rules that will allow Picobot to completely cover an empty square room
Problem 4: one set of rules that will allow Picobot to completely cover the maze (click the arrows next to "MAP" to switch maps)
- In class, we may have motivated three rules (all for state 0, "facing North")
- 0 xE** -> N 0 # "corridor rule"
- 0 *x** -> E 1 # "intersection rule"
- 0 NE** -> X 2 # "dead end rule"

This approach will require 9 more rules (three more for each of the three other states):
- We'd recommend using state 0 for "facing North"
- We'd recommend using state 1 for "facing East"
- We'd recommend using state 2 for "facing West"
- We'd recommend using state 3 for "facing South"

Suggestion from class! Use states to represent the "direction Picobot is facing":
Graphical motivation of Picobot's three state 0 rules, with solutions on the right-hand side:

Things to remember

Click on the "Enter rules for Picobot" before you try to run Picobot
Your solutions must work from arbitrary starting positions within the environment

To submit your work

You need to copy your rules into a plain-text .txt file on your computer!
- For the empty-room problem, be sure to name it hw0pr3.txt
- For the maze, be sure to name it hw0pr4.txt
Submit your work
- hw0pr3.txt via GradeScope
- hw0pr4.txt via GradeScope

Optional extra credit

At its heart, CS fundamentally tries to answer questions of complexity: to show that problems are easier than initially thought—or, sometimes, to prove that they can't be handled with fewer resources. 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).

For extra-credit karma, try to create as efficient a solution as possible for the maze-solving set of rules. That is,

For problem 3 (the empty room), see if you can use only 6 rules [worth karma—more valuable than points!]
For problem 4 (the maze), see if you can use only 8 rules [worth more karma units!]

For extra-credit points, try some other Picobot challenges:

Problem 5 is solving the "diamond" map that looks like this (with any number of rules): [worth +4 points]
Be sure to name your file hw0pr5.txt
Problem 6 is solving the "stalactite" map that looks like this one (with any number of rules): [worth +4 points]
Be sure to name your file hw0pr6.txt

Optional extra challenge

For an extra challenge, try to create as efficient a solution as possible for the maze-solving set of rules. That is,

For problem 3 (the empty room), see if you can use only 6 rules
For problem 4 (the maze), see if you can use only 8 rules

If you accomplish either, let us know!